Hash Map

Reader guide and study workflow · Complete course map

In unsorted values [8,2,6,9,5], find two distinct positions totaling 7. The answer uses indices 1 and 4. What can you remember after each position so that you do not scan all earlier positions again?

Derive the question a map must answer

A pair-enumerating specification tests every earlier index for every new value. That is correct, but at index i it repeats the question “has value target-nums[i] appeared?” A set would answer existence; because the result needs positions, the stored value must include an earlier index.

Before reading 5 at index 4, a map can hold 8→0, 2→1, 6→2, 9→3. The complement is 2, whose stored index is 1. Lookup must happen before inserting the current value: on [4,4], target 8, the first 4 has no earlier partner and the second has exactly one. Inserting first could manufacture an illegal self-pair.

Sorting could support endpoint elimination, but then original indices must travel with their values. A map preserves encounter order and the required index witnesses directly, using extra space. That tradeoff follows from the interface, rather than from declaring hashing universally faster.

Now change the task to constructing a note from available letters. An earlier index is no longer the useful value; a remaining count is. Change it again to grouping anagrams, and the key must represent a whole multiset. The workshop asks what remembered information means in each case, including what a weak key or one-way mapping loses.

Prerequisites and readiness

Know Go map lookup with the comma-ok form, comparable key types, frequency counts, and the distinction between a set and a multiset. Recognize expected-time lookup as an assumption, not a worst-case proof.

Reasoning workshop: the key is the specification

Four different meanings of remembered information

A frequency map stores remaining resources; a position map stores an earlier witness; a signature map stores an equivalence class; a visited set stores whether a complete state has occurred. These meanings imply different update orders. Ransom Note consumes magazine counts and permits leftovers. Valid Anagram requires all final differences to be zero. Two Sum looks up a complement before recording the current index so a single occurrence cannot pair with itself.

For [3,3], target 6, the first 3 must be stored without finding a partner. The second 3 then finds index 0 and returns [0,1]. This is different from Two Sum II, whose sorted input supports endpoint elimination and whose output is one-based. Changing data structures does not remove interface obligations.

Bijections require both directions

A forward map allows a→dog and b→dog, but a one-to-one pattern does not. The reverse map dog→a blocks the second association. For isomorphic strings ab and aa, each source byte can appear consistent in isolation while the combined mapping is invalid. Trace both maps as pairs are accepted; a map that contains only one direction cannot prove injectivity.

Tokenization comes before this proof in Word Pattern. The supplied implementation splits on literal single spaces, not general whitespace. Ordinary inputs use nonempty words separated by one space. At the legacy empty boundary, strings.Split produces one empty token: empty pattern with empty text is false, while a one-byte pattern with empty text is true. Those results are retained here and explicitly distinguished from a redesigned zero-word interpretation.

Canonicalization must preserve exactly the desired equivalence

Anagram groups can use a sorted spelling or a 26-count key. The reference uses a comparable [26]int array directly as its key. If you serialize counts instead, use delimiters so adjacent numeric fields cannot become ambiguous. Empty strings still require key construction and output entries, so complexity must include the number of strings N as well as their total character count C. An all-empty input has C=0 but still takes O(N) work. Duplicate occurrences are not removed; the output is a grouping of the input list, not a set of unique spellings.

Go map iteration does not promise group ordering. Tests should normalize the outer groups and, where the contract permits, their members. They must still preserve multiplicity. Dropping duplicate entries before comparison would hide a real bug.

A set alone does not guarantee linear work

For Longest Consecutive, [1,1,1,2,3,4] should expand the run beginning at 1 once, not once per occurrence. Building a set but iterating the original slice for starts allows duplicate minimum values to repeat long walks. Iterate distinct set keys instead. Every maximal run has one predecessor-free start, and every distinct value belongs to exactly one run; that charging argument proves linear expected total probes.

Cycles are about whole states

Happy Number repeatedly applies a deterministic digit-sum transformation. For 19, the path is 19→82→68→100→1. For a non-happy input, a repeated integer state traps the process in the same future forever. The finite-state argument follows because a ten-digit number maps to at most 810. A visited set is the easiest model to debug; the supplied reference uses Floyd's two-speed pointers to retain constant auxiliary space. Do not describe the set version as constant-space merely because this particular numeric domain is bounded.

