arraysperformancealgorithmprocessing-efficiency

find pair of numbers in array that add to given sum

Question: Given an unsorted array of positive integers, is it possible to find a pair of integers from that array that sum up to a given sum?

Constraints: This should be done in O(n) and in-place (without any external storage like arrays, hash-maps) (you can use extra variables/pointers)

If this is not possible, can there be a proof given for the same?

Solution

  • If you have a sorted array you can find such a pair in O(n) by moving two pointers toward the middle

    i = 0
j = n-1
while(i < j){
   if      (a[i] + a[j] == target) return (i, j);
   else if (a[i] + a[j] <  target) i += 1;
   else if (a[i] + a[j] >  target) j -= 1;
}
return NOT_FOUND;

    The sorting can be made O(N) if you have a bound on the size of the numbers (or if the the array is already sorted in the first place). Even then, a log n factor is really small and I don't want to bother to shave it off.

    proof:

    If there is a solution (i*, j*), suppose, without loss of generality, that i reaches i* before j reaches j*. Since for all j' between j* and j we know that a[j'] > a[j*] we can extrapolate that a[i] + a[j'] > a[i*] + a[j*] = target and, therefore, that all the following steps of the algorithm will cause j to decrease until it reaches j* (or an equal value) without giving i a chance to advance forward and "miss" the solution.

    The interpretation in the other direction is similar.