How Do You Solve Two Sum in Python?

Two Sum gives you a list of numbers and a target, and it asks for the indices of the two values that add up to that target. The brute-force answer tries every possible pair and costs O(n squared) time. The better answer keeps a dictionary of the values it has already seen, and it costs O(n) time. The earlier questions in this topic covered lists and dictionaries, and this problem puts both of them to work.

The reasoning behind the dictionary version is the part that you should explain rather than only showing the code. For each value that you look at, you can work out the value that would complete the pair, which is the target minus the current value. If that complement has already been seen, then you have found the pair, and the dictionary hands you its index directly. Otherwise you record the current value and its index, and you move on to the next one. Each step of that is a single hash lookup, so the whole pass is linear.

Two small details make the difference between a correct answer and a subtly wrong one. The lookup happens before the insert, so an element is never paired with itself, because the target 4 against the single value 4 would otherwise wrongly succeed. And you store the index rather than the value, because the question asks for indices and not for the numbers themselves.

When duplicates exist, the dictionary approach naturally returns the first valid pair, which is what people usually expect. If the interviewer wants every possible pair instead, that is a different problem, and the same two-sum idea still works as a starting point for it.

It is worth writing the brute-force version once, so that you can talk about why it is not the answer that you want to ship. The first question in this page explained the better approach, and this one shows the version that comes before it.

def two_sum_bruteforce(numbers, target):
    """Return the indices of two values that add up to target, or None."""
    for first in range(len(numbers)):
        for second in range(first + 1, len(numbers)):
            if numbers[first] + numbers[second] == target:
                return (first, second)
    return None


print(two_sum_bruteforce([2, 7, 11, 15], 9))   # (0, 1)
print(two_sum_bruteforce([3, 2, 4], 6))         # (1, 2)
print(two_sum_bruteforce([1, 2], 9))           # None

The second example is the interesting one. The pair that adds up to six is 2 and 4, and they sit at indices 1 and 2, which are not the first two elements of the list. A solution that assumes the answer is at the front would fail on exactly this case.

The inner loop starts at first + 1 and not at zero, and that has two effects. It stops an element from being paired with itself, and it stops each pair from being checked twice, because the pair (0, 1) and the pair (1, 0) are really the same pair.

The complexity is the reason that this version is not the final answer. There are about n times n pairs of indices to test, so the time is O(n squared) and the extra space is O(1). For a list of a hundred thousand numbers that is billions of comparisons. The dictionary version does the same job in a single pass, and knowing why it is faster, which is that you are trading space for time by remembering what you have already seen, is the real content of the question.

This is the version to write when you are asked for an efficient solution. The earlier two questions in this page covered the approach and the slow version, and this one is the answer you want to end up with.

def two_sum(numbers, target):
    """Return the indices of two values that add up to target, or None."""
    seen = {}
    for index, value in enumerate(numbers):
        complement = target - value
        if complement in seen:
            return (seen[complement], index)
        seen[value] = index
    return None


print(two_sum([2, 7, 11, 15], 9))   # (0, 1)
print(two_sum([3, 2, 4], 6))         # (1, 2)
print(two_sum([1, 2], 9))           # None
print(two_sum([3, 3], 6))           # (0, 1)

For each value, the function works out the complement that it would need, checks whether that complement has already been seen, and then either returns the pair of indices or records the current value and its index so that it can be used later. The final example confirms that the duplicate case works, because two threes give the pair 0 and 1.

The order inside the loop is the detail that makes the function correct. The lookup comes before the insert, so the current element can never be matched against itself. Without that ordering, two_sum([4], 8) would wrongly report a pair.

The complexity is O(n) time, because each iteration performs a constant number of dictionary operations, and a dictionary operation is O(1) on average. The extra space is O(n) for the dictionary of values that have been seen. The brute-force version costs O(n squared) time with no extra space at all, so the trade here is space for speed.

If you want every pair instead of only the first one, you can build the same dictionary first and then check every key against its complement, which is still linear work. That is the natural follow-up question, so it is worth having the extension ready in your head.