Finding three elements in an array whose sum is closest to a given number

Question

Given an array of integers, A₁, A₂, ..., A_n, including negatives and positives, and another integer S. Now we need to find three different integers in the array, whose sum is closest to the given integer S. If there exists more than one solution, any of them is ok.

You can assume all the integers are within int32_t range, and no arithmetic overflow will occur with calculating the sum. S is nothing special but a randomly picked number.

Is there any efficient algorithm other than brute force search to find the three integers?

Gauffer

If you're looking for a sum equal to a number (and not closest), this would be the 3SUM problem. – Plasmo

Answer 1

Is there any efficient algorithm other than brute force search to find the three integers?

Yep; we can solve this in O(n²) time! First, consider that your problem P can be phrased equivalently in a slightly different way that eliminates the need for a "target value":

original problem P: Given an array A of n integers and a target value S, does there exist a 3-tuple from A that sums to S?

modified problem P': Given an array A of n integers, does there exist a 3-tuple from A that sums to zero?

Notice that you can go from this version of the problem P' from P by subtracting your S/3 from each element in A, but now you don't need the target value anymore.

Clearly, if we simply test all possible 3-tuples, we'd solve the problem in O(n³) -- that's the brute-force baseline. Is it possible to do better? What if we pick the tuples in a somewhat smarter way?

First, we invest some time to sort the array, which costs us an initial penalty of O(n log n). Now we execute this algorithm:

for (i in 1..n-2) {
  j = i+1  // Start right after i.
  k = n    // Start at the end of the array.

  while (k >= j) {
    // We got a match! All done.
    if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])

    // We didn't match. Let's try to get a little closer:
    //   If the sum was too big, decrement k.
    //   If the sum was too small, increment j.
    (A[i] + A[j] + A[k] > 0) ? k-- : j++
  }
  // When the while-loop finishes, j and k have passed each other and there's
  // no more useful combinations that we can try with this i.
}

This algorithm works by placing three pointers, i, j, and k at various points in the array. i starts off at the beginning and slowly works its way to the end. k points to the very last element. j points to where i has started at. We iteratively try to sum the elements at their respective indices, and each time one of the following happens:

• The sum is exactly right! We've found the answer.
• The sum was too small. Move j closer to the end to select the next biggest number.
• The sum was too big. Move k closer to the beginning to select the next smallest number.

For each i, the pointers of j and k will gradually get closer to each other. Eventually they will pass each other, and at that point we don't need to try anything else for that i, since we'd be summing the same elements, just in a different order. After that point, we try the next i and repeat.

Eventually, we'll either exhaust the useful possibilities, or we'll find the solution. You can see that this is O(n²) since we execute the outer loop O(n) times and we execute the inner loop O(n) times. It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.

---

