Two Sum

Two Sum is the problem many coding interviews open with. It looks trivial, and a nested loop solves it in a minute. What the interviewer is really checking is whether you notice that the inner loop is a search, and whether you can replace it with a lookup.

It is also the cleanest example of the index-map shape. Every later problem in this section reuses its one idea: as you scan, keep a map of what is to your left, and ask the map instead of looking back.

The problem

You are given a list of integers numbers and an integer target. Exactly one pair of different positions i < j has numbers[i] + numbers[j] == target. Return [i, j].

• numbers = [2, 7, 11, 15], target = 9 → [0, 1], because 2 + 7 = 9.
• numbers = [4, 9, 6, 2, 11], target = 8 → [2, 3], because 6 + 2 = 8. Note that 4 + 4 is also 8, but there is only one 4, and you may not use one position twice.

Constraints: 2 ≤ n ≤ 10⁵, each value between −10⁹ and 10⁹, and exactly one valid answer.

Clarifying questions

• Can I use the same element twice? No — two different positions. But two equal values at different positions are fine: [3, 3] with target 6 gives [0, 1].
• Do you want indices or values? Indices, in the original array. This matters: sorting the array would lose them.
• Is the array sorted? Assume not. If it were, two pointers would solve it in O(1) extra space.
• Is there always an answer? Assume exactly one. If none is possible, return [].
• Can values be negative? Yes. That rules out tricks such as "stop once a value exceeds the target".

Approach 1: try every pair

The direct idea: for every position i, try every later position j, and return the first pair that sums to the target.

1def two_sum_brute(numbers: list[int], target: int) -> list[int]:2    """Try every pair i < j. O(n^2) time, O(1) space."""3    for i in range(len(numbers)):4        for j in range(i + 1, len(numbers)):5            if numbers[i] + numbers[j] == target:6                return [i, j]7    return []

Time: O(n²). Space: O(1).

With n = 10⁵ there are n(n − 1)/2, about 5 × 10⁹ pairs. Even a fast compiled language needs several seconds for that; Python needs minutes. The limit is usually one or two seconds. So this is correct but far too slow, and it is the answer you say first and then improve.

The key insight

Look at what the inner loop is doing. For a fixed i, it hunts for one specific value: target - numbers[i]. It is not comparing pairs in any clever way. It is searching.

Turn the question around and stand at the later element of the pair. When the scan reaches position j, the question is: "is the value target - numbers[j] somewhere to my left, and at which index?" That is a lookup, and a map from value to index answers it in O(1).

We do not need to build the map in advance. We can fill it while scanning. When we stand at j, the map holds exactly the values at positions 0 to j − 1. Every pair (i, j) is found at the moment we reach j, because i was stored earlier. So one pass is enough.

The order of the two steps is the whole correctness argument. We look up first, then insert the current value. At the moment of the lookup, the current element is not in the map yet, so it can never pair with itself. In the second example, at index 0 we look for another 4, the map is empty, and nothing is found — exactly right.

Approach 2: one pass with an index map

1. Create an empty map from value to index.
2. For each position index with value value, compute needed = target - value.
3. If needed is in the map, return [index_of[needed], index].
4. Otherwise store index_of[value] = index and move on.

1def two_sum(numbers: list[int], target: int) -> list[int]:2    """One pass: look for the partner among earlier values, then record this one."""3    index_of: dict[int, int] = {}              # value -> index where we saw it4    for index, value in enumerate(numbers):5        needed = target - value6        if needed in index_of:                 # check BEFORE inserting7            return [index_of[needed], index]8        index_of[value] = index9    return []

Dry run on numbers = [4, 9, 6, 2, 11], target = 8:

Row 0 is the one to notice. The needed value is 4, the same as the current value, and the lookup correctly fails because the current 4 has not been inserted yet. The answer appears at index 3, the later half of the pair, and index 11 is never read.

Time: O(n) on average — one pass, one lookup and at most one insert per element. Space: O(n) — in the worst case (answer at the very end) the map holds n − 1 entries. The worst-case time, if every key collided, would be O(n²), but that needs an adversarial input.

For a sense of scale: at n = 10⁵ this is about 100,000 lookups instead of 5 × 10⁹ comparisons. The map costs about 10 MB in Python. That trade is almost always worth taking.

Edge cases

• Equal values: [3, 3], target 6. At index 0 the map is empty; 3 is stored. At index 1, needed = 3 is found at index 0. Returns [0, 1]. No special case needed.
• A value that would pair with itself: [4, 1], target 8. The 4 never finds itself, because it is looked up before it is stored. Returns [].
• Negatives and zero: [0, 4, 3, 0], target 0 → [0, 3]; [-3, 5, 8, 1], target −2 → [0, 3]. Subtraction handles signs; nothing to change.
• Duplicates that are not the answer: the line index_of[value] = index overwrites an earlier index with a later one. That is safe. Because there is exactly one answer, no value that appears twice before its partner can be part of it.
• Overflow in other languages: in Java or C++, target - value can overflow a 32-bit int when values are near ±2³¹. Use a 64-bit type for needed. Python integers do not overflow.

Follow-ups

• The array is sorted (often called Two Sum II). Use two pointers from both ends: O(n) time and O(1) space, no map. The Two Pointers section covers it.
• Count all pairs that sum to the target, with duplicates. Switch from an index map to a frequency counter: for each value, add count_of[needed] to the answer, then increment count_of[value]. Still one pass.
• A data structure with add(number) and find(target). Store counts of the numbers. find loops over the distinct keys and checks each partner, so it is O(k) for k distinct values while add is O(1). If find is called far more often, precompute every pairwise sum on add instead — the trade flips.