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

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).

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.

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.

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;
}
}

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

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;
}