LeetCode #1 — Two Sum, and the hash map reflex

Problem: Given an array nums and a target, return the indices of the two numbers that add up to the target. Exactly one solution exists.

The naive instinct

Check every pair. Two nested loops, O(n²) time, O(1) space:

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Fine for n=100. Painful for n=10⁶.

The reframe

The question "which pair sums to target?" is really "for each number x, have I already seen target - x?" — and "have I seen X?" is exactly what a hash map answers in O(1).

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

One pass. O(n) time, O(n) space. We traded memory for time — the most common trade in interview problems.

The pattern to remember

Whenever a problem asks about pairs, complements, or "have I encountered this before?" — reach for a hash map before you reach for a second loop. This reflex alone solves a surprising fraction of easy/medium array problems.