The hash map pattern — turning O(n^2) into O(n)

The single highest-value pattern in interview-style problems, worked through two-sum from brute force to the optimal solution, plus why it works.

Intermediate

3 min read

The problem

Given a list of numbers and a target, find two numbers that add up to the target. Return their indices.

nums = [2, 7, 11, 15]
target = 9
# answer: [0, 1] — because nums[0] + nums[1] == 9

The brute-force instinct — check every pair

def two_sum_brute(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]

This is correct and it's O(n^2) — for every element, it scans every other element looking for a match. It works fine on 10 numbers and becomes genuinely slow on 100,000.

The reframe that unlocks the fast solution

The brute-force version asks, for each number, "does some other number in the list equal target - nums[i]?" — and answers that question by scanning, which is O(n) per element. The fix isn't a cleverer scan — it's replacing the scan with a lookup:

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

One pass. For each number, check whether its complement (the number that would complete the pair) has already been seen — a hash map lookup, O(1) on average — instead of scanning the rest of the list. If not, remember this number's index for later. Total: O(n) time, O(n) extra space for the hash map. The trade is explicit: spend memory to avoid repeated scanning.

Why the hash map lookup is O(1) average case

A hash map computes a hash of the key and uses it to jump almost directly to the right storage bucket — it doesn't search through entries one by one the way a list does. This holds on average; a pathological case with many hash collisions degrades toward O(n), which is why languages harden their hash functions against adversarial input, but for ordinary data this is a safe, standard assumption to build on.

The pattern generalizes far beyond two-sum

Any time a brute-force solution is "for each item, scan the rest of the list looking for X," the question worth asking is: can X be checked with a hash map/set lookup instead of a scan? This exact reframe solves a large family of problems:

Contains duplicate — have I seen this value before? (hash set)
Group anagrams — group strings by a computed key (sorted letters, or a letter-count tuple) using a hash map from key to list of matches.
First unique character — count occurrences with a hash map, then scan once more for the first count of 1.

In every case, the shape is identical: one pass to build or check against a hash map, instead of a nested loop re-scanning the input for every element.