Pattern reference

Use these summaries after deriving the state and the reason each update is safe. The patterns name decisions already justified above.

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]--
// Containment: fail when a requested count becomes negative.
// Equality: after processing both complete strings, require every count == 0.

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
if len(s) != len(t): return false
for i in 0..len(s)-1:
    a = s[i], b = t[i]
    if a in map1 and map1[a] != b: return false
    if b in map2 and map2[b] != a: return false
    map1[a] = b
    map2[b] = a
return true

An absent key imposes no constraint yet. For the first pair p→q, both maps are empty, so establish both directions. In Go, use the comma-ok lookup to distinguish absence from a stored zero byte. Comparing a missing entry's default value with q would reject this valid first pair. For Word Pattern, compare the token count with the pattern length before pairing bytes with words.

Problems:

• isomorphic-strings.
• word-pattern.

---

Pattern C: Complement lookup

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

Invariant: the map stores value -> a usable earlier index. The supplied assignment replaces an earlier index for a repeated value, so it is not necessarily the earliest.

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 distinct keys of set:
    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.

Reconstruction lab and answer key

Close the worked examples before attempting these new cases. Rebuild the state and justify the update, then compare with the model answer.

Ransom Note

Rebuild the difference between a containment check and an equality check on note "xy" and magazine "xxyz". Which leftover counts are legal?

Model answer

After consuming x and y, one x and one z remain. Containment accepts because no demand exhausted its available budget. Anagram equality rejects because those leftover counts are nonzero.

Isomorphic Strings

How would an all-zero mapping table distinguish an unmapped byte from a mapping to ASCII NUL? Give two valid representations.

Model answer

It cannot do so on values alone. Use -1 for unmapped entries, or store a separate presence array/comma-ok map result. NUL is a real ASCII byte, so zero is not an unambiguous absence sentinel.

Word Pattern

Predict WordPattern("ab", "same same") and WordPattern("aa", "same same"). Name the map entry that decides each.

Model answer

The first is false because same is already mapped back to a when b arrives. The second is true because both forward a→same and reverse same→a remain consistent. Word count is two in both cases, so it does not decide this pair.

Valid Anagram

With a simultaneous difference scan for s="az" and t="za", may you reject as soon as the count for z becomes -1? Explain the final state.

Model answer

No. After index 0, a has +1 and z has -1. Index 1 adds z and subtracts a, restoring both to zero. Intermediate deficits are allowed before all source bytes have been added.

Group Anagrams

Choose a Go key type for lowercase anagrams that needs neither sorting nor decimal serialization. Why is a slice unsuitable while your choice works?

Model answer

Use [26]int. Arrays of comparable elements are comparable and usable as map keys; []int slices are not. Equal arrays mean equal letter counts. The map resolves any internal hash collisions by key equality, so a full count vector remains exact.

Two Sum

A solution returns [4,1] for nums=[8,2,6,9,5], target=7. Is its order invalid? Which three conditions must a test actually verify?

Model answer

It is valid: indices 4 and 1 are in bounds, distinct, and their values sum to 7. This interface allows either order. Ascending pair order is a reference choice, while Two Sum II separately requires i<j and one-based indices.

Happy Number

Why does deterministic state repetition justify rejection only when the repeated cycle excludes 1? Reconcile this with 1 being a repeated state too.

Model answer

The successor of 1 is 1, so reaching it is success even though it forms a cycle. A repeated state in another cycle has the same future forever and cannot escape to 1. Check success separately from non-1 cycle detection.

Longest Consecutive Sequence

Input values are [7,5,5,6,20,21]. Name every expansion start and account for the total number of successful extension probes.

Model answer

Distinct starts are 5 and 20, because 4 and 19 are absent. Their runs are 5,6,7 and 20,21, giving three successful extension probes in total. Duplicate 5 does not create another walk when the outer loop iterates set keys.

Problems in this module

• Ransom Note
• Isomorphic Strings
• Word Pattern
• Valid Anagram
• Group Anagrams
• Two Sum
• Happy Number
• Longest Consecutive Sequence

Interactive checkpoint

Open the Hash Map quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable