Two Sum · Optimal Solution

Trading memory for answers.

A warehouse receives a shipment of parts with known weights. Quality control needs to find exactly two parts whose combined weight matches a calibration standard — but scanning every possible pair takes quadratic time. The insight: for each number, calculate its complement, and check a hash map. If the complement exists, you have the answer. One pass. O(n) time. O(n) space.

Interactive

Watch the map grow

Concept

The complement insight

Instead of checking every pair (which takes O(n²)), you ask a simpler question at each position: "Have I already seen the number I need?" A hash map answers that question in O(1).

complement

target − nums[i]. The exact value that, paired with the current number, reaches the target sum.

hash map

Stores every number already visited, keyed by value, mapped to its index. Lookup is O(1).

single pass

One left-to-right scan. Each element is checked and stored once. Total work: O(n).

Algorithm

One pass, one map, one answer

Walk the array from left to right. At each position, either find the pair or record the current number for future lookups.

1

Calculate the complement

At index i, compute complement = target − nums[i].
2

Check the hash map

Look up complement in the map. If it exists, return its stored index and i.
3

Store the current number

If no match was found, insert nums[i] → i into the map and continue.

Edge Cases

Subtle traps

The hash map approach handles cases that trip up naive implementations.

Duplicate values

When two copies of the same number sum to the target — like [3, 3] with target 6 — the first 3 is stored, and the second 3 finds it as its complement. The check-before-store order prevents an element from pairing with itself.

Negative numbers

The complement formula works identically with negative values. For [-3, 4, 3, 90] with target 0, the complement of -3 is 3 — and 3 appears later at index 2. The map stores -3 at index 0; when we reach 3, the lookup succeeds.