Two Sum | Interview Question

People, particularly engineers, are intrigued by technical interview questions. I don’t blame you, these are fascinating and are a good intermediate point to discuss extraordinary solutions. In this post, I’ll show you how to solve the Two Sum problem, a popular coding interview question, using Python.

The Two Sum problem is stated as the following:

Suppose we have an array of integers. We have to return the indices of two integers, such that their sum will reach a specific given target.

How do we solve it, then? There are different approaches, all of them with their own flaws and advantages. The method I’ll show you utilizes dynamic programming, which I will probably cover in a follow-up post.

Let’s begin with our case scenario. First, the list of integers numbers.

numbers = [5, 3, 6, 10, 4, 9]

We need to find two numbers of the list that add up to a given number, in this case target , which is given.

target = 11

Two Sum, Two For Loops

By looking at the statement and what’s given, it’s easy to determine the two numbers are 5 and 6. But how do we find them with the least number of iterations? We could try getting the first number, 5, and then iterating through the rest of the list until we find the second number that adds up to 11. Easy right? Well yes, but inefficient. Let me show with some code:

The code above solves the problem, but it takes two iterations or loops to find the right answer. The Two For Loops approach yields a time complexity of O(n²). This is where dynamic programming comes in. Let’s take another path. Instead of finding the sum, we can do exactly the opposite: find the difference between the target and each number in numbers.

Dynamic Approach. Don’t sum, subtract

The idea is the following: we get the first number of the list, 5, then we find the difference between 11 and 5, resulting in 6 which is the third number in the list! As easy as it sounds, we have 90% of the solution. The next step is to save that difference so that when the iteration gives 6 it returns 5’s index, which is the first and previous number, along with 6’s index as the answer.

For this we will use a dictionary. We can save the difference, 6, which we know is the second answer, as the key, and the index, i, which corresponds to 5, as the value. Thus, we know the number to look for in the following iterations and we have the index of the first answer. In conclusion, all that’s left is finding the next number!

To accomplish this solution, we need to create an empty dictionary before the for loop, which I will name differences .

differences = {}

Next, run the for loop iterating through each index in numbers .

differences = {}
for i in range(len(numbers)):

The first thing we’ll do is checking if the number, in this case 5, is in differences .

differences = {}
for i in range(len(numbers)):
    number = numbers[i]
    if number in differences:
        return differences[number],i

If it is, voilà, we have the answer. Otherwise, we’ll be a step closer to what we are looking for; we’ll save target-number (i.e. 11 - 5 = 6) as key and 5’s index, i , as value (i.e. {6:1} ).

differences = {}
for i in range(len(numbers)):
    number = numbers[i]
    if number in differences:
        return differences[number],i
    differences[target-number] = i

When 6 comes up, the if statement will trigger and return 6’s value in differences, 1, which is 5's index, and the current index, i , which corresponds to 6. The function get_index shows how it looks.

Now you can feel confident on how to solve and explain the solution during your technical interview.