Note: Because this is an interview question, I've cheated a little bit here: this algorithm allows the selection of the same element multiple times. That is, (-1, -1, 2) would be a valid solution, as would (0, 0, 0). It also finds only the exact answers, not the closest answer, as the title mentions. As an exercise to the reader, I'll let you figure out how to make it work with distinct elements only (but it's a very simple change) and exact answers (which is also a simple change).

Inspectorate

It seems the algorithm can only find 3-tuple that equals to S, not closest to S. – Gauffer

ZelluX: As I mentioned in the note, I didn't want to give too much away since it's an interview problem. Hopefully you can see how to modify it so that it gets you the closest answer, though. (Hint: one way is to keep track of the closest answer so far and overwrite it if you find a better one.) – Inspectorate

@John Feminella: I have thought about this algorithm before, but I thought it might miss some closer sum when moving the two pointer, and after trying to find some counterexamples I figure out that's a right algorithm :P – Gauffer

You claim that "Notice that you can go from this version of the problem P' from P by subtracting your target value from each element in A, but now you don't need the target value anymore." If you do this you'll end up with numbers y0 = x0-S, y1 = x1-S, y2 = x2-S such that y0+y1+y2 add to 0, then x0+x1+x2 = 3S not S... Now if S is divisible by 3 then you could subtract S/3 instead of S .. but what if it is not? – Cromer

@Michael Anderson: Sorry, I wasn't completely clear about this part, and you're right; you must subtract S/3, not S. However, it's the same problem even if S isn't divisible by 3. For instance, say you want to find a 3-tuple for S = 11 in [1, 2, 4, 5]. That's the same as finding which numbers sum to zero in [(1 - 11/3), (2 - 11/3), (4 - 11/3), (5 - 11/3)]. The algorithm only cares that numbers can be summed; it doesn't actually care that they're integers. – Inspectorate

@John Feminella: That makes sense. Anyone implementing this will just need to be a bit careful about data type conversions. – Cromer

what if we don't modify the problem statement, instead we will search for aj and ak that sum to ai +S. – Headley

@Raccha: But now you have to pass another parameter to that function (S), which increases its complexity. My approach is simpler if you're willing to do the precomputation. – Inspectorate

@ZelluX: It's similar to how a merge sort works (that's how it first clicked for me). What that inner loop is trying to do is prove that either A[j] or A[k] cannot be part of any satisfying solution. The problem at any point is: "Is there any pair j' >= j and k' <= k such that A[j] + A[k] = S - A[i]?" Looking at the current pair (i, j), there are 3 possibilities: the sum is bang on (stop -- we've won!), it's too low, or it's too high. If it's too low, then the sum A[j] + A[k'] must also be too low for every k' <= k, since in each such sum the first term (A[j]) will be the same... – Literature

... and the second term (A[k']) will be the same or even lower than A[k]. So in this case we have proven that A[j] cannot participate in any satisfying sum -- so we may as well discard it! Which we do by setting j = j+1 and starting over (though it may help to think in terms of solving a smaller subproblem recursively instead). Likewise if the sum A[j] + A[k] is too high, then we know that A[j'] + A[k] must also be too high for every j' >= j, since A[j'] must be at least as big as A[j] and we're already too high. This means we can safely discard A[k] by setting k = k-1 and starting over. – Literature

j should start at i+1, otherwise you're testing A[i]*2 +A[k] with the first run. – Sandisandidge

There is an issue when subtracting S/3 from A[]. Please see details below. – Electrocorticogram

So how is this O(n^2) when you still had to sort the array at O(nlogn)? – Restaurant

@user1529412: That's from the definition of computational complexity notation. O(n log n) + O(n^2) = O(n^2) -- the n^2 term will always dominate. See: en.wikipedia.org/wiki/Big_O_notation – Inspectorate

How can I "keep track of the closest answer so far and overwrite it if you find a better one"? I cannot write code for inside the 'while loop' correctly. – Cresida

I wrote this code in Java, based on your suggestion: ideone.com/uYv5hp, do you have any suggestion or improvement on that? I really appreciate. Thanks – Cresida

Please note that you can use binary search instead of brute force search. So complexity of entire solution becomes O(nlogn). – Gwin

@AlexanderSandler This is the well-known 3SUM problem, for which no-one managed to figure out an O(n log n) solution to date. You're welcome to post an answer with working well-tested code if you think you managed to do so though. – Plasmo

Answer 2

certainly this is a better solution because it's easier to read and therefore less prone to errors. The only problem is, we need to add a few lines of code to avoid multiple selection of one element.

Another O(n^2) solution (by using a hashset).

// K is the sum that we are looking for
for i 1..n
    int s1 = K - A[i]
    for j 1..i
        int s2 = s1 - A[j]
        if (set.contains(s2))
            print the numbers
    set.add(A[i])

Jumper

Downside is O(N) storage, rather than doing it in-place. – Chessman

Using a hashset isn't strict O(n^2) since the hash set can degenerate in rare occasions, resulting in up to linear lookup times. – Plaque

@Charles - Also the solution of John needs O(N) space, since you change the original array while sorting. That means the caller might need a defensive copy before using the function. – Southeastward

I think there's an error in your algorithm. s2 might be an already selected element. E.g. if the array is 0,1,2 and K is 2, there shouldn't be an answer. I think your algorithm will output 0,1,1 which is obviously incorrect. – Catamenia

Answer 3

John Feminella's solution has a bug.

At the line

if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])

We need to check if i,j,k are all distinct. Otherwise, if my target element is 6 and if my input array contains {3,2,1,7,9,0,-4,6} . If i print out the tuples that sum to 6, then I would also get 0,0,6 as output . To avoid this, we need to modify the condition in this way.

if ((A[i] + A[j] + A[k] == 0) && (i!=j) && (i!=k) && (j!=k)) return (A[i], A[j], A[k])

Cist

John Feminella solution is just to present algorithm to solve problem, he has also specified that his solution wouldn't work for distinct number condition and you have to modify above code little bit which he has left for reader. – Larvicide

