visual walkthrough
Two Sum
The most-asked interview problem ever; teaches the 'store the complement' idea behind countless solutions.
The idea
For each number there is exactly one partner that completes the target: target minus the number. Instead of scanning for it, keep every number you've passed in a hash map and look the partner up in one step.
You only ever need to look backwards: if the partner comes later, that later number will find this one when its turn comes.
Complexity
| approach | time | space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Hash map | O(n) | O(n) |