Two Sum

The problem description can be found in LeetCode.

Approach

A brute force approach would consist of generating all possible pairs in the input list and calculate the sum. This would require $O(n^2)$ time and $O(1)$ space. The code would look something like this:

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                curr_sum = nums[i] + nums[j]
                if curr_sum == target:
                    return [i, j]

        raise Exception("expected one solution")

Of course, we can do better in term of time. For sure, we have to iterate until the end of the list, but then we need an auxiliary data structure to use to memorize something.

We could store the complement of the i-th number and then look for it the next iteration. If the i-th number is already in our collection, then it means that we found the other addend.

For a quick look-up table, we can use a Python dictionary.

Let's take an example:

nums = [1, 2, 10]
target = 3

Initially, our dictionary will be empty. The first number to check is 1, which means that our complement is 2 (target - current num). So our dictionary will be the following after the first iteration:

d = {
    2: 0,
}

Where the key is the complement, and the value is the index (remember that we have to return the index of the two numbers).

Then, in the second iteration, we can see that number 2 is already in the dictionary, which means that we found the second addend. Hence, we can return the index in the dictionary entry and the current one.

Solution

from typing import Dict, List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        comps: Dict[int, int] = {}

        for i, num in enumerate(nums):
            if num in comps:
                return [comps[num], i]

            comp = target - num
            comps[comp] = i

        raise Exception("expected one solution")

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the list nums.