find pair of numbers in array that add to given sum

Question

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?

Answer 1

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.