Two Sum

Intuition

Given an array of integers nums and a target, return the two indices whose values sum to target. The brute-force approach pairs every element with every other — O(n²). The trick: instead of asking "are there two values that add to the target?", ask the dual question for each element you see: "does the value I need to pair with this one already exist in what I've already seen?"

That dual question is a constant-time lookup if you keep a hash map of "value → index" as you walk the array. One pass, O(n) total.

How It Works

Walk the array left to right. Maintain a hash map seen that maps each value seen so far to its index. At each position i:

1. Compute the complement. complement = target - nums[i]. This is the partner value you'd need to reach the target.
2. Check seen first. If complement in seen, you've found a pair: return [seen[complement], i]. The order matters — the earlier index comes first.
3. Only then insert. Add the current element: seen[nums[i]] = i.

The "check before insert" ordering is the load-bearing detail. It's what prevents the algorithm from accidentally pairing an element with itself when nums[i] happens to equal target / 2. By the time nums[i] enters the map, its complement check has already finished.

Step By Step

For the default input nums = [3, 2, 4], target = 6:

1. i = 0, nums[i] = 3. complement = 6 − 3 = 3. Is 3 in seen? No (map is empty). Insert seen[3] = 0. Map is now {3: 0}.
2. i = 1, nums[i] = 2. complement = 6 − 2 = 4. Is 4 in seen? No. Insert seen[2] = 1. Map is now {3: 0, 2: 1}.
3. i = 2, nums[i] = 4. complement = 6 − 4 = 2. Is 2 in seen? Yes, at index 1. Return [1, 2].

In the visualization, the array sits on the right and the seen dictionary builds up as a two-column "value | index" panel on the left. At each step the active cell glows; the complement is computed above it; a probe arrow shoots into the dict. When the probe hits, the matched dict row and the active cell both turn green simultaneously — they're the pair.

Complexity

Space: O(n) — the hash map can grow to hold every element if no pair is found until the last one.

The space trade-off is what buys the speedup. Brute force is O(1) space and O(n²) time; the hash-map approach is O(n) space and O(n) time. Almost always the right call.

Edge Cases

• No solution exists. The problem statement on LeetCode guarantees exactly one solution, but the displayed code falls off the end of the loop without returning, which is None in Python. Real code should handle this explicitly.
• The pair is two equal values. Example: nums = [3, 3], target = 6. The check-before-insert ordering matters: at i = 1, complement = 3 and seen already contains {3: 0} from the previous iteration. Return [0, 1]. If you reversed the order (insert first, check second), seen[3] would be overwritten to 1 before the check, and you'd return [1, 1] — using the same element twice, which the problem forbids.
• The pair is nums[i] with itself in a different sense: nums = [3, 2, 4], target = 6. complement at i = 0 is 3, the same value as nums[0]. Check-before-insert prevents the false match by checking against an empty map first.
• Negative numbers / zero. No special handling needed — the hash map handles any int key.
• Duplicates in nums not part of the answer. The map can only hold one index per value; the later index overwrites the earlier. This is safe because by the time the overwrite happens, the earlier index's complement check has already either succeeded or moved on.

Common Mistakes

• Insert before check. The most common bug. It looks symmetric ("we'll just check on the next iteration") but it breaks the self-pairing case.
• Returning values instead of indices. The problem asks for the two indices. The map must store indices as values, not the array values themselves.
• Sorting first. A natural instinct ("then I can two-pointer it") — but sorting destroys the original indices. If you really want the two-pointer approach, you have to remember each value's original index alongside it, which adds bookkeeping the hash-map solution avoids entirely.
• Using a hash set instead of a hash map. A set tells you "this value is present" but not "at which index". The output requires indices, so a map is non-negotiable.
• Over-engineering for the rare "multiple solutions" case. The problem guarantees exactly one. Don't write code to collect all pairs — you'll fail the early-return optimization that makes this O(n) average.