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!
See Question&Answers more detail:os