Two Sum

The machine must return the indices of two numbers that add up to a target, and exactly one solution is guaranteed. The naive approach checks every pair, which is O(n²). The insight: you never need to look ahead. Walking left to right, each element asks "have I already seen the complement target - num?" A hash map answers that in O(1).

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        comp = target - num
        if comp in seen:
            return [seen[comp], i]
        seen[num] = i

Steps: (1) iterate once, (2) check whether the complement is in the map, (3) if found, return [stored_index, i]; otherwise record num -> i and keep going.

Time is O(n): every lookup and insert is O(1) amortized, over n elements. Space is O(n) in the worst case, when the answer sits at the end of the array.

Trickiest edge case: duplicates like [3, 3] with target 6, and the self-pair trap when target == 2 * num. Because each value is stored only after its own lookup, an element can never pair with itself — check-then-store is what makes [3,3] return [0,1].