Actually, i will never be j since you are always starting it at j = i + 1. The only real condition that you should check is whether j == k. However, by setting the while loop to j < k, you've solved the problems without a lengthy if statement since k will always be greater than j and j always greater than i. – Sedgewinn

This does not seem like an answer to the question, but rather like a comment on John Feminella's answer. – Plasmo

Answer 4

How about something like this, which is O(n^2)

for(each ele in the sorted array)
{
    ele = arr[i] - YOUR_NUMBER;
    let front be the pointer to the front of the array;
    let rear be the pointer to the rear element of the array.;

    // till front is not greater than rear.                    
    while(front <= rear)
    {
        if(*front + *rear == ele)
        {
            print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
            break;
        }
        else
        {
            // sum is > ele, so we need to decrease the sum by decrementing rear pointer.
            if((*front + *rear) > ele)
                decrement rear pointer.
            // sum is < ele, so we need to increase the sum by incrementing the front pointer.
            else
                increment front pointer.
        }
    }

This finds if sum of 3 elements is exactly equal to your number. If you want closest, you can modify it to remember the smallest delta(difference between your number of current triplet) and at the end print the triplet corresponding to smallest delta.

Confess

if you want to find k elements to get the sum what is the complexity? How you deal with this? – Piezochemistry

With this approach, complexity for k elements is O(n^(k-1)) for k >= 2. You need to add an outer loop for every additional summand. – Plaque

Answer 5

Note that we have a sorted array. This solution is similar to John's solution only that it looks for the sum and does not repeat the same element.

#include <stdio.h>;

int checkForSum (int arr[], int len, int sum) { //arr is sorted
    int i;
    for (i = 0; i < len ; i++) {
        int left = i + 1;
        int right = len - 1;
        while (right > left) {
            printf ("values are %d %d %d\n", arr[i], arr[left], arr[right]);
            if (arr[right] + arr[left] + arr[i] - sum == 0) {
                printf ("final values are %d %d %d\n", arr[i], arr[left], arr[right]);
                return 1;
            }
            if (arr[right] + arr[left] + arr[i] - sum > 0)
                right--;
            else
                left++;
        }
    }
    return -1;
}
int main (int argc, char **argv) {
    int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29};
    int sum = 4;
    printf ("check for sum %d in arr is %d\n", sum, checkForSum(arr, 10, sum));
}

Margrettmarguerie

It is needed to calculate absolute difference of a[r] + a[l] + a[i] - sum. Try on arr = [-1, 2, 1, -4] sum = 1. – Buchmanism

Answer 6

Here is the C++ code:

bool FindSumZero(int a[], int n, int& x, int& y, int& z)
{
    if (n < 3)
        return false;

    sort(a, a+n);

    for (int i = 0; i < n-2; ++i)
    {
        int j = i+1;
        int k = n-1;

        while (k >= j)
        {
            int s = a[i]+a[j]+a[k];

            if (s == 0 && i != j && j != k && k != i)
            {
                x = a[i], y = a[j], z = a[k];
                return true;
            }

            if (s > 0)
                --k;
            else
                ++j;
        }
    }

    return false;
}

Solifluction

Answer 7

Very simple N^2*logN solution: sort the input array, then go through all pairs A_i, A_j (N^2 time), and for each pair check whether (S - A_i - A_j) is in array (logN time).

Another O(S*N) solution uses classical dynamic programming approach.

In short:

Create an 2-d array V[4][S + 1]. Fill it in such a way, that:

V[0][0] = 1, V[0][x] = 0;

V1[A_i]= 1 for any i, V1[x] = 0 for all other x

V[2][A_i + A_j]= 1, for any i, j. V[2][x] = 0 for all other x

V[3][sum of any 3 elements] = 1.

To fill it, iterate through A_i, for each A_i iterate through the array from right to left.

Akkad

slight change to the first algorithm.. if the element doesn't exist, then at the end of the binary search, we'd have to look at the element on the left, current, and right to see which one gives the closest result. – Sniffle

The array is too big and it is not O(s*N) . This step is O(N^2 ) : V[2][Ai + Aj]= 1, for any i, j. V[2][x] = 0 for all other x . – Instantaneity

Answer 8

This can be solved efficiently in O(n log (n)) as following. I am giving solution which tells if sum of any three numbers equal a given number.

import java.util.*;
public class MainClass {
        public static void main(String[] args) {
        int[] a = {-1, 0, 1, 2, 3, 5, -4, 6};
        System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toString());
}

