Two Sum

Two Sum is the most famous warm-up in coding interviews. It teaches the single most useful trick in the whole field: trading memory for speed with a hash map.

The slow way first

The obvious idea: try every pair. For each number, loop over all the others and check if they add up to the target. That works, but it is O(n²) — for a big array it is far too slow.

The question to ask: while I am looking at one number, what do I wish I already knew? I wish I knew whether its partner (the number that completes the target) has already shown up. A hash map lets me answer that in O(1).

The idea: remember what you've seen

Walk the array once. For each number num, its partner is need = target - num. Before storing num, check: have I already seen need? If yes, the pair is num and that earlier number — done. If no, remember num (store its value → index) and keep going.

The key insight: we check for the partner before adding the current number. That way we never pair a number with itself, and the first complete pair we find is the answer.

Walk through it

Step through the animation. The pointer i scans left to right. The seen map fills up underneath. When i reaches 4, its partner 2 is already in the map (we stored it a step earlier), so we stop and return both indices.

Pseudocode

make an empty map called "seen"     # maps a value -> its index
for each index i with value num in nums:
    need = target - num
    if need is a key in seen:
        return [seen[need], i]        # found the pair
    seen[num] = i                     # remember this number for later
return []                             # (problem guarantees we never reach here)

The Python solution

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

• seen is a dictionary mapping a value → the index where we saw it.
• enumerate gives us both the index i and the value num as we loop.
• need = target - num is the partner we are hoping to find.
• Line 5 is the O(1) lookup — the heart of the trick. need in seen checks a hash map, not the whole array.
• We store seen[num] = i after the check, so a number is never matched with itself.

Complexity

We trade O(n) extra space (the map) for a big speed win: O(n²) → O(n). That trade — use a hash map to remember things and look them up instantly — shows up in a huge number of problems.

When this pattern shows up

Practice