Two Sum, Properly Explained
Two Sum is the first problem where most people meet the core trick of algorithmic thinking: instead of searching for a partner, remember what you have seen so you can be found. That inversion — from asking to being asked — is what collapses the nested loop, and it reappears in half of the problems you will solve afterwards.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
vector<int> twoSum(vector<int>& a, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < (int)a.size(); i++) {
int need = target - a[i];
if (seen.count(need)) {
return {seen[need], i};
}
seen[a[i]] = i;
}
return {};
}
int main() {
vector<int> a = {2, 7, 11, 15};
vector<int> r = twoSum(a, 9);
cout << r[0] << ' ' << r[1] << endl;
return 0;
}Single pass: it looks for the complement among values already stored, then records the current value — order matters and is the source of the classic bug.
How it works, step by step
Turn the search around
The brute force asks, for each i, which later j completes the pair. The hash version asks, for each i, whether some earlier element was waiting for exactly this value. Both find the same pair; only one costs O(1) per element.
The complement is fully determined
Given a[i] and the target, the partner must be target - a[i]. There is nothing to search for — you compute the exact value you need and ask the map whether it exists. That is why no comparison loop is required.
Lookup before insert
Checking the map before adding a[i] guarantees the match came from a strictly earlier index. Insert first and a[i] can match itself whenever target is exactly 2 * a[i].
The map stores value to index
The key is the value because that is what you look up; the payload is the index because that is what you must return. Getting these backwards is a surprisingly common mistake and produces a map you cannot query.
Duplicates resolve themselves
If a value appears twice, the first occurrence is stored and the second finds it. The later assignment seen[a[i]] = i overwrites the earlier index, but only after any pair involving it would already have been found.
Complexity
Each element does one hash lookup and one insert, both expected O(1), so the pass is linear; worst-case hashing degrades to O(n) per operation with adversarial keys, and the O(n) space is the price you pay to avoid the quadratic scan.
Common bugs
Inserting before looking up
If seen[a[i]] = i comes first, then for target 6 and input {3, 2, 4} the element 3 finds itself and you return {0, 0}. The lookup must happen against the map as it was before the current element was added.
Sorting to use two pointers, then returning wrong indices
The two-pointer approach requires sorted input, but sorting destroys the original positions, so the indices you return refer to the sorted copy. If the problem wants original indices, either use the hash map or sort pairs of (value, index) and return the stored index.
Using seen[need] to test membership
operator[] on an unordered_map inserts a default-constructed 0 when the key is missing. Writing if (seen[need]) both mutates the map and misreads a genuine index 0 as absent. Use count() or find(), not the subscript, for existence checks. The map quietly gaining an entry on every miss is obvious the moment you watch its contents step by step in DryRun, and invisible in the final output.
Assuming exactly one solution exists
The classic problem statement promises a unique answer, and the early return depends on it. If your input can have several valid pairs, this returns whichever comes first in scan order, which is not necessarily the one your tests expect.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why is the hash map solution to Two Sum O(n)?
Because each element is processed once and each processing step does a constant-time hash lookup and insert. The brute force is O(n squared) because for every element it scans the rest of the array; the hash map replaces that scan with a single direct lookup of the exact complement value.
Can Two Sum be solved without extra space?
Yes, by sorting the array and using two pointers converging from both ends, which uses O(1) extra space but O(n log n) time. The catch is that sorting changes the indices, so this only works when the problem asks for the values or when you sort value-index pairs together.
Why check the hash map before inserting the current element?
To prevent an element from pairing with itself. If you insert first, then for a target equal to twice the current value the lookup finds the entry you just wrote and returns the same index twice. Checking first guarantees any match came from a strictly earlier position.
What if the array contains duplicate values?
It still works. The first occurrence is stored in the map, and when the second occurrence computes its complement it finds that stored index. Overwriting the map entry afterwards is harmless because any pair involving the earlier index would already have been returned.