L05 · Hashing — Your Default Weapon

Series: LeetCode — From Basics to Interview-Ready · Session 5 / 65 · Phase 0 · Foundations

What this pattern IS — remembering what you have seen

A huge class of problems reduces to: for the current element, has some related element appeared before? "Is its partner here?" "Have I seen this value?" "How many times did this occur?"

The naive answer is a nested loop: for each element, scan the rest looking for the match — O(n^2). But scanning is wasteful because you re-examine the same elements over and over. The fix is to remember: as you pass each element, drop it into a hash map. Then when a later element needs a partner, it does not scan — it asks the map, which answers in O(1) average time.

You are spending memory (the map) to buy speed (the O(1) lookup replacing an O(n) scan). That single trade — memory for time — is the most common first optimisation in all of algorithms, and hashing is how you make it.

The naive version and its cost

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):     # scan the rest for the partner
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
# O(n^2): every element scans the remaining elements.

The inner scan is the waste. Each element's partner, if it exists, is a specific value (target - nums[i]). We should be able to look that value up directly instead of scanning for it.

The templates — annotated

Template A — complement lookup (Two Sum shape)

def two_sum(nums, target):
    seen = {}                        # value -> index we saw it at
    for i, x in enumerate(nums):     # single pass, O(n)
        need = target - x            # the specific partner that completes x
        if need in seen:             # has the partner appeared already? O(1) avg
            return [seen[need], i]
        seen[x] = i                  # remember x so a FUTURE element can find it
    return []

The order matters: check for the partner before inserting x, so a value never pairs with itself.

Template B — seen-set for existence / dedup

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:                # O(1) membership
            return True
        seen.add(x)
    return False

Template C — frequency map for counting

from collections import Counter, defaultdict
 
counts = Counter(nums)               # {value: how many times}
groups = defaultdict(list)           # {key: list of items with that key}
for i, x in enumerate(nums):
    groups[compute_key(x)].append(i)

Memory technique — "look before you sign in"

The bug that eats beginners is pairing an element with itself, or inserting before checking. Peg the correct order as a doorway ritual: look before you sign in. You glance at the guest list (lookup) first, and only then write your own name (insert). If you sign in first, you might "find" yourself as your own partner.

Reinforce it with the code shape — the loop body is always the same two lines in the same order:

if partner_of(x) in seen:  ->  found it
seen.add / seen[x] = ...   ->  now record x

Lookup on top, insert on the bottom. If you ever write the insert first, the ritual is broken.

What interviewers actually ask

Hashing underlies more interview problems than any other single idea. These are the ones where recognising 'this is a hash problem' is the whole battle:

• Two Sum (1) · Amazon, Google, Meta (Easy) — probes: complement lookup in one pass; the canonical hashing problem. Follow-up: "sorted input, O(1) space?" → two pointers (167).
• Contains Duplicate (217) · Amazon, Adobe (Easy) — probes: seen-set existence check. Follow-up: "within a window of k indices? (219)."
• Valid Anagram (242) · Amazon, Bloomberg (Easy) — probes: frequency-map equality. Follow-up: "unicode / streaming input."
• Group Anagrams (49) · Amazon, Uber (Medium) — probes: hashing by a computed signature (sorted string or count tuple). Follow-up: "remove the sort from the key."
• Subarray Sum Equals K (560) · Meta, Amazon (Medium) — probes: prefix-sum COUNT map — the subtle case where sliding window fails because of negatives. Follow-up: "count vs existence; why not two pointers."
• Longest Consecutive Sequence (128) · Amazon, Google (Medium) — probes: a set turns O(n log n) sort into O(n); start-of-run detection. Follow-up: "prove it is O(n), not O(n^2)."
• Two Sum II — Input Array Is Sorted (167) · Amazon, Microsoft (Medium) — probes: recognising that sorting lets you DROP the map for two pointers. Follow-up: "why is O(1) space possible now?"

