The Problem#
Given an array of integers nums and a target integer target, return the indices of the two numbers that add up to target. You can assume exactly one solution exists.
Approach 1: Brute Force, O(N²)#
Check every pair:
This works, but it's slow: N² comparisons for N elements.
Approach 2: Hash Map, O(N)#
For each number, check if its complement (target - num) is already in a hash map. If yes, we found the pair. If no, store the current number.
We trade space (O(N) for the hash map) for time: one pass instead of two nested loops.
The Hash Map, Visualized#
The one-pass solution rests entirely on seen answering "is the complement in here?" without scanning. So it's worth watching a hash map do that.
Let's take the example of this visualization: the keys apple, banana, cherry and date going into a 7-bucket table. Press play and watch each key get hashed straight to a bucket index rather than compared against the keys already stored. That includes cherry, which collides with banana and is chained behind it, still one hop from its bucket. That single jump is what replaces the inner loop of the brute-force version. target - num in seen is exactly this lookup, run once per element.
Key Insight#
The hash map lets us answer "have I seen the complement of this number?" in O(1) instead of scanning the whole array again. This O(N) vs O(N²) gap becomes significant at scale. For N = 10,000, brute force does 50 million comparisons; the hash map does 10,000.