Hash Maps: Trading Space for Speed

The one move behind a dozen problems

Look at almost any brute-force O(n^2) solution and you'll find the same shape: an outer loop over the array, and an inner loop that rescans the array asking a simple question — "does X exist somewhere?", "how many of these have I seen?", "where did I last see this?".

A hash map answers those questions in O(1). So the entire trick of this module is: replace the inner loop with a dictionary probe. You pay O(n) extra memory to remember what you've seen; in exchange, O(n^2) becomes O(n). That's the trade in the lesson title — space for speed.

Quick vocabulary: a hash map stores key–value pairs with O(1) average insert and lookup; a hash set stores just keys. "Average" because two keys can land in the same internal slot (a collision) and chain together — the worst case is O(n), but for interview purposes you say "O(1) average" once and move on.

The pattern comes in four flavors. Learn to spot which question the inner loop is really asking.

Flavor 1: membership — "does X exist?"

The simplest use: a hash set as a seen-it-before detector. Contains Duplicate is the pure form — walk the array, and for each value ask "is it already in my set?" before adding it.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

One pass, O(n) time, O(n) space. The brute force compared every pair: O(n^2).

Flavor 2: complements — "have I seen the partner I need?"

Two Sum is the canonical interview problem, and its key insight generalizes everywhere: instead of searching for a pair, walk the array once and for each value x ask, "have I already seen target − x?" The map stores value → index as you go.

Worked example: nums = [2, 7, 11, 15], target = 9.

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

The order matters: check before you insert. If you insert x first and then look up target − x, an element can match itself — with target = 8 and x = 4, you'd "find" 4 in the map and return the same index twice.

Flavor 3: counting — "how many so far?"

A hash map from value to count turns frequency questions into one pass. Valid Anagram is the clean example: two strings are anagrams (same letters, rearranged) exactly when their letter counts match. Count the first string up, count the second string down, and check nothing is left over. Any "appears more than n/2 times", "first unique character", or "do these collections match" problem is this flavor.

Flavor 4: grouping — design a signature key

The most creative flavor: choose a key so that things belonging together collide on purpose. Group Anagrams asks you to bucket words that are anagrams of each other. The insight is that all anagrams share a canonical form — their letters in sorted order:

def group_anagrams(words):
    groups = {}
    for w in words:
        key = "".join(sorted(w))       # "eat", "tea", "ate" -> "aet"
        groups.setdefault(key, []).append(w)
    return list(groups.values())

"eat", "tea", and "ate" all produce the key "aet", so they land in the same bucket. An equally valid key is the tuple of 26 letter counts, which avoids sorting each word. The general rule: a good key is canonical (all group members produce the identical key) and immutable (sets and maps can't use keys that might change — in Python that means a string or tuple, not a list).

A subtler membership trick: sequence heads

Longest Consecutive Sequence asks for the longest run of consecutive integers (like 1, 2, 3, 4) hiding in an unsorted array — in O(n), so sorting is off the table. Put everything in a set, then count runs. The naive version counts upward from every element and quietly becomes O(n^2) on a long run.

The fix: only start counting from a sequence head — a value x where x − 1 is not in the set. Interior values are skipped as starting points, so each element is visited a constant number of times and the whole thing stays O(n):

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:        # only launch from sequence heads
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
    return best

When to reach for it

Signals that a hash map or set is the tool:

• "Find a pair/complement" → flavor 2.
• "Anagram", "count", "frequency", "first unique", "majority" → flavors 3–4.
• "Group by anything" → flavor 4: design the signature key.
• "Duplicate", "seen before", "consecutive", "within distance k" → flavor 1 (sometimes storing last-seen index as the value).
• Any O(n^2) idea where the inner loop merely asks "does X exist / how many X so far."

When you're stuck on an array problem, the single highest-value question to ask yourself is: "would a hash map help?" More often than not, it would.