Two Sum (LeetCode #1)

Two Sum — LeetCode problem #1 — asks for the two indices in an array nums whose values add up to a target. The one-pass hash-map solution walks the array once, asking at each element whether its complement has already been seen, and cuts the time complexity from the brute-force O(n²) to O(n).

Think of a doorman with a guest list. As each guest arrives, he doesn't run back through the whole party looking for their partner — he checks the list first: "is the person who would complete this pair already inside?" If yes, done. If no, he writes the newcomer down and waits for the next arrival. The list is the hash map; the check-then-write order is the whole algorithm.

How Two Sum Works

Walk the array left to right, maintaining a dictionary seen that maps each value to its index. At position i, compute complement = target - nums[i] — the partner value this element needs. Check whether the complement is already in seen; if it is, return [seen[complement], i], earlier index first. Only after the check fails do you insert the current element: seen[nums[i]] = i.

That ordering — check the list before writing yourself onto it — is the load-bearing detail. When nums[i] happens to equal target / 2, a same-iteration lookup would find the element you just inserted and pair it with itself, which the problem forbids. Because the check runs against the map as it stood before this iteration, an element can never be its own partner.

The naive alternative tests every pair (i, j) with j > i in a double loop. No memory, no dictionary — just n(n−1)/2 candidate pairs, O(n²). Both solutions are animated here: the Approach toggle in the Inputs panel switches between Hash map (the default) and Brute force on the same input.

Two Sum Step by Step

The default input is nums = [2, 7, 11, 15] with target = 18, hash-map approach:

1. i = 0, nums[i] = 2. complement = 18 − 2 = 16. Is 16 in seen? No — the map is empty. Insert seen[2] = 0.
2. i = 1, nums[i] = 7. complement = 18 − 7 = 11. Not in seen. Insert seen[7] = 1. The map is now {2: 0, 7: 1}.
3. i = 2, nums[i] = 11. complement = 18 − 11 = 7. Is 7 in seen? Yes — at index 1. Return [1, 2]. The doorman never even glances at the 15.

Flip the toggle to brute force and the same input takes four pair checks: 2 + 7 = 9, 2 + 11 = 13, 2 + 15 = 17, then 7 + 11 = 18 — return [1, 2]. Same answer, but the running checks counter in the header is the number to watch: it grows with the square of the input, while the hash map's pass stays linear.

In the visualization, the array sits on the right and seen builds up as a two-column "value | index" panel on the left — the guest list, made literal. Each iteration runs four beats: the active cell glows, the complement is computed, the dictionary is probed, and the element either matches (the dict row and the active cell turn green together — they are the pair) or is written into seen — a new row, or an overwrite of its row when the value repeats. In brute-force mode the panel disappears entirely; that absence is the difference between the two approaches.

Time and Space Complexity

The space buys the speed: the hash map spends O(n) memory to make "have I seen your partner?" a constant-time question instead of a rescan. At the default's tiny n = 4 the two finish in a comparable number of beats — grow the input and watch the checks counter pull away while the hash map's work grows only linearly.

Edge Cases

The player accepts 3–8 values in the range 1–99, so a couple of these are worth working on paper.

• No solution. LeetCode guarantees exactly one answer, but the displayed code simply falls off the end of the loop (returning None in Python). The animation surfaces this honestly with an explicit "no solution" beat rather than crashing; real code should handle it explicitly.
• The pair is two equal values — say nums = [3, 3, 4], target = 6. At i = 1, the complement 3 is already in seen from index 0, so the result is [0, 1]. This works only because of check-before-insert.
• Duplicates not in the answer. A repeated value overwrites its row in the map — safe, because the earlier index's own complement check has already run by the time it gets overwritten.
• Negatives and zero need no special handling — a hash map keys on any integer — though the player's input range keeps them off the canvas.

Common Mistakes

• Insert before check. The most common bug. It looks symmetric, but it lets target / 2 match the element you just wrote down — the doorman pairing a guest with their own name tag.
• Returning values instead of indices. The problem wants positions. The map must store indices as its values, not the numbers themselves.
• Sorting first to use two pointers. Sorting destroys the original indices; recovering them means carrying each value's position along, which is more bookkeeping than the hash map needed in the first place.
• Using a set instead of a map. A set answers "is this value present?" but not "at which index?" — and the index is the output.