Two Sum
Two Sum is LeetCode 1 (Easy). Given an array nums and a target, return the indices of the two numbers that add up to target.
Exactly one valid answer exists, and the same element may not be used twice. With n up to 10⁴ the brute-force double loop still passes, which is why the two sum hash map version is worth learning here rather than being forced on you.
- 2 ≤ nums.length ≤ 10⁴
- −10⁹ ≤ nums[i] ≤ 10⁹
- −10⁹ ≤ target ≤ 10⁹
- Exactly one valid answer exists
At n ≤ 10⁴ the O(n²) scan is about 10⁸ operations, so the brute force passes but crawls. The values are what rule out the alternatives: at ±10⁹ you cannot index an array by value, so counting or bucketing is out and a hash map is the only O(1) lookup available. And exactly one valid answer is the licence to return on the first hit instead of collecting every pair.
Intuition
The brute-force double loop asks the same question over and over: for this number, is its partner anywhere in the array? But the partner is not something to search for — it is fully determined. The partner of num is exactly target − num.
So the question becomes have I already seen target − num, which a hash map answers in O(1). One pass suffices: for each number, look up its complement, and if it is absent record the current number against its index for later numbers to find.
The map is keyed by value because the lookup is by value, and stores the index because the index is the answer.
The two sum problem is the template: when the brute force is a double loop, ask what the inner loop keeps asking. If the answer is have I seen this value before, a hash map deletes that loop and turns O(n²) into O(n). The same reflex solves subarray-sum-equals-k and contains-duplicate.
Approach
Before reading on: you know the brute force is a double loop. Write down, as one sentence, the question that inner loop keeps asking. If your sentence contains the words “have I seen”, you already have the solution.
Two ways to solve it
Use this whenever the array is unsorted and the answer must be indices.
- Speed: a single pass with O(1) lookups.
- Indices: preserved exactly, since nothing is sorted or moved.
- Cost: O(n) extra memory to hold the map of values seen.
This is the version an interviewer is waiting for.
Reach for this only when extra memory is the binding constraint.
- Memory: constant, because nothing is ever stored.
- Simplicity: no data structure to reason about or get wrong.
- Speed: roughly 10⁸ operations at n = 10⁴, so it crawls.
It passes within these constraints, but it is exactly the loop the hash map exists to remove.
The hash map wins because the partner of each number is known in advance, so no inner loop is needed. The steps, code and live run below follow it; the brute-force pair scan appears further down for comparison.
Look the partner up instead of searching for it
For each number, its partner is exactly target − num. Keep a hash map of every value seen so far against its index, so asking whether the partner exists is a single O(1) lookup rather than a scan of the rest of the array. These are the two sum indices the problem wants back.
Key the map by value, store the index
You look up by value and you return indices, so value must be the key and index the payload. Reversing them makes the lookup impossible, since you never know the partner’s position in advance — only its value.
Check the map before inserting the current number
Query the map first, then insert. That order does two things:
- Stops self-matching: inserting first lets a number find itself whenever the target is double its value, so
[3, 2, 4]with target 6 would return[0, 0]. - Enforces no reuse for free: the map holds only earlier numbers, so no explicit test that the two indices differ is needed.
Return on the first match
Exactly one valid answer is guaranteed, so the first pair found is the answer and the scan can stop. Without that guarantee you would have to keep scanning and collect every pair, which is a different problem.
Two Sum solution in Python | C++ | Java
target − num, so there is nothing to search for. Walk the array once, and for each number ask the map whether its partner has already gone by.2, so the partner must be 7. The map does not hold it, so this number cannot be the second half of the pair — record it and move on.2 against index 0. The value is the key because the lookup is by value, and the index is what the answer needs. Storing after the check is what stops a number pairing with itself.2 from index 0, and 2 + 7 = 9. Exactly one answer is guaranteed, so return [0, 1] straight away.target − num, so there is nothing to search for. Walk the array once, and for each number ask the map whether its partner has already gone by.3, so the partner must be 3. The map does not hold it, so this number cannot be the second half of the pair — record it and move on.3 against index 0. The value is the key because the lookup is by value, and the index is what the answer needs. Storing after the check is what stops a number pairing with itself.2, so the partner must be 4. The map does not hold it, so this number cannot be the second half of the pair — record it and move on.2 against index 1. The value is the key because the lookup is by value, and the index is what the answer needs. Storing after the check is what stops a number pairing with itself.2 from index 1, and 2 + 4 = 6. Exactly one answer is guaranteed, so return [1, 2] straight away.target − num, so there is nothing to search for. Walk the array once, and for each number ask the map whether its partner has already gone by.3, so the partner must be 3. The map does not hold it, so this number cannot be the second half of the pair — record it and move on.3 against index 0. The value is the key because the lookup is by value, and the index is what the answer needs. Storing after the check is what stops a number pairing with itself.3 from index 0, and 3 + 3 = 6. Exactly one answer is guaranteed, so return [0, 1] straight away.Brute-force pair scan
Check every unordered pair of indices and return the first whose values add up to the target. The inner loop starts at i + 1, which is what stops an element being paired with itself.
Common pitfalls
Storing the whole array first, then searching
for i, n in enumerate(nums):
seen[n] = i
for i, n in enumerate(nums):
if target - n in seen:
return [i, seen[target - n]]for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = iWith nums = [3, 2, 4] and target = 6, the pre-filled map lets 3 find itself and returns [0, 0]. Checking before inserting means a number can only ever pair with an element that came earlier, so it can never be its own partner.
Keying the map by index instead of value
seen[i] = n ... if target - n in seen: # searching keys that are indices
seen[n] = i ... if target - n in seen: # searching keys that are values
You look things up by value (target - n) and return indices, so value must be the key and index the payload. Reversing them makes every lookup a coincidence of small arrays where indices and values happen to overlap.
Edge cases
Checking the map before inserting means the first 3 is stored and the second 3 finds it — two distinct indices, no element reused.
target − num is plain arithmetic, so sign and zero change nothing about the lookup.
A later duplicate overwrites the earlier index, which is harmless: the answer is unique, so the overwritten index was never going to be needed.