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

Question

Given an array of integers  A1  A2       An  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

User · Answer

Here is the C   code   bool FindSumZero int a    int n  int amp  x  int amp  y  int amp  z        if  n  lt  3          return false       sort a  a n        for  int i   0  i  lt  n-2    i                int j   i 1          int k   n-1           while  k  gt   j                        int s   a i  a j  a k                if  s    0  amp  amp  i    j  amp  amp  j    k  amp  amp  k    i                                x   a i   y   a j   z   a k                   return true                             if  s  gt  0                  --k              else                   j                       return false

User · Answer

Is there any efficient algorithm other than brute force search to find the three integers    Yep  we can solve this in O n2  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 n3  -- 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  gt   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   gt  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 n2  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

User · Answer

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  lt   rear                if  front    rear    ele                        print  Found triplet   lt  lt  front lt  lt     lt  lt  rear lt  lt     lt  lt ele lt  lt endl              break                    else                          sum is  gt  ele  so we need to decrease the sum by decrementing rear pointer              if   front    rear   gt  ele                  decrement rear pointer                 sum is  lt  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

User · Answer

Another solution that checks and fails early   public boolean solution int   input            int length   input length           if  length  lt  3                return false                        x   y   z   0    gt  -z   x   y         final Set lt Integer gt  z   new HashSet lt  gt  length           int zeroCounter   0  sum     if they re more than 3 zeros we re done          for  int element   input                if  element  lt  0                    z add element                              if  element    0                      zeroCounter                  if  zeroCounter  gt   3                        return true                                                     if  z isEmpty      z size      length     z size     zeroCounter    length                 return false            else               for  int x   0  x  lt  length    x                    for  int y   x   1  y  lt  length    y                        sum   input x    input y      will use it as inverse addition                     if  sum  lt  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

User · Answer

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

User · Answer

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

User · Answer

Very simple N 2 logN solution  sort the input array  then go through all pairs Ai  Aj  N 2 time   and for each pair check whether  S - Ai - Aj  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 Ai   1 for any i  V1 x    0 for all other x  V 2  Ai   Aj   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 Ai  for each Ai iterate through the array from right to left

User · Answer

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 lt Integer gt  A  int B        Collections sort A       int ansSum   0      int ans     new int 3       int minCloseness   Integer MAX VALUE      for  int i   0  i  lt  A size  -2  i             int j   i 1          int k   A size  -1          while  j  lt  k               int sum   A get i    A get j    A get k               if  sum  lt  B                   j                 else                  k--                            if  minCloseness  gt   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

User · Answer

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 lt  arr length-1   i         for  int j i 1  j lt  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   lt  sum           for  int k  j 1  k lt  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 lt Integer gt                    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

User · Answer

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  amp A  int B     sort A begin   A end      int k 0 i j closest val int diff INT MAX   while k lt A size  -2        i k 1      j A size  -1       while i lt j                val A i  A j  A k           if val  B  return B          if abs B-val  lt diff                        diff abs B-val               closest val                    if B gt val            i          if B lt val           --j              k     return closest

User · Answer

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   amp  amp   i  j   amp  amp   i  k   amp  amp   j  k   return  A i   A j   A k

User · Answer

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 lt Integer gt  stack   new Stack lt Integer gt              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  lt  endIndex  currentIndex                   if  sumInStack   data currentIndex   lt   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 lt Integer gt  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

User · Answer

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  lt  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  lt   end            mid    start   end   gt  gt  gt  1          if  elem  lt  array mid                 end   mid - 1            else if  elem  gt  array mid                 start   mid   1            else                 exact match case               Suits more for this particular case to return -1             return -1                      return mid

User · Answer

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  lt stdio h gt    int checkForSum  int arr    int len  int sum      arr is sorted     int i      for  i   0  i  lt  len   i              int left   i   1          int right   len - 1          while  right  gt  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  gt  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

User · Answer

Here is the Python3 code  class Solution      def threeSumClosest self  nums  List int   target  int  - gt  int          result   set           nums sort           L   len nums               for i in range L               if i  gt  0 and nums i     nums i-1                   continue             for j in range i 1 L                   if j  gt  i   1 and nums j     nums j-1                       continue                   l   j 1                 r   L -1                 while l  lt   r                      sum   nums i    nums j    nums l                      result add sum                      l   l   1                     while l lt  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    lt  abs target - min                   min   result i          return min

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

Examples related to arrays

Examples related to algorithm