public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) {

    //O(n log (n))
    Arrays.sort(array);
    System.out.println(Arrays.toString(array));

    int leftIndex = 0;
    int rightIndex = array.length - 1;

    //O(n)
    while (leftIndex + 1 < rightIndex - 1) {
        //take sum of two corners
        int sum = array[leftIndex] + array[rightIndex];
        //find if the number matches exactly. Or get the closest match.
        //here i am not storing closest matches. You can do it for yourself.
        //O(log (n)) complexity
        int binarySearchClosestIndex = binarySearch(leftIndex + 1, rightIndex - 1, targetNumber - sum, array);
        //if exact match is found, we already got the answer
        if (-1 == binarySearchClosestIndex) {
            System.out.println(("combo is " + array[leftIndex] + ", " + array[rightIndex] + ", " + (targetNumber - sum)));
            return true;
        }
        //if exact match is not found, we have to decide which pointer, left or right to move inwards
        //we are here means , either we are on left end or on right end
        else {

            //we ended up searching towards start of array,i.e. we need a lesser sum , lets move inwards from right
            //we need to have a lower sum, lets decrease right index
            if (binarySearchClosestIndex == leftIndex + 1) {
                rightIndex--;
            } else if (binarySearchClosestIndex == rightIndex - 1) {
                //we need to have a higher sum, lets decrease right index
                leftIndex++;
            }
        }
    }
    return false;
}

public static int binarySearch(int start, int end, int elem, int[] array) {
    int mid = 0;
    while (start <= end) {
        mid = (start + end) >>> 1;
        if (elem < array[mid]) {
            end = mid - 1;
        } else if (elem > array[mid]) {
            start = mid + 1;
        } else {
            //exact match case
            //Suits more for this particular case to return -1
            return -1;
        }
    }
    return mid;
}
}

Brownstone

I don't think this is going to work. Granted, you have two simple cases of how to advance leftIndex or rightIndex when all the elements in the middle are either strictly smaller or larger than your desired number. But what about the case when binary search stopped somewhere in the middle? You would need to check both branches (where rightIndex-- and leftIndex++). In your solution you just ignore this situation. But I don't think that there is a way to overcome this issue. – Thorrlow

Answer 9

Reduction : I think @John Feminella solution O(n2) is most elegant. We can still reduce the A[n] in which to search for tuple. By observing A[k] such that all elements would be in A[0] - A[k], when our search array is huge and SUM (s) really small.

A[0] is minimum :- Ascending sorted array.

s = 2A[0] + A[k] : Given s and A[] we can find A[k] using binary search in log(n) time.

Nauseating

Answer 10

Here is the program in java which is O(N^2)

import java.util.Stack;


public class GetTripletPair {

    /** Set a value for target sum */
    public static final int TARGET_SUM = 32;

    private Stack<Integer> stack = new Stack<Integer>();

    /** Store the sum of current elements stored in stack */
    private int sumInStack = 0;
    private int count =0 ;


    public void populateSubset(int[] data, int fromIndex, int endIndex) {

        /*
        * Check if sum of elements stored in Stack is equal to the expected
        * target sum.
        * 
        * If so, call print method to print the candidate satisfied result.
        */
        if (sumInStack == TARGET_SUM) {
            print(stack);
        }

        for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

            if (sumInStack + data[currentIndex] <= TARGET_SUM) {
                ++count;
                stack.push(data[currentIndex]);
                sumInStack += data[currentIndex];

                /*
                * Make the currentIndex +1, and then use recursion to proceed
                * further.
                */
                populateSubset(data, currentIndex + 1, endIndex);
                --count;
                sumInStack -= (Integer) stack.pop();
            }else{
            return;
        }
        }
    }

    /**
    * Print satisfied result. i.e. 15 = 4+6+5
    */

    private void print(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        sb.append(TARGET_SUM).append(" = ");
        for (Integer i : stack) {
            sb.append(i).append("+");
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
    }

    private static final int[] DATA = {4,13,14,15,17};

    public static void main(String[] args) {
        GetAllSubsetByStack get = new GetAllSubsetByStack();
        get.populateSubset(DATA, 0, DATA.length);
    }
}

Fluorocarbon

Nice approach, but I could not get the point where you restrict the number of results to a triplet. For example consider the input: [1,11,3,4,5,6,7,8, 2] and sum 12, from your solution it appears that [1, 11] [4,8] [1,4,5,2] etc would all work. – Haem

