Two Sum Solution

Given an array of integers and a target integer, return the indices of two numbers in the array such that they add up to the target.

Example:

Given numbers = [1, 4, 8, 13, 23] and target = 17,

Because numbers[1] + numbers[3] = 4 + 13 = 17,
return [1, 3].

Understand The Problem

The first step in problem-solving is to understand the problem.

When you read the problem statement, you might immediately have ideas how to solve it. Do not jump to conclusions and do not let your mind fool you. It’s best not to trust your instincts, and instead, you should go through systematic steps of analyzing the problem. Using a system will dramatically reduce the chance of a mistake.

Note: During the interview, make sure to ask questions before you start solving the problem! Interviewers often give a vague problem definition, and you have to fill in the details by asking questions.

Let’s look at the problem statement:

• Given an array of integers and a target integer, return the indices of two numbers in the array such that they add up to the target.

There is a lot to unpack in every problem statement. First, let’s look at the question overall and then highlight the key parts:

• Given an array of integers and a target integer, return the indices of two numbers in the array such that they add up to the target.
• The input is an array of ‘random’ integers and a ‘target’ integer.
• The output is the indices of two numbers.
  • This is crucial. You do not want to mix this up by returning the numbers instead.
  • The question doesn’t specify what to return. That’s something to discuss with the interviewer. You can propose various solutions like using a tuple, or a struct, or an array. Nevertheless, we can see that the example returns [1,3], so we will be using an array for the output.
• Finally, we see that we have to perform some algorithm that takes two numbers and checks whether they add up to the target.

From this information we can form a basic idea of how the function will look like:

function twoSum(numbers, target) {
  return [index1, index2];
};

At this point, we have no idea how to solve anything. However, we do know the input, we do know the output, and we have a basic sense of the algorithm. Let’s dive a little more into the details before we try coming up with a solution…

Let’s analyze the input.

First, analyze the array part of array of integers:

• Could the array be empty?
  • No.
• Can I expect the array to be at least 2 integers?
  • Yes.
• Is it sorted?
  • No.
• Could there be duplicate values?
  • Yes.

Note: Notice how simple these questions are. Yet they are so crucial. ANY change in the answers can mean the difference between solving the algorithm and getting it wrong.

Then, analyze the integer part of array of integers:

• Could the integers be negative?
  • Yes.
• Could there be zero’s?
  • Yes.
• Could there be positives?
  • Yes.

Then, lets analyze the target integer:

• Could the target be negative?
  • Yes.
• Could the target be 0?
  • Yes.
• Could the target be positive?
  • Yes.
• Could the target match one of the values in the array?
  • Yes.

Note: Some of these details may seem pointless. However, many questions are tricky: the solutions, or bugs, often lay between the little details. Examine every aspect of the question because you can’t discern the critical parts until you know the solution. View this process as a way to feed your brain information; hopefully, something will spark an insight that will lead to the solution.

Let’s analyze the output (array of integers).

• It’s an array, so it could be empty, or have 1 number, 2 numbers, 3 numbers, etc. An array of numbers could even contain negative numbers!
• However, as we figured out above, there will always be a solution, so we will always return an array of two numbers.
  • This is an important point because it means that we do not have to worry about handling special cases.
• We then can also notice that the values in the array must be >= 0 because they represent the array indices.
• In summary, the output is an array of two integers, where both are >= 0 && < array.length.

Other questions to consider:

• Do we have to worry about overflow when adding two integers?
  • No.
• Can there be multiple answers?
  • Yes.
  • What to do about them?
    • Return any pair from the set of answers.

We now have a basic understanding of the problem. Let’s try to come up with a solution.

Note: There’s always a chance you miss something – even after carefully examining each detail. Don’t worry. It’s natural. However, you should treat every mistake as an opportunity to improve. Why did you make a mistake? Can you improve your problem-solving system to ensure that you don’t make the same mistake again? That’s the whole point of learning: identify weaknesses, improve your system, and repeat. Iterate, iterate, iterate.

Coming Up With The Solution

Each algorithm problem is different. There is no single approach that will help you solve every problem. However, I recommend to start by creating examples and walking through them.

Let’s start by creating examples:

• Example 1
  • numbers = [1, 2]
  • target = 3
  • Why this example?
    • This input is nice because it’s simple. If you are struggling to come up with a solution, choosing the simplest possible input can get you going.
