Pattern Recognition Guide
The decision table that maps problem signals and constraints to the right technique — the single most useful page for solving problems you've never seen.
The core idea
Most interview problems are variations of about 25 patterns. Solving an unseen problem is largely recognizing which pattern it is. The recognition comes from three sources:
- The input shape (sorted array, tree, grid, string pairs, intervals…)
- The question's keywords (“longest”, “all combinations”, “minimum steps”, “k-th”…)
- The constraints (n ≤ 20 vs n ≤ 10⁵ vs n ≤ 10⁹)
Test yourself with the pattern quiz.
Step 1: Read the constraints
| n up to | Target complexity | Suggests |
|---|---|---|
| 10–12 | O(n!) | permutations, brute force |
| 20–25 | O(2ⁿ · n) | subsets, bitmask DP, meet in the middle (n ≤ 40) |
| 100–500 | O(n³) | interval DP, Floyd-Warshall |
| 1,000–5,000 | O(n²) | 2D DP, all pairs |
| 10⁵–10⁶ | O(n log n) or O(n) | sorting, heaps, binary search, two pointers, hashing, prefix sums, greedy |
| 10⁹–10¹⁸ | O(log n) or O(1) | binary search on answer, math, matrix exponentiation |
Step 2: Match the signals
Arrays and strings
| If the problem says… | Try | Topic |
|---|---|---|
| pair/triplet with a sum, sorted input | two pointers | Two Pointers |
| pair with a sum, unsorted, need indices | hash map complement | Hashing |
| longest/shortest contiguous subarray/substring with a condition | sliding window | Sliding Window |
| subarray sum equals k (negatives allowed) | prefix sum + hash map | Prefix Sums |
| many range-sum queries, no updates | prefix sums | Prefix Sums |
| many range updates, then read | difference array | Prefix Sums |
| range queries with updates | Fenwick / segment tree | Range Queries |
| next greater/smaller element, spans, histogram | monotonic stack | Stacks |
| max/min of every window | monotonic deque | Stacks |
| k largest / smallest / most frequent | heap (or quickselect) | Heaps |
| in-place, O(1) extra space, values in 1..n | index as hash / cyclic sort | Hashing |
| anagram, frequency, duplicates | counting array / hash map | Hashing |
| “find the element” in O(log n) | binary search | Binary Search |
| minimum X such that feasible(X) / minimize the maximum | binary search on answer | Binary Search |
| every element twice except one; subsets of ≤ 20 items | bit manipulation | Bits |
| pattern occurrence, periodicity | KMP / Z / hashing | Strings |
Linked lists
| Signal | Try |
|---|---|
| cycle, middle, k-th from end | fast & slow pointers |
| reverse (all / part / in groups) | three-pointer reversal |
| head may change | dummy node |
| merge sorted lists | merge routine; k lists → heap |
Trees
| Signal | Try |
|---|---|
| level by level, minimum depth, right view | BFS |
| height, diameter, balanced, path sums | DFS returning values (post-order) |
| constraints passed from ancestors (BST validity, max on path) | DFS with parameters (pre-order) |
| BST → sorted order, k-th smallest | in-order traversal |
| lowest common ancestor | recursive LCA (or BST walk) |
| choose nodes with neighbour constraints | tree DP returning multiple states |
Graphs and grids
| Signal | Try | Topic |
|---|---|---|
| connected regions, islands, flood fill | DFS/BFS | Graphs |
| shortest path, unweighted / minimum steps | BFS | Graphs |
| distance to nearest of many sources | multi-source BFS | Graphs |
| dependencies, prerequisites, ordering | topological sort | Graphs |
| shortest path, weighted non-negative | Dijkstra | Shortest Paths |
| at most k edges / negative weights | Bellman-Ford | Shortest Paths |
| all pairs, n ≤ 400 | Floyd-Warshall | Shortest Paths |
| grouping by connectivity, edges added over time | Union-Find | Union-Find |
| connect everything with minimum cost | MST (Kruskal/Prim) | Advanced Graphs |
| critical edges/nodes | Tarjan bridges / articulation points | Advanced Graphs |
| can it be split into two groups with no conflicts | bipartite check | Graphs |
Search over choices
| Signal | Try | Topic |
|---|---|---|
| return all combinations/permutations/partitions | backtracking | Backtracking |
| count ways / min/max value with overlapping choices | dynamic programming | DP |
| locally best choice provably works (scheduling, jumps) | greedy | Greedy |
| two sequences compared/aligned | 2D DP on prefixes | 2D DP |
| subset with a target sum / capacity | knapsack | Knapsack |
| merging/removing adjacent elements with costs | interval DP | Advanced DP |
| n ≤ 20, visit/assign all | bitmask DP | Advanced DP |
| count numbers ≤ N with a digit property | digit DP | Advanced DP |
Intervals
| Signal | Try |
|---|---|
| merge overlapping | sort by start, sweep |
| max non-overlapping / min removals / arrows | sort by end, greedy |
| min rooms / max concurrency | sweep line events or min-heap of end times |
| insert into sorted intervals online | balanced BST / sorted map |
Design
| Signal | Try |
|---|---|
| O(1) get/put with recency eviction | hash map + doubly linked list (LRU) |
| O(1) insert/delete/random | array + value→index map, swap-with-last |
| values over time / snapshots | per-key list + binary search |
| prefix lookups / autocomplete | trie |
| running median | two heaps |
Step 3: Keywords cheat sheet
| Keyword | Usually means |
|---|---|
| “contiguous”, “subarray”, “substring” | sliding window, prefix sums, Kadane |
| “subsequence” | DP (LIS, LCS) or two pointers (is-subsequence) |
| “all possible”, “generate”, “every combination” | backtracking |
| “number of ways” | DP (or combinatorics) |
| “minimum number of steps/moves” | BFS (unweighted) or DP |
| “minimum cost path” | Dijkstra or grid DP |
| “k-th largest/smallest”, “top k” | heap, quickselect, binary search on value |
| “sorted” / “rotated sorted” | binary search, two pointers |
| “in-place”, “O(1) space” | two pointers, index marking, bit tricks |
| “stream”, “online” | heaps, running aggregates, union-find |
| “prefix”, “dictionary of words” | trie |
| “parentheses”, “nested” | stack |
| “next greater”, “previous smaller” | monotonic stack |
| “overlapping”, “meetings”, “schedule” | intervals: sort + sweep |
| “connected”, “groups”, “provinces” | union-find / DFS |
| “prerequisites”, “order” | topological sort |
| “maximize the minimum” / “minimize the maximum” | binary search on answer |
| “palindrome” | two pointers, expand around center, DP |
| “XOR” | bit tricks, prefix XOR, binary trie |
| “modulo 10⁹ + 7” | counting DP or combinatorics |
Step 4: When you're stuck
- Brute force first. Write down the naive solution and its complexity. Then ask what's repeated or wasted.
- What would sorting give me? Many problems unlock after sorting.
- What would a hash map give me? Replace an inner search with O(1) lookups.
- Can I binary search the answer? Is there a monotone yes/no question?
- Draw small examples. Trees, grids, and DP tables are much easier on paper.
- Think about the last step. What was the last choice made? (DP, interval DP, greedy exchange.)
- Reverse the problem. Work backwards from the target, reverse edges, add instead of delete (offline union-find).
- Change the representation. Grid → graph, string → counts, numbers → bits, intervals → events.
- Relax a constraint to find the core difficulty, then add it back.