Trade memory
for a time machine

Every slow array solution has the same disease: it keeps re-visiting the past. “For each element, scan everything before it” — that inner scan is you walking back through data you already read once, because you didn't write anything down. Do that n times and you've bought yourself O(n²) — n scans of up to n elements.

The hash map is the cure, and the deal is stark: spend O(n) memory to record what you've seen, and every question about the past collapses to O(1). Insert: constant. Lookup: constant. Delete: constant. It's a time machine with a storage fee — you never re-scan history, you just ask it.

That's the entire pattern. The craft — the part interviewers actually probe — is choosing what the key is and what the value is. This chapter is really a tour of four key choices:

• Key = the value itself, no payload → a set. “Have I seen this?” — Contains Duplicate Easy.
• Key = the complement you're waiting for → Two Sum Easy.
• Key = the value, value = a count → frequency maps. Valid Anagram Easy, Top K Frequent Medium.
• Key = a canonical form shared by everything equivalent → Group Anagrams Medium.

Contains Duplicate Easy: does any value appear twice? Chapter 3 solved this three ways as a complexity demo; here's the same trio read as a pattern decision:

• Nested scan — for each element, re-read everything before it. O(n²). The disease.
• Sort first — duplicates become neighbors, one walk finds them. O(n log n) — sort once, then walk. Decent, but it mangles the original order and buys nothing extra.
• A set — one pass, ask-then-insert. O(n) time, O(n) space. Four lines, and the four lines are the whole hashing pattern in miniature.

Note the shape of the winning loop, because every solution in this chapter repeats it: look up first, then insert. Ask “is x already in the set?” before adding x — flip the order and every element happily matches itself. That off-by-one-in-time bug has sunk real interviews.

Two Sum Easy is the complement flavor: for each x, the question isn't “is x here?” but “has target − x already walked past?” Store every value you've seen (with its index, since the problem wants indices); each new element asks one O(1) question about its partner.

Below, both solutions run on the same twelve-element input, one operation per tick. The brute force grinds through pairs; the hash map reads each element once, asks about its complement, and files itself in the seen map. Watch the counters — this gap is what O(n²) vs O(n) feels like at n = 12. At n = 10⁵, the gap is a coffee break versus a lifetime.

One more detail worth saying out loud in the room: the map stores value → index, and because we look up before we insert, an element can never claim itself as its own partner — but a legitimate duplicate pair like [7, 7] with target 14 still works, because the first 7 is already filed when the second one asks. The pattern handles the edge case for free; mention it and collect the verification points from Chapter 1's scorecard.

Promote the map's value from “exists” to “how many” and a second family opens up. Valid Anagram Easy: are two words rearrangements of each other? Don't compare arrangements — take a census. Count the letters of s up, count the letters of t down, and check the ledger reads zero everywhere. One map, two passes, O(n).

The census idea scales past yes/no questions. Top K Frequent Elements Medium starts the same way — one O(n) counting pass — and then becomes a selection problem on the counts. You can sort the census (O(n log n) — sort once, then take k), keep a heap of size k, or bucket counts by frequency for a full O(n). The counting half never changes; only the selection half does. We'll meet the heap version properly in Chapter 14, where this exact problem makes its second appearance.

What makes counting problems interview favorites is that the naive alternatives are so tempting: sorted(s) == sorted(t) is a correct one-liner for Valid Anagram, and saying so is fine — then note it pays O(n log n) for a question a census answers in O(n). Stating the cheaper alternative unprompted is exactly the “names the pattern” dial from Chapter 1.

Group Anagrams Medium: given a list of words, gather the anagrams into groups. The instinct that must not fire is “compare every word with every other word” — that's O(n²) pair checks, the re-scanning disease in a new costume.

The pattern move: find a canonical key — a fingerprint that all equivalent items share and no others do. For anagrams, sort the letters: "eat", "tea", "ate" all become "aet". Now nothing is ever compared to anything; each word computes its own key and files itself. Grouping is just a hash map from key to list — one pass, and the groups assemble themselves.