• Example 2
  • numbers = [2,9,1,5,6,3]
  • target = 4
  • Why this example?
    • This input is nice because it is a randomized.
    • We can also see that the answer ([1,3]) is spread apart, which means we have to go through a lot of the input before we will find the answer.
• Example 3
  • numbers = [1,2,3,4,5,6,7,8,9]
  • target = 18
  • Why this example?
    • It’s a sorted array instead of a randomized one.
    • There is no answer to this example: no two numbers add up to 18.
    • However, we don’t have to worry about this example because I said we can assume that there will always be an answer!

Note: The number of examples you can go through during the interview will be limited. If you have infinite time, it’s best to try a lot of examples where each examines a specific edge-case. However, you don’t have infinite time in an interview, so you have to strike the balance between speed and accuracy.

As a result of not having a lot of time, let’s pick an example that seems to cover various edge-cases:

• numbers = [-3,0,1,5,1,3]
• target = 4

This example is nice because:

• There is an answer.
• It covers various edge-cases: zeroes, negative numbers, random sorting.
• It’s not too small.
  • We want the example to be complex enough where it will thorougly test our algorithm.
• It’s not too large.
  • The larger the example, the harder it is for us to “load” this example into our brain and understand it.

After spending some time thinking about the problem, we can make two quick observations:

• We need to find two indices in the numbers array. That means we will have to loop through the array to search for numbers.
• The numbers could be anywhere in the array (maybe the start, maybe the end), so in the worst case, we will have to go through the whole array. That makes this algorithm at least O(N).

With the observations in mind, let’s take the example [-3,0,1,5,1,3] and start thinking about how we can go through the array:

• We need to start somewhere, so let’s start at index 0, which gives us the number 3.
• We have one number, but we need two. Lets keep going through the array trying each one:
  • If we try numbers[1] == -3, 3 + 0 = -3; -3 != 4
  • If we try numbers[2] == 1, 3 + 1 = -2; -2 != 4
  • If we try numbers[3] == 5, 3 + 5 = 2; 2 != 4
  • If we keep going, we will see that we can’t find another number that, combined with 3, adds up to the target 4.
• We have exhausted all possibilities from index 0, which means we have to move to index 1 and repeat this process.
• Eventually, we find that numbers[2] + numbers[5] == 4.

From this simple exercise, we have already derived an algorithm:

• Start at index 0 for the first number
• Then, try all other indices to see whether the first number adds up to the second number.
  • If they do…return the two indices.
  • If they do not…increment the index of the first number and repeat…

Here is the algorithm written down:

def twoSum(numbers, target):
    for index1 in range(len(numbers)):
        for index2 in range(index1 + 1, len(numbers)):
            if numbers[index1] + numbers[index2] == target:
                return [index1, index2]

Note:This process may sound simplistic to you, but there is a powerful lesson here. You can make a simple observation like “I need two numbers from an array,” and begin by doing the most straightforward thing possible: begin at index 0. Then, let the algorithm evolve from there.I can credit this method to helping me pass the Google hiring committee. I had a question in front of me, and I was frozen. It seemed simple, but I was nervous, and I had no insights. So…I just started. I began with simple premises and went through an example, step-by-step. The process gave me ideas that helped me finish the algorithm on time.

If you are familiar with time complexity analysis, you can see that the algorithm can be solved in O(N^2). From this information, we can make further observations:

• To do better, we can solve this in:
  • O(N*log(N)) or O(N) or O(log(N))
  • Not all algorithms fit neatly into these time-complexity buckets, but a lot of them do – especially in interviews. As a result, making this type of analysis is helpful to keep moving toward a solution.

Let’s consider each time-complexity and create more insights:

• O(N*log(N)) algorithm can mean that there is sorting involved, can we sort this?
  • Another possibility is using a heap, but usually a heap is related to finding the min or the max.
• O(N) algorithm means we need to do this in one pass.
  • To achieve O(N) we need O(1) operations.
  • There are various data structures with O(1) operations: a set and a hashtable.
• O(log(N)) alogrithm usually means doing a binary search.
  • However, we observed earlier that we need to visit every number in the array. So this will probably not work unless we made the wrong observations, which is always possible!

