4.4.0 — Arrays & Hashing: The Pattern

Recognition cue. The brute force is a nested loop where the inner loop asks a question about what you have already seen: "does this appear again", "have I got a matching value", "how many times has this occurred". That inner loop is a lookup, and a lookup belongs in a hash map.

The move. Replace O(n^2) with O(n) time and O(n) space. It is the single most common optimisation in the whole of Part 4.

The skill that separates the easy problems in this group from the hard ones is not using a map — it is choosing what to put in it. Sometimes the key is the value. Sometimes it is a derived fingerprint. Sometimes it is what you still need rather than what you have.

The four templates

# 1. Have I seen this?  → a set
seen = set()
for x in nums:
    if x in seen: return True
    seen.add(x)                       # ← always check BEFORE inserting

# 2. How many of each?  → a map from value to count
count = Counter(items)                # or: count[x] = count.get(x, 0) + 1

# 3. Group by a fingerprint I choose  → a map from key to list
groups = defaultdict(list)
for x in items:
    groups[fingerprint(x)].append(x)  # ← the whole problem is this line

# 4. Store what I NEED, not what I have  → a map from value to index
seen = {}
for i, x in enumerate(nums):
    if (target - x) in seen: return [seen[target - x], i]
    seen[x] = i

Templates 1 and 4 look almost identical and are used for opposite reasons. Template 1 remembers what has happened. Template 4 anticipates what would complete an answer. Being able to say which one a problem needs, out loud, before writing anything, is most of the recognition skill.

The nine problems

#	Problem	The one insight
4.4.1	Contains Duplicate ★	A nested scan asking "have I seen this" is a set lookup
4.4.2	Valid Anagram ★	Anagram means equal counts; ordering is more work than counting
4.4.3	Two Sum ★	Do not search for a pair — compute the partner and look it up
4.4.4	Group Anagrams ★	Design a fingerprint; the map is bookkeeping
4.4.5	Top K Frequent Elements ★	A frequency cannot exceed n, so counts are array indices
4.4.6	Encode and Decode Strings ★	No separator is safe — prefix the length instead
4.4.7	Product of Array Except Self ★	Two passes in opposite directions replace a nested loop
4.4.8	Valid Sudoku	Name each group with an index; (r//3)*3 + c//3
4.4.9	Longest Consecutive Sequence ★	Walk only from run starts, and prove the result is linear

★ marks the Blind 75 subset.

The traps on this pattern

Checking after inserting. In Two Sum and Contains Duplicate, insert after the check, or an element matches itself.

Claiming O(1) space while using a map. A map over an unbounded alphabet is O(k). Only a fixed-size array over a bounded alphabet is O(1), and you should say which assumption you are making.

Mutable objects as keys. Python refuses a list as a dictionary key — TypeError: unhashable type — which is loud and easy to fix with tuple(...). JavaScript accepts an array as a Map key and compares it by identity, so every entry becomes unique and nothing ever matches, with no error at all. The silent failure is the dangerous one. Encode to a string or a number first, and keep a separator in the encoding.

Aliased containers. [[]] * n in Python and new Array(n).fill([]) in JavaScript create one container and n references to it. Use [[] for _ in range(n)] and Array.from({length: n}, () => []).

Using {} where you mean a map. A plain JavaScript object coerces keys to strings, so 1 and "1" collide, and it inherits toString, constructor and friends from the prototype, so obj["constructor"] returns something you never stored. Use Map when keys are data (Chapter 3.6.11 covers this and prototype pollution).

Sorting when counting would do. If you only need frequencies or a maximum, sorting is O(n \log n) for something a single pass gives you.

What the interviewer will push on

"Your solution uses O(n) extra space. Can you do it in O(1)?" Usually the honest answer is "only by sorting, which costs O(n \log n) time and destroys the original indices" — and then you ask whether the input can be modified. Naming the trade instead of guessing is the right move.

"Is your hash lookup really O(1)?" It is O(1) expected. Adversarially chosen keys can force every value into one bucket and degrade a lookup to O(n); real runtimes defend against this by randomising the hash seed (4.3). Most candidates say "yes, O(1)" and stop.

"Why is Longest Consecutive Sequence O(n) and not O(n^2)?" The amortized argument: the inner loop runs only from run-starts, runs do not overlap, and each number belongs to exactly one run. This is the most common follow-up in the group and it is asked because the code looks quadratic.

"What if the values were bounded — say 1 to n?" Then the hash disappears and an array indexed by value replaces it: no hashing, better cache behaviour, and sometimes O(1) space by reusing the input's sign bits as flags. A bounded small value range turns a hash into an array index, and that realisation is what makes the linear solution to Top K Frequent work.

One thing to volunteer: say explicitly what you chose as the key and why. "I am hashing the sorted letters, because two words are anagrams exactly when that matches." That sentence shows you designed the solution rather than recalled it — and every hard problem in this group is a key-choice problem in disguise.

Recall

• The pattern: a nested loop whose inner half is a lookup becomes one loop plus a hash map. O(n^2) \to O(n), paid for in space.
• The skill is choosing the key: the value itself, a derived fingerprint (sorted letters, character counts, difference sequences), or what you still need (target - nums[i]).
• Check before inserting, always, or an element matches itself.
• When the sort key is a bounded small integer, do not sort — index into buckets.
• Two passes in opposite directions replace a nested loop when each answer depends on a prefix and a suffix.
• Length prefixing beats delimiters when the data may contain any character — the same reason HTTP uses Content-Length.
• A nested loop is linear when you can prove each element is touched a constant number of times overall.
• In JavaScript, arrays and objects as Set/Map keys compare by identity; encode to a string or number first.

Next: 4.4.1 Contains Duplicate — the simplest problem in the book, and the one that establishes the check-before-insert discipline every other problem here reuses.