Hashing — Your Default Weapon

Review boundary and corrected contracts

Look up the complement before storing the current item, so an index cannot match itself. The prefix-count base {0:1} counts ranges starting at index zero; counts, not a set, preserve repeated-prefix multiplicity. Hashing uses space proportional to distinct stored keys, not invariably n.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Learn the complement-lookup skeleton and the general 'trade memory for time' move: remember what you have seen in a hash map so a future element can find its partner with expected O(1) bounded-key lookup, replacing repeated scans with one pass.

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

Prerequisites: L02 (why dict/set lookups are O(1) average) and L03 (Counter, defaultdict). This session turns those tools into a reflex.

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). This memory-for-time trade is worth considering when repeated equality lookups dominate. It is not the first or best move for every quadratic algorithm; changing the recurrence, ordering or invariant may matter more.

Real: Instead of asking every person at a party "are you my friend Sam?" one by one, you keep a guest list at the door. When someone new arrives you glance at the list — one look tells you if Sam is already inside. The list costs paper (memory) but saves you asking everyone (time).

Instead of scanning the array for each element's partner (O(n) each), you keep a hash map of everyone seen. A lookup is one glance (O(1) average) instead of a full scan.

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.

Question: Why does storing seen elements in a hash map turn a quadratic scan into a single linear pass?

Premise: For element x, the thing that completes it is a KNOWN value (e.g. target - x).

Because: The relationship is fixed, so we do not need to search — we need to check existence of one specific value.

Premise: A hash map answers 'is value v present, and where?' in O(1) average.

Because: Suitable hashing keeps expected collision-probe work bounded; computing the hash and comparing keys have their own costs.

Premise: If we insert each element as we pass it, then when we reach x its partner (if earlier) is already in the map.

Because: We only ever look BACK at elements we have already inserted.

Premise: With bounded-cost arithmetic and suitable hashes, each element does expected O(1) work and we make one pass.

Because: n elements times O(1) is O(n) total.

Conclusion: For integer pair lookup under this cost model, expected O(1) dictionary operations yield expected O(n) total time. Memory is O(u) for u stored distinct values; worst-case collision behavior can make total time O(n²). A correctness proof still needs the earlier-indices invariant.

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:                # expected O(1) membership
            return True
        seen.add(x)
    return False

Template C — frequency map for counting

from collections import Counter, defaultdict
 
nums = [1, 2, 2, 3]
compute_key = lambda x: x % 2          # illustrative grouping by parity
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)

These templates share a lookup table, but they do not all give time the same meaning. A completed frequency map describes the whole input; the complement and seen-set loops describe only earlier elements. Return to that second view for the guest-list picture: looking before inserting is what makes a match refer to a different, earlier entry. Counting and grouping reuse the storage tool, not necessarily that lookup-before-insert ritual.

Name: The guest list at the door

Picture: One pass down the array. Beside it sits a hash map — the guest list. Each element you pass, you (1) glance at the list to see if its partner already checked in, then (2) add yourself to the list. Look before you sign in, so you never match yourself.

• Decide what the KEY is (the value, the complement, a computed signature).

• Look up the partner/existence BEFORE inserting the current element.

• Insert the current element so future ones can find it.

• With suitable bounded-cost keys: expected O(n) time and O(u) stored-key space, u <= n.

Trigger: Problem looks O(n^2) with a nested search for a related element, OR asks 'has this appeared', 'how many', 'find the pair/complement', 'group by'.

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.

Myth: A hash map lookup is guaranteed O(1), so hashing is always the fastest option.

Hash lookup has expected constant probe cost under suitable assumptions. Extra storage is O(m) for m distinct stored keys, at most O(n); hashing long keys and adversarial collisions must be accounted for separately.

Why: A hash map trades memory for time. When the input is already sorted, two pointers achieve the same result in O(1) extra space; when you need order, a sort or heap may beat a map. 'Default weapon' means try it first, not that it always wins.