Note: Notice how we can utilize prior knowledge of time-complexity, algorithms, and data structures to generate ideas of how to solve the problem. Make sure to study the Terminology!Note: Whether the observations are relevant to the question doesn’t matter at first. You can’t judge whether an observation is useful because you don’t know the answer yet! Don’t assume whether something will work or will not work. Instead, let your brain see all the possibilities.

Let’s use the O(N*log(N)) observation. We have an array of numbers, so sorting seems like a good option to try.

When we sort the array we get: [-3,0,1,1,3,5].

Cool. We sorted the array, but what does that give us?

We formed a new property for the input: the numbers are ordered from small-to-large. Can we somehow exploit this property?

• Let’s begin by repeating what we did above: start at index 0.
  • numbers[0] + numbers[1] == -3 + 0 = -3; -3 != 4
  • numbers[0] + numbers[2] == -3 + 1 = -2; -2 != 4
  • numbers[0] + numbers[3] == -3 + 1 = -2; -2 != 4
  • numbers[0] + numbers[4] == -3 + 3 = 0; 0 != 4
  • numbers[0] + numbers[5] == -3 + 5 = 2; 2 != 4
• While we didn’t find an answer, we did find a pattern:
  • 3 + 0 = -3
  • 3 + 1 = -2
  • 3 + 1 = -2
  • 3 + 3 = 0
  • 3 + 5 = 2
• Let’s clarify some of the things we are noticing:
  • Every time we increment the second index the sum will increase.
  • If we start at index 0, the highest sum we can achieve is 2. That means that we only have to look at at the first number (index[0]) and the last number (index[5]) to figure out how close we are to the target (4). If index[0] + index[5] < target that means that there is NO way that index[0] will ever add up to the target: the sum will always be too small. On the other hand, if index[0] + index[5] > target there is NO way that index[5] can be used to add up to the target: the sum will always be too large. In other words, we only need to compare two numbers to go through the array.

Let’s recap:

1. By starting at index 0 and listing all the possibilities, we found a pattern.
2. Then, by analyzing the pattern, we realized that we only need to compare the first and the last number to find the target.

Note: Leaping to this conclusion is not always straightforward. However, with a lot of practice, and by using the “start at index 0” tactic, you will be able to find these types of insights.

These observations give us an O(N*log(N)) algorithm:

def twoSum(numbers, target):
    def comparisonFunction(number1, number2):
        if number1 <= number2:
            return -1
        elif number1 > number2:
            return 1
        else:
            return 0
    
    numbers.sort(key=comparisonFunction)
    firstIndex = 0
    lastIndex = len(numbers) - 1

    while firstIndex < lastIndex:
        _sum = numbers[firstIndex] + numbers[lastIndex]
        if _sum == target:
            return [firstIndex, lastIndex]
        elif _sum > target:
            lastIndex -= 1
        else:
            firstIndex += 1

# Example usage
numbers = [2, 7, 11, 15]
target = 9
result = twoSum(numbers, target)
print(result)  # This will output [0, 1]

However, this is the wrong answer!

The question requires us to return the indices of the numbers. We sorted the numbers, which changed the original indices!

If the question asked us to return two numbers that add up to target, or asked us to return whether there exist two numbers that add up to the target, this approach would be perfectly fine. That being said, it is still possible to solve the question using this method; you will just have to map the original indices to the sorted indices.

A mistake such as this is a great lesson! You can now put this observation in your bag of tools: “If the question requires the original order, then sorting, which changes the order, might not be the optimal solution.”

Can we do better than O(N*log(N))? Yes.

Let’s go for O(N) time complexity:

• O(N) means we need O(1) operations.
• As a thought experiment, what if we place the whole array into a Set?
  • This will cost O(N) space. It’s a common optimization tactic to trade space for speed.
  • If all the numbers are in a Set, we can find ANY of them in O(1) time.

Let’s write down what we have if we put numbers in a Set:

• numbers = [-3,0,1,5,1,3]
• target = 4
• numberSet = (-3,0,1,5,3)

There are a few possible next steps:

• Sometimes, a solution will immediately pop in your head. This is the best-case scenario. It means that you are familiar with the concepts of the question because of your dedicated practice!
• Other times, you will have no idea how to proceed next. This can cause panic during an interview.
  • Luckily, you now know what to do: start at index 0.

By starting at index 0, we have the following variables:

• numbers = [-3,0,1,5,1,3]
• target = 4
• numberSet = (-3,0,1,5,3)
• numberOne = numbers[0] == -3

How can you utilize these 4 variables?

• Checking whether numberOne is in the numberSet doesn’t give us anything.
• Checking whether target exists in the set also doesn’t give us much because we are looking for TWO numbers that add up to the target — not one.
• Let’s formalize “two numbers that add up to the target” by writing an equation: numberOne + numberTwo = target
• We have numberOne and we have target so: numberTwo = target - numberOne
• In other words, given numberOne and target, we can figure out what number we need to find in the array. The numberSet gives us the ability to find a number in O(1) time.

We have the basis for a solution: go through the array and keep checking whether numberOne - target is within the set. If it is, we found a pair of numbers that add up to the target.

Nevertheless, there are still two issues:

1. We need to return the indices of the two numbers, and currently, we are storing only numbers in the set.
2. We need to avoid an edge-case with duplicate numbers. For example, if the target is 4 and we have the number 2 in the array, we don’t want to reuse the same number 2 for the solution.

Fixing #1 is straighforward. We can use a hashtable to store a mapping of each number to the index.

Fixing #2 is less obvious, but we can avoid checking for the same number in the hashtable by checking the hashtable before updating it with the new number.

This gives us the following pseudocode:

def twoSum(numbers, target):
    hashtable = {}  # Create an empty dictionary

    for i in range(len(numbers)):
        numberOne = numbers[i]
        if target - numberOne in hashtable:
            return [hashtable[target - numberOne], i]
        else:
            hashtable[numberOne] = i

# Example usage
numbers = [2, 7, 11, 15]
target = 9
result = twoSum(numbers, target)
print(result)  # This will output [0, 1]

Note: You might be still questioning whether you would have arrived at these same insights during the interview. I feel you. It will take a lot of practice, but there is a way to increase the chance that you discover these insights – and that is by starting at index 0 and systematically breaking down the question to its core parts.

Writing The Solution

If you worked through an example and wrote pseudocode, “Writing The Solution” should be mostly straightforward.

One of the biggest problems in this phase is small errors. You can avoid them by regularly performing sanity-checks.

For example:

• Did I use every variable?
• Did I increment the counter?

Final code for the solution:

def twoSum(numbers, target):
    hashtable = {}  # Create an empty dictionary

    for i in range(len(numbers)):
        numberOne = numbers[i]
        numberTwo = target - numberOne
        if numberTwo in hashtable:
            return [hashtable[numberTwo], i]
        else:
            hashtable[numberOne] = i

# Example usage
numbers = [2, 7, 11, 15]
target = 9
result = twoSum(numbers, target)
print(result)  # This will output [0, 1]

Note: Take a moment to recognize the shortness of this section. Writing the final code on the whiteboard is the end-goal, yet we spend the least amount of time here. It displays the importance of really thinking through the solution before writing it.

Testing / Reflection

During an interview, if you have the time, you want to test your code by walking through it step-by-step. It’s not uncommon to make a silly mistake.

During practice, you want to reflect on how the solving process went by asking various questions:

• What is the time complexity?
  • O(N)
• What is the space complexity?
  • O(N)
• What are some interesting observations from this problem?
  • The brute-force O(N^2) solution is very common. We compared every number to the other numbers – exhausting the search space.
  • Sorting the numbers gave the problem a unique property: we only need to check the first and last numbers to figure out how to proceed through the array. This reduced time complexity to O(N*log(N)).
  • Using a dictionary is a classic tactic of trading space for time. The dictionary O(1) access allowed us to improve the solution to O(N).
  • If the input was already sorted, we wouldn’t need to use the dictionary. We could immediately use the “compare first and last numbers trick.”
  • We first tried to solve the problem in ANY way possible (start at index 0). Then, we took the first solution we found and tried to reduce the time complexity. We can apply this method to any problem we are struggling with!
• What are some related problems?
  • There are other variations of this problem like 3sum and 4sum.

Reflection is a great step that allows us to “chunk” the learnings from the problem by connecting it to existing ideas.

What else can you think of? Send feedback!

P.S. you can try it @ https://leetcode.com/problems/two-sum/