Two Sum (2sum) Solved - Leetcode Top Question Solutions #1

The problem - Leetcode #1

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Quick Recap

This question is asking us to take as input an array of integers, nums, and a target integer T. We then want to see if any two numbers in the array add up to T, if so, we’ll return their indices (not the numbers themselves). In the leetcode problem, we are given that there’s exactly one solution, this allows us not to worry about:

What to do if there isn’t a solution.
Which solution to return if there are many solutions.

In an interview, we’ll want to be able to solve this problem with a brute force method, as well as other more efficient methods and discuss the pros and cons of each. Thinking of multiple ways to solve a problem and giving the pros and cons of each is key to getting really good marks on the coding interview.

The Brute Force Solution

The first thing we should do is find a brute force solution. The problem asks us to see if any pair of integers in the array adds up to T, so a brute force method would be to simply generate all pairs of indices and see if any correspond to two numbers that add up T.

For example, if we had as our input:

nums = [4,8,12,16] and T = 28

We’d generate all pairs of indices, e.g.:

(0,1), (0,2), (0,3), (1,2), (1,3), (2,3) (Note that we don’t need to generate: e.g. [1,0] because [0,1] is the same pair of numbers or [1,1] because we aren’t allowed to use the same number twice).

Once we generate all pairs of indices, we’d loop through each pair and check if any of the numbers indexed by the values in the pair add up to T, if so, we’d return the pair.

So, for the example above, we’d try:

pair: (0,1) -> nums[0] + nums[1] -> 4 + 8 = 12 != T

pair: (0,2) -> nums[0] + nums[2] -> 4 + 12 = 16 != T

pair: (0,3) -> nums[0] + nums[3] -> 4 + 16 = 20 != T

pair: (1,2) -> nums[1] + nums[2] -> 8 + 12 = 20 != T

pair: (1,3) -> nums[1] + nums[3] -> 8 + 16 = 24 != T

pair: (2,3) -> nums[2] + nums[3] -> 12 + 16 = 28 == T

Once we see that nums[2] + nums[3] == T, we return 2,3.

The code for this might look like (in python):

# Generates all distinct pairs of possible indices for an array of length n.
# n - An integer
def generateAllPairsOfIndices(n):
    for i in range(n)
        for j in range(i+1, n)
            yield [i,j]

# Nums
def twoSum(nums, T)
    for pair in generateAllPairsOfIndices(len(nums)):
        if nums[pair[0]] + nums[pair[1]] == T:
            return pair

Usually, since this is so simple, we’d probably just inline the generateAllPairsOfIndices:

def twoSum(nums, T)
    for i in range(len(T)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == T:
                return [i, j]

Whenever we come up with an algorithm, especially during a coding interview, we’ll want to analyze it’s time and space complexity.

What’s the time complexity of this solution?

The double nested for loop:

for i in range(len(nums)):
    for j in range(i+1, len(T)):

is a classic O(n^2) pattern. If we let n = len(T), the second for loop runs: n - 1 times then n - 2 times then n - 3 times … 1 time

Using the fact that n + (n - 1) + (n - 2) + (n - 3) = n(n-1)/2 = (n^2 - n) / 2 = O(n^2) we can conclude that this is O(n^2)

For space complexity, we can simply note that we only generate one pair at a time to prove that we use only O(1) extra space.

Removing Unnecessary work

To find a solution that’s faster than O(n^2), we can start by looking for unnecessary work in our first solution.

If we look at the solution, we see that we’re basically ‘setting’ the first number, and then using the second loop to ‘search’ for a second number so that first_number + second_number = T is satisfied.

We can rearrange the equation to get: second_number = T - first_number

With that rearrangement, we can see that our inner loop is only being used to search indices i+1 to n (the end of the array) for a value of T - nums[i].

Whenever we want to ‘search’ or ‘lookup’ a value quickly, we should consider using a hash table (because of its O(1) amortized lookup cost) in the rest of the array.

We could hash the whole array, but then we wouldn’t be able to look at only values from i+1 to n and we might end up using the same number twice (Consider an example, nums = [2,3] with T = 4. If we first build a hash table and then loop through each value searching for T - value, we’d set num1 = 2 and then we’d search for 4-2 = 2 in the hash table, we’d find it in our hash table and erroneously return the same index twice (in this case [0,0]).

To solve the problem, we can build a hash table as we go:

val_to_index = {}
for i in range(len(nums), -1, 0):
    if (T - nums[i] in val_to_index):
        return [i, val_to_index[T-nums[i]]]

Since the problem is symmetrical, we could just do this same thing going from the front of the array as well. Using this idea to make our code slightly easier to understand:

value_to_index = {}
for i in range(len(nums)):
    if (T - nums[i] in val_to_index):
        return [i, val_to_index[T-nums[i]]]

How much time does this solution take?

We have one loop and then inside a O(1) insert and a O(1) lookup. So we have O(n) time.

How much space?

The hash table uses O(n) space.

Takeaways

In the end, we came up with two solutions:

	Space	Time
nested for loop	O(1)	O(n^2)
hash table	O(n)	O(n)

It’s important to:

Try to give multiple different solutions and analyze them all.
Try solutions involving hash tables when you have to do lookups because of the O(1) amortized search time (BSTs are another good idea).