algorithm - Find 2 numbers in an unsorted array equal to a given sum

Question

We need to find pair of numbers in an array whose sum is equal to a given value.

A = {6,4,5,7,9,1,2}

Sum = 10 Then the pairs are - {6,4} , {9,1}

I have two solutions for this .

• an O(nlogn) solution - sort + check sum with 2 iterators (beginning and end).
• an O(n) solution - hashing the array. Then checking if sum-hash[i] exists in the hash table or not.

But , the problem is that although the second solution is O(n) time , but uses O(n) space as well.

So , I was wondering if we could do it in O(n) time and O(1) space. And this is NOT homework!

Answer 1

Use in-place radix sort and OP's first solution with 2 iterators, coming towards each other.

If numbers in the array are not some sort of multi-precision numbers and are, for example, 32-bit integers, you can sort them in 2*32 passes using practically no additional space (1 bit per pass). Or 2*8 passes and 16 integer counters (4 bits per pass).

---

Details for the 2 iterators solution:

First iterator initially points to first element of the sorted array and advances forward. Second iterator initially points to last element of the array and advances backward.

If sum of elements, referenced by iterators, is less than the required value, advance first iterator. If it is greater than the required value, advance second iterator. If it is equal to the required value, success.

Only one pass is needed, so time complexity is O(n). Space complexity is O(1). If radix sort is used, complexities of the whole algorithm are the same.

---

If you are interested in related problems (with sum of more than 2 numbers), see "Sum-subset with a fixed subset size" and "Finding three elements in an array whose sum is closest to an given number".