Find the pair of numbers in an unsorted array with a sum closest to an arbitrary target

Question

This is a generalization of the 2Sum problem

Given an unsorted array of numbers, how do you find the pair of numbers with a sum closest to an arbitrary target. Note that an exact match may not exist, so the O(n) hashtable solution doesn't fit here.

I can solve the problem in O(n*log(n)) time for a target of 0 as so:

1. Sort the numbers by absolute value.

2. Iterate across the sorted array, keeping the minimum of the sums of adjacent values.

This works because the three cases of pairs (+/+, +/-, -/-) are all handled by the logic of absolute value. That is, the sum of pairs of the same sign is minimized when they are closest to 0, and the sum of pairs of different sign is minimized when the components of the pair are closest to each other. Both of these cases are represented when sorting by absolute value.

How can I generalize this to an arbitrary target sum?

Answer 1

If you are going to sort the numbers anyway, your algorithm already will have a complexity of at least O(n*log(n)). So here is what you can do: for each number v you can perform a binary search to find the least number u in the array that gets the sum u + v more than target. Now check u + v and u + t where t is the predecessor of v in the sorted array.

The complexity of this is n times the complexity of binary search i.e. O(n * log (n)) thus your overall complexity remains O(n*log(n)). Also this solution is way easier to implement than what you suggest.

As pointed out by amit in a comment to the question you can do the second phase with linear complexity, improving its speed. Still the overall computational complexity will remain the same and it is a little bit harder to implement the solution.

Answer 2

Step 1: Sort the array in non-decreasing order. Complexity: O( n lg n )

Step 2: Scan inwards from both ends. Complexity: O( n )

On the sorted array A, let l point to the left-most (i.e. minimum) element and r point to the right-most (i.e. maximum) element.

 while true:
   curSum = A[ l ] + A[ r ]
   diff = currSum - target
   if( diff > 0 ):
      r = r - 1
   else:
      l = l + 1

If ever diff == 0, then you got a perfect match for 2Sum.

Otherwise, look for change of sign in diff, i.e. transition from positive to negative, or negative to positive. Whenever the transition happens, either just before or just after the change, currSum is closest to target.

Overall Complexity: O( n log n ) because of step 1.