Hash Map

Hash maps give O(1) expected-time lookups, which turns counting, indexing, and grouping tasks into single passes. Most patterns are about choosing the right key and maintaining an invariant about what the map represents.

Pattern A: Frequency counting

Use when: you need to compare multisets or check availability.

Invariant: map or array counts match the elements seen so far.

Skeleton:

counts = array[26] or map
for ch in s: counts[ch]++
for ch in t: counts[ch]--
if any count < 0: return false

Problems:

• ransom-note.
• valid-anagram.

Pattern B: Bijection mapping

Use when: two sequences must map one-to-one.

Invariant: forward and reverse maps are consistent for all processed positions.

Skeleton:

map1 = map[a]b
map2 = map[b]a
for i in 0..n-1:
    a = s[i], b = t[i]
    if map1[a] != b or map2[b] != a: return false
    map1[a] = b
    map2[b] = a

Problems:

• isomorphic-strings.
• word-pattern.

Pattern C: Complement lookup

Use when: you need two items that sum to a target.

Invariant: map stores value -> earliest index seen so far.

Skeleton:

index = map
for i, x in nums:
    if target-x in index: return [index[target-x], i]
    index[x] = i

Problems:

• two-sum.

Pattern D: Cycle detection with a set

Use when: a process repeats states (digit sums, graph-like transitions).

Invariant: once a value repeats, the process is in a loop.

Skeleton:

seen = set
while n != 1 and n not in seen:
    add n to seen
    n = next(n)
return n == 1

Problems:

• happy-number.

Pattern E: Group by normalized signature

Use when: items are equivalent up to reordering or counting.

Invariant: signature uniquely represents the equivalence class.

Skeleton:

key = sort(word)  // or 26-count signature
map[key].append(word)

Problems:

• group-anagrams.

Pattern F: Expand from sequence starts

Use when: you need the longest consecutive sequence.

Invariant: only start expansion when x-1 is absent.

Skeleton:

set = all nums
for x in nums:
    if x-1 not in set:
        y = x
        while y in set: y++
        best = max(best, y-x)

Problems:

• longest-consecutive-sequence.

When to use Hash Maps (checklist)

• You need fast membership checks or counts.
• You can define a stable key for grouping.
• Order is irrelevant or can be recovered later.

Common failures (checklist)

• Forgetting to enforce a bijection in both directions.
• Using a mutable key (e.g., slice) as a map key.
• Counting with a map when a fixed-size array is faster and simpler.
• Not handling duplicates correctly when grouping.

Problem mapping

• ransom-note: count available letters.
• valid-anagram: count or sort characters.
• isomorphic-strings: two-way mapping.
• word-pattern: bijection between pattern and words.
• two-sum: complement lookup.
• group-anagrams: group by signature.
• happy-number: visited set for cycles.
• longest-consecutive-sequence: expand from sequence starts.