Hash the complement

43 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You are given the numbers 2, 7, 11, 15 and asked which two of them add up to 9. By hand you would pick the first number, 2, and ask "what would I need to go with it?" The answer is 9 − 2 = 7. Then you scan the rest of the list looking for a 7. It is there, so you are done.

That works, but look at how much scanning it costs when the list is long. For every number you walk through the rest of the list. With n numbers that is roughly n × n ÷ 2 looks. For 8 numbers it is 28 looks, which is fine. For a million numbers it is about 500 billion looks, which is not fine. The slow part is the scan, not the subtraction.

Build the structure, one piece at a time

The scan is slow because the list has no memory of what it contains. Give it one. A hash map is a notebook with two columns: on the left a value you have seen, on the right where you saw it. Looking something up in the notebook costs about one step no matter how many entries it holds, because the computer turns the value into a page number and jumps straight there.

Now walk the list once, and at each number do exactly two things, in this order:

1. Compute the partner you need: target − nums[i]. Ask the notebook whether that partner is already written down.
2. If it is not, write the current number and its index into the notebook, and move on.

Here is the notebook after each step, with target 9 and the list 2, 7, 11, 15:

The order of the two things matters. Looking up first and writing second means a number can never pair with itself: when you ask about 7's partner, the notebook holds only numbers from earlier positions.

Why it is correct

The rule the loop keeps true is: when we are at position i, every number before position i is in the notebook. It is true at the start because nothing is before position 0 and the notebook is empty. Each step writes the current number before moving on, so it stays true.

Now suppose a correct pair exists at positions a and b with a < b. When the loop reaches b, the number at a is already in the notebook by the rule above, and the partner we ask for is exactly

target − nums[b] = nums[a]

so the lookup finds it. If no pair exists, no lookup ever succeeds and we correctly report nothing. Duplicates are handled too: if the list were 3, 3 with target 6, the second 3 finds the first one in the notebook.

Why it is fast

Each of the n numbers causes one lookup and at most one write, and each of those is about one step. So the whole pass is about 2n steps, which is O(n). Compare that with the by-hand scan: for a million numbers, two million steps instead of 500 billion. The price is the notebook, which can hold up to n entries, so the memory is O(n). You traded space for time, and that trade is the whole pattern.

How to recognise it in an interview

Listen for "find two elements whose sum (or difference) is k" on data that is not sorted, or "count pairs where a + b" satisfies something. If the data were sorted you would reach for two pointers instead; the hash map is for when sorting is not free.

The first thing to say out loud: "I will do one pass, and at each element look up its complement in a hash map before inserting the element itself." In Two Sum that is the whole solution. In Number of Good Pairs the partner is the same value, so the notebook stores counts instead of indices and each new element adds the count already seen. In Pairs of Songs With Total Durations Divisible by 60 the partner is (60 − t mod 60) mod 60, which is the same idea with a remainder instead of a difference.

02The idea in one line

One pass: look up what you still need, then store what you have.

Reach for it when: Find a pair/triple with a target sum or difference in unsorted data.

Cost: O(n) time, O(n) space.

03The walk-through, step by step

The video works one example: Two Sum on [2,7,11,15], target 9. These are its captions in order, so you can follow without the video or check a step you missed.

1. One pass: look up what you need, then store what you have
2. nums[0] = 5: need 5, is it in the map?
3. Not yet: store 5 → 0
4. nums[1] = 2: need 8, is it in the map?
5. Not yet: store 2 → 1
6. nums[2] = 11: need -1, is it in the map?
7. Not yet: store 11 → 2
8. nums[3] = 7: need 3, is it in the map?
9. Not yet: store 7 → 3
10. nums[4] = 3: need 7, is it in the map?
11. Yes: 7 was stored at index 3. Answer [3, 4]
12. Every earlier element is in the map, so each check is O(1): total O(n)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Arrays & Hashing: Frequency counting, Canonical key hashing, In-place index hashing, Set-start expansion, Seen-set cycle detection.