p01 Two Sum — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

You don’t need to compare every pair. Think about what information you’d want to have already seen by the time you reach element nums[i].

Hint 2 — Data structure family

For each element x you encounter, there is exactly one “partner value” that would solve the problem. What data structure lets you check in O(1) whether you’ve seen a specific value already?

Hint 3 — The key insight

For each x at index i, the value you need to find is target − x. If you’ve stored every previously seen value with its index, you can ask the question “have I seen target − x before?” in O(1).

Hint 4 — Pseudocode skeleton

seen = empty map (value → index)
for i in 0 to N-1:
    let x = nums[i]
    let complement = target - x
    if complement is in seen:
        return [seen[complement], i]
    add x → i to seen

Pay close attention to the order of the check and the insert. There is exactly one correct order.

Hint 5 — Full algorithm in words

Walk the array left to right with a hashmap seen that grows as you go. For each element x at index i:

1. First, check if target − x is already a key in seen. If yes, return [seen[target − x], i] — you’ve found the pair, with the earlier index first.
2. Then, insert x → i into seen.

Why check before insert? If you insert first, then for input [3, 3] with target = 6, at index 0 you’d insert 3 → 0, then check for complement 3 and find it — but the only index satisfying it is 0 itself, returning [0, 0], which violates “two distinct indices”. Checking before inserting guarantees the complement was found at a strictly earlier index.

The loop invariant: at the start of iteration i, seen contains exactly the values nums[0..i-1] mapped to their indices.

Time: O(N) — one pass, O(1) per element. Space: O(N) — the map can hold up to N entries.