Animations
Two Sum — Visual Walkthrough
Watch how the hash map solution finds a pair of numbers that add up to a target in one pass.
Two Sum
Array: [2, 7, 11, 3, 5, 9] — Target: 9
Find two numbers that add up to 9. Return their indices.
Two Sumhash map · O(n)
target9
2
[0]7
[1]11
[2]3
[3]5
[4]9
[5]current (i)
match in seen
found pair
seen dictionary
empty — nothing stored yet
arr[i]—
complement—
in seen?—
two_sum.py
def two_sum(arr, target):
seen = {}
for i, num in enumerate(arr):
complement = target - num
if complement in seen:
return [seen[complement], i] # found!
seen[num] = i
return -1 # no pair found
Call two_sum([2, 7, 11, 3, 5, 9], target=9)
step 0/9
0%
How it works
The hash map approach solves this in a single pass — O(n) time:
def two_sum(arr, target):
seen = {}
for i, num in enumerate(arr):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return -1For each number, calculate what value is needed to reach the target — the complement. Check if that complement was already seen. If yes — found the pair. If no — store the current number and keep going.
The brute force approach uses two nested loops — O(n²). The hash map approach uses one loop and a dictionary — O(n). For 10,000 numbers that is a 10,000x speedup.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Hash map | O(n) | O(n) |