Worked example 1 — Two Sum (the archetype)

Problem in plain words: Return indices of the two numbers in nums that add to target. Exactly one answer exists.

Brute + cost. Nested loop over all pairs — O(n^2). Fine for tiny n, times out at 10^5.

Insight. The partner of x is exactly target - x. Remember each value's index in a map; when a later value's partner is already in the map, you have the pair.

def two_sum(nums, target):
    seen = {}                            # value -> index
    for i, x in enumerate(nums):
        need = target - x                # the one value that completes x
        if need in seen:                 # partner already seen? O(1) avg
            return [seen[need], i]        # return earlier index, then current
        seen[x] = i                      # record x for future partners
    return []
# Time O(n), space O(n).

Complexity. O(n) time, O(n) space. We paid memory (the map) to remove the inner scan.

Follow-up. "The array is sorted — do it in O(1) extra space." Drop the map; converge two pointers from the ends (L07):

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1                      # need a bigger sum -> move left pointer up
        else:
            hi -= 1                      # need a smaller sum -> move right pointer down
    return []
# O(n) time, O(1) space — no hash map needed once sorted.

from collections import defaultdict
 
def count_pairs(nums, target):
    seen = defaultdict(int)              # value -> how many times seen so far
    pairs = 0
    for x in nums:
        pairs += seen[target - x]        # every earlier partner forms a new pair
        seen[x] += 1                     # record x AFTER counting (look before sign in)
    return pairs
 
print(count_pairs([1, 5, 3, 3, 3], 6))   # pairs summing to 6: (1,5),(3,3)x3 -> 4

Worked example 2 — Subarray Sum Equals K (the prefix-sum map)

Problem in plain words: Count the contiguous subarrays whose elements sum to exactly k. Values may be negative.

Brute + cost. Try every subarray, sum it — O(n^2) or O(n^3). Too slow, and sliding window fails here because negatives break monotonicity.

Insight. Let prefix[i] = sum of the first i elements. A subarray (j, i] sums to k exactly when prefix[i] - prefix[j] == k, i.e. prefix[j] == prefix[i] - k. So as you sweep, count how many earlier prefixes equal prefix - k — a hash count map, not a set.

from collections import defaultdict
 
def subarray_sum(nums, k):
    count = defaultdict(int)
    count[0] = 1                         # empty prefix: sum 0 seen once
    prefix = 0
    result = 0
    for x in nums:
        prefix += x                      # running prefix sum
        result += count[prefix - k]      # how many earlier prefixes complete a k-sum
        count[prefix] += 1               # record this prefix for the future
    return result
# Time O(n), space O(n).

Complexity. O(n) time, O(n) space. The count[0] = 1 seed handles subarrays that start at index 0.

Follow-up. "Why not a sliding window?" Because negatives mean growing the window can decrease the sum, so there is no monotonic expand/contract rule — the prefix-count map is required.

Where this shows up in production

Hash maps are the backbone of real systems: caches (key → value in O(1)), database indexes and joins (hash-join builds a map of one table then probes it with the other — exactly the "build a guest list, then look each up" move), deduplication of events by id, and rate limiters keying on a client id. The Two Sum trick — "remember what you have seen so a later item finds its partner in one lookup" — is structurally identical to a streaming hash join. The interview loves it because it is a miniature of a technique you will use for the rest of your career.

Practice queue

Solve, and for each say aloud what the KEY is and what you look up.

• Two Sum (1) — Easy · complement lookup. (spaced-repeat anchor: +7d)
• Contains Duplicate (217) — Easy · seen-set.
• Valid Anagram (242) — Easy · frequency map.
• Group Anagrams (49) — Medium · hash by signature.
• Two Sum II — Input Array Is Sorted (167) — Medium · when to DROP the map.
• Subarray Sum Equals K (560) — Medium · prefix-sum count map. (spaced-repeat anchor: +21d)
• Longest Consecutive Sequence (128) — Medium · set turns sort into O(n).