In FP terms this is groupBy with a well-chosen projection — you're quotienting the list by an equivalence relation, and the canonical key is the representative. Once you see it that way, a whole family of “group the equivalent things” problems becomes one design question: what's the fingerprint? Sorted letters work; a 26-slot letter count works even better (no sort, O(k) per word) — that upgrade is in this chapter's code card.

Product of Array Except Self Medium looks like a division one-liner: total product divided by nums[i]. The problem statement bans division — and it's not being precious. One zero in the input and the total product is 0, dividing by the zero element is undefined, and the trick collapses. The ban is the puzzle.

The pattern answer reads like an assembly line: everything-except-me is (product of everything to my left) × (product of everything to my right). So run the line twice. Pass one moves left→right carrying a running prefix product, writing “product of my left side” into each output cell. Pass two moves right→left carrying a suffix product, multiplying it into each cell. Two passes, one running carry each: O(n) time, O(1) extra space beyond the output — the follow-up answer interviewers fish for.

This is your first taste of the precompute once, answer forever idea: a running product is just a prefix sum wearing multiplication. Chapter 7 builds the full machine — prefix sums, range queries, and the prefix+hash-map combo that cracks Subarray Sum Equals K.

Three footnotes separate “knows the trick” from “knows the tool”, and interviewers love asking about all of them:

• O(1) is amortized, not sworn. Hashing buckets collide; a table resize occasionally costs O(n); an adversarial input can degrade lookups. Say “expected O(1), amortized” once and you've shown you know what's under the hood — Chapter 3's amortized picture applies verbatim.
• Keys must be hashable — and immutable. In Python, a list can't be a dict key; convert to a tuple (the code card does exactly this for the 26-count fingerprint). Mutating an object after using it as a key strands the entry in the wrong bucket — a bug that no test catches and every code reviewer fears.
• Hashing forgets order. A hash map can't answer “what's the smallest key ≥ x?” or “give me a range” — it traded order away for speed. Ordered questions belong to sorting and binary search (Chapter 9); range-sum questions to prefix sums (Chapter 7).

And the strategic footnote: when the input is already sorted, hashing is often the wrong bid. Sortedness is information you've been handed for free, and Chapter 5's two pointers spend it to get O(1) space where a map pays O(n). Two Sum II — the sorted sequel — exists precisely to test whether you notice that.

Stack the chapter's problems side by side and the repetition is almost embarrassing: one pass over the input; a map interrogated and then updated at each element; the answer either found mid-pass (Two Sum) or read off the map afterward (counts, groups). Only two design decisions ever changed — what is the key? and what is the value? Everything else was the same eight lines.

That's why this pattern goes first in Part II. It's the highest-frequency shape in the bank, it's the default “unstick move” when you have no idea (Chapter 2: try a hash map is literally on the stuck list), and it composes with nearly everything downstream: prefix + hash map in Chapter 7, hash + doubly-linked list for LRU Cache in Chapter 10, census + heap in Chapter 14.

The pattern, as a whiteboard skeleton:

1. 1Hear the tell — “seen before / count how many / find the pair / group the equivalent” — and say “hash map” out loud before touching the marker.
2. 2Choose the key: the value itself, the complement you're waiting for, or a canonical fingerprint.
3. 3Choose the value: nothing (a set), an index, a count, or a list of members.
4. 4One pass over the input; for each element, look up first —
5. 5— then insert or update. Lookup-before-insert is what stops elements from partnering with themselves.
6. 6Emit the answer: mid-pass on a hit, or from the map after the pass (values, groups, top-k).
7. 7State the trade: O(n) time bought with O(n) space, expected/amortized — and whether sorted input would change your bid.
8. 8Test the classics: empty input, single element, duplicates, and the pair that's the same value twice.

The flagship. Group Anagrams Medium is the chapter's whole argument in one function: no word is ever compared to another word. Each word computes its own canonical key and mails itself to the right bucket — the hash map is the postal system. Version one keys on sorted letters, O(n·k log k) for n words of length k. Version two upgrades the fingerprint to a 26-slot letter census — O(n·k), no sorting — and shows the hashable-key rule from Section 7 in action: the count array must become a tuple (Python) or stay an immutable Vector (Scala) before it may serve as a key.

Read the Scala tab for the punchline: groupBy is the pattern, shipped in the standard library. The interview version just writes the loop that groupBy hides.