Lesson 4.2 · Hashing
The Complement Trick
Turn "find two elements that combine to a target" from O(n²) into O(n) by remembering each element as you pass it.
12 min
Think of it like this
Matching socks from a laundry pile: instead of comparing every sock with every other sock, you lay each one on the bed. When a new sock comes out, you just check whether its partner is already on the bed.
1.Ask about the past, not the future
In a pair problem, every pair has a later element. So scan left to right, and for each element ask: has its partner (the complement, like target − x) already appeared? A hash map from value to index answers in O(1).
Check first, then store the current element. That order stops an element from pairing with itself.
nums = [3, 8, 4, 6], target = 10seen (value → index)(map)
Step 1/4Need 10 − 3 = 7: not seen. Store 3.
2.Other complements
The complement isn't always target − x. For "difference equals k" it's x − k and x + k. For "duplicate within k positions" it's the same value, with a window of recent indexes. For "longest consecutive run" it's x − 1 (is x the start of a run?).
Remember
- Scan once; for each x, look up its complement among earlier elements.
- Check before inserting.
- Store indexes as values when you must return positions.
Common mistakes
- Inserting before checking, so x pairs with itself when target = 2x.
- Sorting first when the problem needs original indexes.