Coding Interview —Two Sum Problem

The two sum problem is a common interview question, and it is a variation of the subset sum problem. There is a popular dynamic programming solution for the subset sum problem, but for the two sum problem we can actually write an algorithm that runs in O(n) time.

Prompt

The challenge is to find all the pairs of two integers in an unsorted array that sum up to a given S.

For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.

Naive Solution

A naive approach to this problem would be to loop through each number and then loop again through the array looking for a pair that sums to S. The running time for the below solution would be O(n²) because in the worst case we are looping through the array twice to find a pair.

Faster Solution

We can write a faster algorithm that will find pairs that sum to S in linear time. The algorithm below makes use of hash tables which have a constant lookup time.

As we pass through each element in the array, we check to see if S minus the current element exists in the hash table. We only need to loop through the array once, resulting in a running time of O(n) since each lookup and insertion in a hash table is O(1).

Example

If the array is: [4, 5, 1, 8] and the sum is 6 the algorithm would proceed with the steps below:

(1) The hash table is initially empty and the first element in the array is 4. We simply put 4 into the hash table. 
(2) The next element is 5. We check to see if the sum minus the current element exists in the hash table. 6–5 = 1 does not exist in the hash table. So add 5 to the hash table. 
(3) The next element is 1. We check to see if the sum minus the current element exists in the hash table. 6–1 = 5 does exist in the hash table so we found a pair!

If you are interested in data engineering, check out the course below.