Test: If the problem says O(1) extra space AND the array is sorted, the hash map is the wrong tool — reach for two pointers (L07) instead.

What reviewers actually ask

These practice problems use different key and multiplicity invariants. Recognizing a possible hash table is only the start of the argument:

• Two Sum (1) · Practice selection. (Easy) — probes: complement lookup in one pass; the canonical hashing problem. Follow-up: "sorted input, O(1) space?" → two pointers (167).
• Contains Duplicate (217) · Practice selection. (Easy) — probes: seen-set existence check. Follow-up: "within a window of k indices? (219)."
• Valid Anagram (242) · Practice selection. (Easy) — probes: frequency-map equality. Follow-up: "unicode / streaming input."
• Group Anagrams (49) · Practice selection. (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) · Practice selection. (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) · Practice selection. (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) · Practice selection. (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 zero-based indices of two distinct elements summing to target, using bounded integers. The common exercise guarantees one answer; the implementations here also return any valid pair if several exist and [] if none does.

Brute + cost. The distinct-pair loop can examine n(n-1)/2 pairs: Θ(n²) worst-case work with bounded integers. At n=100,000 this is nearly five billion pairs, a strong reason to seek better growth, not a portable timeout theorem.

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 []
# Expected time O(n), space O(n), under suitable bounded-cost keys.

Complexity and proof. At iteration i the map contains only earlier indices. A hit therefore uses two distinct positions; for any existing solution, its later element finds the earlier value. Replacing an earlier index for a duplicate value is safe when any pair is acceptable. Time is expected O(n) and space O(u), u <= n, under suitable bounded-key hashing; collision-heavy behavior can be quadratic.

Follow-up. For an already nondecreasing array, converge two pointers from the ends. If the endpoint sum is below target, that left value paired with any remaining right value is still too small, so discard it; the symmetric argument discards the right endpoint when too large. The function below returns zero-based indices (convert to one-based only if the problem’s output contract asks for that). It does not perform sorting:

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.

Goal: Turn a quadratic into a one-pass hash solution.

Hint: Count pairs (i<j) with nums[i]+nums[j]==target using a frequency map.

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.get(target - x, 0) # no insertion for an unseen queried key
        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

The count map preserves multiplicity: three occurrences of 3 contribute three distinct index pairs for target 6. For a triple-count variant, specify whether distinct index triples or unique value triples are wanted. Fixing one index and counting pairs in its suffix gives an expected O(n²) approach; unique value triples need separate duplicate handling.

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. There are Θ(n²) nonempty subarrays. Recomputing each sum from scratch costs Θ(n³) total; extending a running sum from each starting index costs Θ(n²). Negative values invalidate the usual sum-threshold expand/shrink monotonicity. They do not invalidate every possible window technique.

Insight. Let prefix[i] = sum of the first i elements. The zero-based half-open 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.get(prefix - k, 0)  # count earlier prefixes, without inserting queries
        count[prefix] += 1               # record this prefix for the future
    return result
# Expected time O(n), space O(n), under suitable bounded-cost keys.

Invariant and complexity. Before recording the current prefix, count holds multiplicities of earlier prefix sums, including the empty prefix once. Every matching earlier prefix gives a different nonempty range ending here. Recording the new prefix only afterward prevents counting an empty range when k=0. For [0, 0] and k=0, the two iterations add 1 then 2, giving 3; a set would lose this multiplicity. Expected time O(n), space O(u) for u distinct prefix sums, u <= n+1, with bounded-cost arithmetic/hashing. Huge integers add bit costs. Using .get() prevents missing complement queries from inserting zero-count keys.

Follow-up. In [1, -1, 1] with k=1, valid ranges are [0,1), [0,3) and [2,3). A positive-sum shrinking rule can discard candidates that become valid after adding -1. The prefix-count map handles arbitrary signs; it is a suitable method, not the only conceivable correct algorithm.

Decision: Hash map vs sorting/two-pointers for pair-and-lookup problems.

Name: Hash map

Gain: Expected O(n) time for bounded-key pair lookup; works on unsorted input and retains original indices.

Cost: Up to O(n) extra memory; O(1) is expected, not worst case; no value-sorted ordering. Dictionary insertion order is a different property.

Pick: Unsorted input, need indices, or need counts/grouping.

Name: Sort + two pointers

Gain: The two-pointer scan uses O(1) auxiliary space on already sorted input and can support some closest-pair variants.

Cost: Sorting first adds O(n log n) comparison time and implementation-dependent workspace; Python list.sort may use O(n) temporary storage. To retain original indices, decorate values with indices, adding storage rather than claiming indices must always be lost.

Pick: Input already sorted, memory is tight, or you need ordered scans (3Sum).

Name: Brute nested loop

Gain: No memory, trivial to write.

Cost: Θ(n²) worst-case pair work; exact runtime depends on input and environment.

Pick: Only when constraints guarantee tiny n.

Verdict: Consider hashing for repeated equality lookups, or two pointers when sortedness supplies an elimination proof. If sorting is needed, include its time, workspace and index-preservation costs before claiming an O(1)-space solution.

Where this shows up in production

An in-memory build/probe hash join illustrates the same storage trade: group records from one input by join key, then probe matching groups for the other input. Output multiplicity still matters; a hot key can produce a large cross product. A streaming join additionally needs a policy for retained state, event time and late arrivals, so Two Sum is not a complete streaming-join design. Likewise, keyed caches or deduplication tables need eviction, concurrency and durability decisions that the local map examples do not demonstrate.

You can now…

• Recognise a nested search-for-a-partner loop as a hashing opportunity.

• Write the complement-lookup skeleton with 'look before you sign in' ordering.

• Use a set for existence, a Counter/defaultdict for frequency and grouping.

• Apply a prefix-sum COUNT map for subarray-sum problems (including negatives).

• Explain the memory-for-time trade and when it is NOT worth it.

• Explain why an already-sorted two-pointer scan needs O(1) workspace, while sorting first may not.

Self-check (answer follows each question).

Recall check

Q: In Two Sum, why do you check for the complement BEFORE inserting the current value?

A: So an element never pairs with itself; the map should only contain earlier elements when you look. 'Look before you sign in.'

Q: What is the memory-for-time trade in one sentence?

A: Store up to O(n) distinct keys so suitable bounded-key lookups have expected O(1) cost instead of scanning previous elements; pair search then takes expected O(n) time rather than quadratic worst-case scan work.

Q: Why does a plain sliding window fail on Subarray Sum Equals K?

A: Values can be negative, so growing the window can decrease the sum; there is no monotonic expand/contract rule. Use a prefix-sum count map instead.

Q: When is a hash map the WRONG choice for a pair problem?

A: When O(1) extra space is required and the array is sorted — two pointers achieve it without a map.

Q: For Subarray Sum Equals K, why initialise count[0] = 1?

A: It represents the empty prefix (sum 0), which lets subarrays starting at index 0 be counted.

Q: ★ Hash lookup is 'O(1)'. State the caveat and one situation where it bites.

A: It is O(1) on AVERAGE; worst-case collisions degrade it, and it uses O(m) stored keys, at most O(n), for m distinct recorded values. For the already-sorted pair-sum contract with O(1) workspace, two pointers meet the space requirement without an unbounded map; this is not a universal ranking across tasks.

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).

Next session (L06) gives you UMPIRE — the six-step process that turns twenty blank minutes into a repeatable routine, so hashing and every other pattern gets applied on purpose instead of by luck.

Corrective source notes

• Python 3.14 collections — defaultdict indexing invokes its missing-key factory, while get does not; exact passage rechecked 2026-10-09. Counter equality is not the proof of the prefix-sum algorithm.
• CPython v3.14.0 sorting design — in-place sorting can use linear temporary storage; inspected 2026-10-09.
• Pair and prefix-count correctness follow from the explicit invariants above; local finite oracles test rather than replace those arguments.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.