90 — Problem patterns

Most interview questions are one of about fifteen shapes wearing a different story. Recognising the shape in the first two minutes is the difference between solving in twenty minutes and stalling for forty.

Prereqs: 01 · Reading: 7 min · Cards: 8 · Practice: the 20 pattern pages in the study site

The map

This module is a lookup table you run in your head, and it has two levels. The first is a mapping from words in the prompt to a candidate pattern — "contiguous subarray" suggests a sliding window, "next greater element" suggests a monotonic stack, "prerequisites" suggests a topological sort. That mapping is fast and shallow, and it gets you started.

The second level is the justification, and it is what actually gets scored. Saying "this is a sliding window problem" and stopping is worth nothing; the interviewer wants to hear why the window is valid — that expanding the right end can only break the condition and shrinking the left can only fix it. Pattern recognition is the start of the conversation, not the end of it.

The full recognition table lives in the reference card, and every problem in the bank sits behind one of these patterns on the study site, with a plan of attack. This page is the reasoning that connects them.

What decides your score here

Naming the pattern with its justification attached. One sentence for the name, one for why it applies. The second sentence is the one being assessed.

Having a fallback when nothing matches. Three generic questions — what am I recomputing, would sorting help, which structure gives me constant time — reach an approach in almost every case.

Not forcing a pattern that does not fit. Recognising that the shape is nearly sliding window but the values can be negative, so the monotonicity fails, is a stronger signal than confidently applying the wrong tool.

The patterns that carry most of the weight

Hash map is the most frequent by a distance. You store what you have seen so you can answer "what is missing?" in constant time. Its more interesting form is the canonical key: when the task is grouping equivalent things, the craft is finding a function that maps every equivalent input to the same hashable value — for anagrams, a tuple of letter counts rather than a sorted string, because that is linear instead of n log n.

Two pointers needs structure to be valid: sorted input, a palindrome, or a monotonic property. Without one of those, moving a pointer cannot be proven safe. In Container With Most Water the justification is that the area is capped by the shorter line, so any pair using it with a narrower width is strictly worse — which is why discarding it loses nothing.

Sliding window applies when the prompt says contiguous and longest or shortest. The window grows on the right and shrinks from the left whenever the condition breaks, and the reason that terminates in linear time is that both pointers only ever move forward. Its most common failure is negative numbers: with them the sum is no longer monotonic in the window size, and the whole argument collapses — which is why "count subarrays summing to k" is a prefix-sum-plus-hash problem instead.

Binary search does not require a sorted array; it requires a monotonic predicate. Once you internalise that, binary search on the answer stops being a trick. "The smallest speed that finishes in h hours" is a search over speeds where checking a candidate is a linear pass, and "minimise the maximum" is the same shape. Those two phrases are the trigger.

Monotonic stack answers "next greater element" and its variants in linear amortised time, and the amortisation is the part worth saying: each element is pushed once and popped at most once, so a nested while does not make it quadratic.

Heap is for when you need the extreme rather than the order — and for the k largest you want a min-heap of size k, because the thing you need cheaply is the weakest candidate you are holding.

Backtracking is choose, explore, un-choose, and the design decision inside it is the pruning. Dynamic programming is two questions, state and transition, asked out loud before any code. Both are covered properly in modules 09 and 06.

Graph patterns — BFS for fewest steps, DFS for connectivity and cycles, topological sort for ordering, union-find for grouping — are in module 05. The thing to carry here is that grids, dependency lists and word ladders are all graphs, and saying so is half the solution.

Intervals almost always start with a sort, and which key you sort by decides the problem: by start to merge overlapping ones, by end for greedy selection of the maximum non-overlapping set. That second one is counterintuitive and worth remembering — keeping the interval that finishes earliest leaves the most room for everything after it.

Prefix sums turn any range query into a subtraction, and combined with a hash map they answer "how many subarrays sum to k" in linear time. Bit manipulation is signalled by a constant-space constraint: XOR cancels pairs, n & (n-1) clears the lowest set bit. And designing a structure is signalled by a prompt opening with "Design a…" and naming a per-operation complexity — the answer is always two structures combined, each covering the other's weakness.

When nothing matches

Three questions, in this order, and one of them almost always produces an approach.

What am I recomputing? If the same subresult appears repeatedly, the answer is memoisation, prefix sums or DP.

Would sorting help? Sorting costs n log n and frequently unlocks something linear — two pointers, a greedy sweep, an interval merge. Paying n log n to make the rest trivial is usually a good trade.

Which structure gives me what I need in constant time? If the bottleneck is "find the minimum repeatedly", that is a heap. "Have I seen this?" is a hash set. "What came most recently?" is a stack.

Say these out loud when you are stuck. Narrating the search is far better than narrating nothing, and it frequently causes the interviewer to nudge you in the right direction.

Say it

Cover the answers. Out loud, in English.

?What question do you run in the first two minutes?

Which of the fifteen shapes is this? And if none fits: what am I recomputing, would sorting help, which structure gives me constant time?

?What tells you it is a sliding window, and what justifies it?

Contiguous plus longest or shortest. And the justification is that expanding right can only break the condition while shrinking left can only fix it.

?What does binary search actually require?

A monotonic predicate, not a sorted array. That is why binary search on the answer works.

?Why is a monotonic stack linear despite the inner while?

Each element is pushed once and popped at most once, so the total across the pass is bounded.

?Intervals — sort by start or by end?

By start to merge. By end for greedy selection, because finishing earliest leaves the most room.

?You recognise the pattern. Is that the answer?

No, it is the start of the conversation. I still have to say why it applies and what the window, stack or state represents here.

Now do this

Four problems chosen because each one is a different pattern with a justification worth rehearsing. Say the pattern and the reason out loud before writing.

Longest Substring Without Repeating Characters — 20 min. Sliding window; say why the window stays valid.
Daily Temperatures — 20 min. Monotonic stack; say why it is linear.
Koko Eating Bananas — 25 min. Binary search on the answer; say what you are searching over.
Merge Intervals — 15 min. Say which key you sort by and why.

Then work through the pattern pages in the study site, which hold all 130 problems grouped by shape, each with a plan of attack and the English to narrate it:

python3 tools/build_site.py --serve

Stop when you can name the pattern and give its justification within two minutes of reading a prompt, five times in a row.