Answer 11

The problem can be solved in O(n^2) by extending the 2-sum problem with minor modifications.A is the vector containing elements and B is the required sum.

int Solution::threeSumClosest(vector &A, int B) {

sort(A.begin(),A.end());

int k=0,i,j,closest,val;int diff=INT_MAX;

while(k<A.size()-2)
{
    i=k+1;
    j=A.size()-1;

    while(i<j)
    {
        val=A[i]+A[j]+A[k];
        if(val==B) return B;
        if(abs(B-val)<diff)
        {
            diff=abs(B-val);
            closest=val;
        }
        if(B>val)
        ++i;
        if(B<val) 
        --j;
    }
    ++k;

}
return closest;

Quincy

Answer 12

Here is the Python3 code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        result = set()
        nums.sort()
        L = len(nums)     
        for i in range(L):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1,L):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue  
                l = j+1
                r = L -1
                while l <= r:
                    sum = nums[i] + nums[j] + nums[l]
                    result.add(sum)
                    l = l + 1
                    while l<=r and nums[l] == nums[l-1]:
                        l = l + 1
        result = list(result)
        min = result[0]
        for i in range(1,len(result)):
            if abs(target - result[i]) < abs(target - min):
                min = result[i]
        return min

Cu

Answer 13

Another solution that checks and fails early:

public boolean solution(int[] input) {
        int length = input.length;

        if (length < 3) {
            return false;
        }

        // x + y + z = 0  => -z = x + y
        final Set<Integer> z = new HashSet<>(length);
        int zeroCounter = 0, sum; // if they're more than 3 zeros we're done

        for (int element : input) {
            if (element < 0) {
                z.add(element);
            }

            if (element == 0) {
                ++zeroCounter;
                if (zeroCounter >= 3) {
                    return true;
                }
            }
        }

        if (z.isEmpty() || z.size() == length || (z.size() + zeroCounter == length)) {
            return false;
        } else {
            for (int x = 0; x < length; ++x) {
                for (int y = x + 1; y < length; ++y) {
                    sum = input[x] + input[y]; // will use it as inverse addition
                    if (sum < 0) {
                        continue;
                    }
                    if (z.contains(sum * -1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

I added some unit tests here: GivenArrayReturnTrueIfThreeElementsSumZeroTest.

If the set is using too much space I can easily use a java.util.BitSet that will use O(n/w) space.

Mantegna

Answer 14

Program to get those three elements. I have just sorted the array/list first and them updated minCloseness based upon each triplet.

public int[] threeSumClosest(ArrayList<Integer> A, int B) {
    Collections.sort(A);
    int ansSum = 0;
    int ans[] = new int[3];
    int minCloseness = Integer.MAX_VALUE;
    for (int i = 0; i < A.size()-2; i++){
        int j = i+1;
        int k = A.size()-1;
        while (j < k){
            int sum = A.get(i) + A.get(j) + A.get(k);
            if (sum < B){
                j++;
            }else{
                k--;
            }
            if (minCloseness >  Math.abs(sum - B)){
                minCloseness = Math.abs(sum - B);
                ans[0] = A.get(i); ans[1] = A.get(j); ans[2] = A.get(k);
            }
        }
    }
    return ans;
}

Motorman

Answer 15

I did this in n^3, my pseudocode is below;

//Create a hashMap with key as Integer and value as ArrayList //iterate through list using a for loop, for each value in list iterate again starting from next value;

for (int i=0; i<=arr.length-1 ; i++){
    for (int j=i+1; j<=arr.length-1;j++){

//if the sum of arr[i] and arr[j] is less than desired sum then there is potential to find a third digit so do another for loop

      if (arr[i]+arr[j] < sum){
        for (int k= j+1; k<=arr.length-1;k++)

//in this case we are now looking for the third value; if the sum of arr[i] and arr[j] and arr[k] is the desired sum then add these to the HashMap by making the arr[i] the key and then adding arr[j] and arr[k] into the ArrayList in the value of that key

          if (arr[i]+arr[j]+arr[k] ==  sum){              
              map.put(arr[i],new ArrayList<Integer>());
              map.get(arr[i]).add(arr[j]);
              map.get(arr[i]).add(arr[k]);}

after this you now have a dictionary that has all the entries representing the three values adding to the desired sum. Extract all these entries using HashMap functions. This worked perfectly.

Snowdrift