Find two numbers in an array whose sum =X

Find if the sum of two elements in an array sum up to b (a number) with complexity of O(n)?

Input – Array : 1,2,3,4,5,6,7,8 and the sum is : 6

Output would be : {1,5} {2,4}

Solution : Here is the idea is to start from the first element of the array and keep a hashtable to store the potential pairs. We will check if sum – (a[i]) already exists in the Hashtable. If yes, we have a pair (a[i], value from hashtable) as the pair with the sum. If no, we store a[i] in the hashtable.

Here is a little dry run of array a= {1,2,3,4,5,6,7,8} and sum = 6.

6 – 1 = 5 — found in Hashtable H ? No – store it in H. H will contain (1)

6 –2 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2)

6 –3 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2, 3)

6 –4 = 2 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (4,2)

6 –5 = 1 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (5,1)

Why Hashtable ? because the lookup is always O(1) in a hashtable.