The Pattern Map: Reading Problem Signals
The master decision flowchart: signal words like 'sorted', 'shortest', 'all combinations', or 'top k' and which pattern each one points to. Pattern recognition is the real interview skill.
The real skill isn't solving — it's recognizing
There are thousands of interview problems but only about twenty underlying patterns. Strong candidates aren't faster thinkers; they've trained themselves to read a problem statement and hear which pattern it's quietly describing. Problem writers can't avoid leaving fingerprints — words like "sorted," "shortest," "all combinations," and "top k" each point at a specific tool.
This lesson is the master map. You won't have learned every pattern on it yet — that's fine. The goal is to install the habit of translating signal words into pattern names, so that as you learn each pattern in later modules, it clicks into a slot that already exists.
The signal table
| When the problem says... | Reach for | Because |
|---|---|---|
| "sorted array" + find a value or boundary | Binary search | each comparison discards half |
| "sorted" + pair/triple with target sum, "palindrome", "in-place" | Two pointers | walk inward, eliminating candidates |
| "substring", "contiguous subarray", "longest/shortest such that..." | Sliding window | stretch and shrink one window in O(n) |
| "sum of a range", "how many subarrays sum to k" | Prefix sums | precompute once, answer in O(1) |
| "have I seen X", "count occurrences", "group by", "anagram" | Hash map / set | O(1) lookup replaces the inner loop |
| "next greater/smaller element", "days until warmer" | Monotonic stack | evictions reveal each element's answer |
| "maximum/minimum of every window of size k" | Monotonic deque | front card is always the answer |
| "top k", "k closest", "k most frequent", "kth largest in a stream" | Heap | keep only the k best, O(n log k) |
| "kth largest" once, rest unsorted is fine | Quickselect | partition and discard half, O(n) average |
| "median of a stream" | Two heaps | the middle sits between two balanced halves |
| "merge k sorted lists/arrays" | K-way merge | a size-k heap picks the global next |
| "shortest path", "fewest moves" (no weights) | BFS | explores in distance order |
| "cheapest/shortest path" (weighted edges) | Dijkstra | greedy expansion with a min-heap |
| "count islands", "connected regions", "all paths exist?" | DFS | exhaust reachability one branch at a time |
| "all combinations/permutations/subsets", n ≤ ~20 | Backtracking | build, prune, undo |
| "prerequisites", "must come before", "task order" | Topological sort | peel off zero-dependency nodes |
| "are these connected yet?" as edges arrive | Union-Find | near-O(1) group merging |
| "prefix", "starts with", "autocomplete" | Trie | walk the word, not the dictionary |
| "how many ways", "min/max over sequential decisions" | Dynamic programming | reuse subproblem answers |
| linked list + "cycle", "middle", "O(1) space" | Fast & slow pointers | the runners meet or find the midpoint |
| "intervals", "meetings", "overlap", "booked" | Sort + sweep | sort by start, then merge or count |
| "numbers in range 1..n", "find missing/duplicate", O(1) space | Cyclic sort | every value has one home index |
| "every element appears twice except one" | XOR / bit tricks | pairs cancel to zero |
| "minimize the maximum...", "least capacity/speed so that..." | Binary search on the answer | guess a value, check feasibility |
The four-question triage
When no keyword jumps out, run this quick interrogation:
1. What shape is the input? Array or string → think two pointers, sliding window, hashing, sorting. Linked list → pointer surgery, fast & slow. Tree or graph → DFS/BFS. Intervals → sort and sweep. A stream you can't store → heap.
2. What is the ask? Find one thing → search patterns. Find the best thing → greedy, DP, or heap. Count the ways → DP. Enumerate all of something → backtracking. Yes/no about reachability → DFS/BFS/Union-Find.
3. Which signal words appear? Scan the table above. "Contiguous" alone nearly always means sliding window or prefix sums. "At most k distinct" is a sliding window. "Any order" removes sorting pressure.
4. What do the constraints allow? This is the tiebreaker. n up to 10^5 demands O(n log n) or better — rule out nested loops. n ≤ 20 practically announces backtracking. A required O(1) space rules out the hash map and points at pointers or bit tricks.
Two worked reads
"Given meeting time intervals, find the minimum number of conference rooms required." Shape: intervals — sort and sweep territory. Ask: a minimum count of concurrent things. Read: sort the times, sweep left to right counting how many meetings are open at once; the peak is the answer. Pattern named in under a minute, before any code.
"Find the length of the longest substring with at most 2 distinct characters." "Substring" → contiguous → window. "Longest ... such that condition" → the grow-and-shrink variant. "At most 2 distinct" → the window's rule, tracked with a small frequency map. That's the whole plan: expand right, shrink left when a third character appears, record the best length.
Train the reflex
Make this a ritual for every practice problem, before writing code:
- Say the signals out loud: "sorted array, pair with target sum, O(1) space required."
- Name the pattern they point to: "opposite-end two pointers."
- Sanity-check it on a five-element example before committing.
When a problem seems to match two patterns, the constraints usually break the tie — and some problems genuinely compose two patterns (a sliding window whose state is a hash map, a DFS that fills a memo table). The map isn't a cheat sheet to memorize; it's a reflex to build. Each module ahead drills one region of it until the translation happens without thinking.