Two Sum
Find the two numbers in an array that add up to a target, and return their positions.
- Hash map lookup
- Complement
Before this, know: Arrays and indexes, Hash maps (Map in JavaScript, dict in Python)
You get a list of numbers called nums and one more number called target.
Somewhere in the list, exactly two numbers add up to target. Your job is to
say where they are.
“Where” means their index: the position of an item in the list. Indexes start at 0, so the first item is at index 0, the second at index 1, and so on.
Here is a small example. nums = [4, 1, 5, 3] and target = 8:
- 40
- 11
- 52
- 33
So the answer is [2, 3]. A few rules from the problem statement:
- There is always exactly one correct pair.
- You can’t use the same position twice. If
targetis 8 and there is one 4, you can’t answer[0, 0]. - You may return the two indexes in any order.
That “someone wearing a 3” has a name in this problem: the complement. It’s the missing piece that completes your number:
Pause and think
For 7 you need 2, because 9 − 7 = 2.
For 11 you need −2, because 9 − 11 = −2. Complements can be negative, and that’s fine: we just look for −2 in the list.
Brute force means “try every possibility”. It’s the most obvious idea, and it’s always a good first step to say out loud in an interview.
The idea: pick the first number, then add it to every number after it. Then pick
the second number and add it to every number after that. Stop when a sum
equals the target. We use two pointers (variables that remember a position):
i for the first number and j for the second.
Brute force: try every pair
nums = [4, 1, 5, 3], target = 8
- 40
- 11
- 52
- 33
- target
- 8
- nums[i] + nums[j]
- —
- checks so far
- 0
- First number (i)
- Second number (j)
- Pair that works
Pick nums[0] = 4 as the first number. Now try every number after it.
Which line is running?
function twoSum(nums, target) {Running now: for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } return []; // LeetCode promises an answer exists, so we never get here}Brute force
function twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } return []; // LeetCode promises an answer exists, so we never get here}def two_sum(nums, target): for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return [] # LeetCode promises an answer exists, so we never get herej always starts at i + 1. That does two jobs: we never pair a number with
itself, and we never check the same pair twice (4 + 1 is the same as 1 + 4).
Count the checks. With 4 numbers, the first number is checked against 3 others, the second against 2, the third against 1:
3 + 2 + 1 = 6 checks. That’s fine.
With 10,000 numbers it’s 9,999 + 9,998 + … + 1, which is
10,000 × 9,999 ÷ 2 = 49,995,000 checks. About fifty million! In general,
for n numbers we do about n × n ÷ 2 checks.
We describe this growth with Big-O notation: a way of saying how the work grows as the input grows. Work that grows like n × n is written O(n²) (“O of n squared”): double the input, and the work goes up four times.
The brute force spends almost all its time searching for a partner. What if looking up “is there a 3?” took one step instead of a whole scan?
That’s exactly what a hash map gives us. A hash map stores key → value
pairs, like a dictionary stores word → meaning, and it can answer “do you have
this key?” in about one step, no matter how many items it holds. In JavaScript
it’s called a Map; in Python it’s a dict.
Pattern
Hash map lookup (complement)
Use it when: you need to find a pair (or partner) that satisfies a condition, and checking every pair would be too slow.
Signal words
- “two numbers that add up to”
- “find a pair”
- “return their indices”
- “has a matching element”
- Create an empty hash map called
seen. It will remember number → index for every number we pass. - Walk through the list one number at a time. Call the current index
i. - Work out the partner we need:
need = target − nums[i]. - Ask the map: is
needinseen? If yes, we’re done. Return[seen[need], i]. - If not, write the current number into the map,
seen[nums[i]] = i, so later numbers can find it. Then move on.
Press Play, or click the player and use the arrow keys. Watch the code panel underneath: the highlighted line is the one running at that moment. Try the edge-case buttons too.
One pass with a hash map
nums = [4, 1, 5, 3], target = 8
- 40
- 11
- 52
- 33
| number | index | |
|---|---|---|
| empty | ||
- target
- 8
- i
- —
- nums[i]
- —
- need
- —
- answer
- —
- Looking at now
- Already written in the map
- Partner found
- Partner not found (yet)
- Just written in the map
We want two numbers that add up to 8. We start with an empty hash map called "seen": a notebook where we'll write down every number we pass and its index.
Which line is running?
function twoSum(nums, target) {Running now: const seen = new Map(); // number -> the index where we saw it for (let i = 0; i < nums.length; i++) { const need = target - nums[i]; if (seen.has(need)) { return [seen.get(need), i]; } seen.set(nums[i], i); } return []; // LeetCode promises an answer exists, so we never get here}Notice the order inside the loop: we check first, then write. That’s what
stops a number pairing with itself. Try the “duplicates” example: with
[3, 3] and target 6, the first 3 doesn’t find a partner (the map is empty), so
it gets written down. The second 3 then finds the first one.
One pass with a hash map
function twoSum(nums, target) { const seen = new Map(); // number -> the index where we saw it for (let i = 0; i < nums.length; i++) { const need = target - nums[i]; if (seen.has(need)) { return [seen.get(need), i]; } seen.set(nums[i], i); } return []; // LeetCode promises an answer exists, so we never get here}def two_sum(nums, target): seen = {} # number -> the index where we saw it for i, num in enumerate(nums): need = target - num if need in seen: return [seen[need], i] seen[num] = i return [] # LeetCode promises an answer exists, so we never get hereLines 1–6 are the same in both languages; after that JavaScript has an extra
closing brace }, so its line numbers run one ahead.
- Line 1: define the function. It takes the list
numsand the numbertarget. (On LeetCode, Python wraps this inclass Solutionasdef twoSum(self, nums, target); the body is identical.) - Line 2: create an empty hash map.
new Map()in JavaScript,{}in Python. We’ll store each number as the key and its index as the value, because the index is what we have to return at the end. - Line 3: loop over every position. In JavaScript
icounts 0, 1, 2…; in Pythonenumerate(nums)hands us both the indexiand the numbernumeach time. - Line 4: compute the complement, the partner this number needs.
- Line 5: the key question.
seen.has(need)/need in seenasks the map whether that partner has already gone by. This takes about one step, which is the whole reason the solution is fast. - Line 6: if it has, we know both positions: the partner’s index (stored in
the map) and our own index
i. Return them. - Line 8 (JS) / line 7 (Python): otherwise, remember the current number and its index for later. This happens after the check on purpose (see the mistakes section).
- The last line: the problem promises an answer exists, so we never reach it. It’s there so the function always returns a list.
Let’s trace nums = [4, 1, 5, 3], target = 8 by hand, the way you’d do it on a
whiteboard. Each row is one trip around the loop.
| i | nums[i] | need = 8 − nums[i] | need in seen? | what happens | seen afterwards |
|---|---|---|---|---|---|
| 0 | 4 | 4 | no (empty) | write 4 → 0 | {4: 0} |
| 1 | 1 | 7 | no | write 1 → 1 | {4: 0, 1: 1} |
| 2 | 5 | 3 | no | write 5 → 2 | {4: 0, 1: 1, 5: 2} |
| 3 | 3 | 5 | yes, at index 2 | return [2, 3] | (we stop here) |
Look at the i = 0 row: the number 4 needs another 4. The map is empty, so there’s no match, which is correct: there is only one 4, and we can’t use it twice.
Brute force
Time
O(n²)
Every number is checked against every number after it: about n × n ÷ 2 additions.
Space
O(1)
Only two pointers, i and j, no matter how long the list is. O(1) means 'a fixed amount'.
One pass with a hash map
Time
O(n)
We visit each number once, and each map lookup or insert takes about one step. 10,000 numbers ≈ 10,000 steps, not 50 million.
Space
O(n)
In the worst case (the pair is at the very end) the map ends up holding almost every number.
This is a classic trade: we spend extra memory (the map) to save a huge amount of time. In interviews that trade is almost always worth it, and it’s worth saying out loud.
What to say out loud, in this order:
- Restate the problem and confirm: “Exactly one answer? Can I use the same element twice? Any order?”
- Give the brute force and its cost: “Checking every pair is O(n²) time, O(1) space.”
- Spot the waste: “Most of the time goes into searching for the partner.”
- Fix it: “A hash map makes that search one step, so one pass is O(n) time, at the cost of O(n) extra space.”
- Walk through a small example (like the dry run above) before and after coding.
Likely follow-up questions:
- “What if the array is sorted?” Then you don’t need the map at all: put one pointer at each end and move them toward each other. That’s O(n) time with O(1) space. It’s Two Sum II, coming up in week 2.
- “What if there could be no answer?” Return an empty list (our last line already does).
- “Return all pairs?” You’d keep going instead of returning, and think about duplicates.
Related problems:
- Contains Duplicate and Valid Anagram (this week): the same “remember what you’ve seen in a hash map/set” idea. See the week 1 overview.
- Two Sum II and 3Sum (week 2): pair-finding again, using two pointers on sorted input.