Two Sum
Store what you've seen so each element only looks up its complement.
Hash Map Trace
Problem
Given an array of integers and a target value, find two different positions whose values add up to the target. Return the two indices in any order; the input guarantees that exactly one valid pair exists.
Examples
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
The Goal
Find two different positions in nums whose values add up to target, and return their indices.
For nums = [2, 7, 11, 15] and target = 9, the pair is 2 + 7, at indices 0 and 1. The answer is [0, 1].
Checking every pair is O(n²). A hash map gets it down to one pass.
One partner per number
Each number has exactly one partner that works: target minus itself. Ask a map whether that partner has already gone by.
One lookup per number replaces a scan over every earlier one.
Key Idea: Remember What You've Seen
For each num, the only partner that works is complement = target - num.
Keep a map seen from each number already read to its index. If complement is in seen, its index is the other half of the answer.
Store num only after its own lookup. Then seen holds earlier positions only, and a number can't pair with itself.
Work out target - num and look it up.
At 7: 9 - 7 = 2, found at index 0
The Algorithm
One pass. Each step works out the complement, looks it up, and either returns or stores the number.
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []The problem promises an answer, so the last line only runs on inputs that break that promise.
| Approach | Work per number | Time | Extra space |
|---|---|---|---|
| Check every pair | Scan the others | O(n²) | O(1) |
| Hash map | One lookup | O(n) | O(n) |
| Sort, then two pointers | Move one pointer | O(n log n) | O(n) to keep indices |
Walkthrough
Run it on [2, 7, 11, 15] with target = 9.
At index 0, 2 needs 7. seen is empty, so 2 goes in: {2: 0}. At index 1, 7 needs 2, and seen has it at index 0. Return [0, 1]. The loop never reaches 11 or 15.
Change the numbers on the stage. The search stops at the first number whose partner has already gone by.
Checkpoint · predict the next step
Step 3 of 7 on the stage: Is 7 in seen? No. No earlier number pairs with 2.
i on 2 (index 0) · seen = {} · target 9 · complement 7
Pitfalls
- Look up before you store. Storing first lets
[3, 2, 4]withtarget = 6pair the 3 with itself. - Return indices, not values.
- Equal values are fine at different positions. For
[3, 3]andtarget = 6, the first 3 is stored and the second finds it. - A repeated number overwrites its index in
seen, so a match returns the later index.
At each index, what should the loop do first?
Complexity
Each number gets one lookup and at most one store, both constant time on average. That's O(n) time.
seen can hold almost every number, so extra space is O(n). You trade that memory for the O(n²) pair checks.
One pass with a hash map
- One passEach index once.dominantO(n)
- Lookup and storeOn average, per number.O(1)
- seenUp to one entry per number.dominantO(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Linear memory buys a single pass.
In short
The brute force checks every pair in O(n²). Instead, walk the array once and keep a hash map of value → index. For each number, check whether its complement (target − num) is already in the map; if so you're done, otherwise record the current number. You trade O(n) memory for a single linear pass.
Common mistake
Adding a number to the map before checking for its complement — that can match an element with itself. Check first, then insert.