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.
Visualized
Here's a hash map in action. Watch how keys map to bucket positions, and how lookups are O(1):
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.