Free lessons · from Think in Patterns
Which pattern is this?
Problems rarely say which pattern they want. The statement gives cues: the shape of the input, the word used for the answer, a constraint that rules out the obvious approach. Match the cue, turn to the chapter, and start from its template.
By what the problem asks for
Read the problem twice and underline the words. They usually name the pattern for you.
| You read… | Think | Chapter |
|---|---|---|
| “two numbers that…”, “does a duplicate exist”, “count how often”, “group the…” | hash map or set | 1 Arrays & Hashing |
| “sum of a range”, “subarray with sum k”, “equal zeros and ones” | prefix sums | 2 Prefix Sum |
| numbers in 1..n, “missing”, “duplicate”, “first missing positive”, O(1) space | cyclic sort | 3 Cyclic Sort |
| rotate, spiral, set rows and columns | matrix walks | 4 Matrix & Grid |
| palindromes, find a pattern in text, parse a string | expand around centre, KMP | 5 Strings |
| sorted array, pair or triplet, “in place”, “remove”, “move zeroes” | two pointers | 6 Two Pointers |
| “longest / shortest substring or subarray with…”, “at most k distinct”, window of size k | sliding window | 7 Sliding Window |
| sorted input, “find the position”, “minimum capacity / speed / days such that…” | binary search, binary search on the answer | 8 Binary Search |
| “kth largest”, custom order, values in a small range | quickselect, custom sort, counting sort | 9 Sorting & Quickselect |
| reverse, merge, reorder, remove the nth from the end | linked list with a dummy head | 10 Linked List |
| cycle, middle, “without extra space” on a list, repeated function application | fast and slow pointers | 11 Fast & Slow Pointers |
| brackets, “undo”, nested structure, evaluate an expression | stack | 12 Stack |
| “next greater / smaller”, “days until warmer”, largest rectangle, window maximum | monotonic stack or deque | 13 Monotonic Stack |
| depth, path sum, diameter, lowest common ancestor, serialise | tree DFS | 14 Binary Trees |
| “level by level”, right side view, zigzag, connect siblings | tree BFS | 14 Binary Trees |
| BST property, kth smallest in a BST, validate, insert, delete | inorder is sorted | 15 Binary Search Trees |
| “starts with”, prefix search, many words to match against a text | trie | 16 Tries |
| “top k”, “k closest”, “k most frequent”, stream of numbers | heap of size k | 17 Heaps |
| running median, two halves of a stream | two heaps | 17 Heaps |
| “merge k sorted…”, “smallest range covering…” | k-way merge | 17 Heaps |
| islands, regions, “reachable”, clone a graph, shortest steps in a grid | graph BFS / DFS | 18 Graph BFS & DFS |
| prerequisites, ordering with dependencies, “is it possible to finish” | topological sort | 19 Topological Sort |
| connected components, “redundant connection”, merge accounts, equality constraints | union-find | 20 Union-Find |
| weighted edges, “cheapest”, “minimum effort”, “within k stops”, connect all points | Dijkstra, Bellman-Ford, Prim, Kruskal | 21 Shortest Paths & MST |
| “all subsets / permutations / combinations”, “generate every”, N-Queens, Sudoku, word search | backtracking | 22 Backtracking |
| “number of ways”, “minimum cost to reach”, “longest increasing”, choices along a line | 1-D DP | 23 1-D Dynamic Programming |
| two strings, a grid of paths, edit distance, subsequence of two sequences | 2-D DP | 24 2-D Dynamic Programming |
| “can we pick items to reach a sum”, “coins”, “partition into equal halves”, “burst / cut / merge” | knapsack, interval DP | 25 Knapsack & Interval DP |
| intervals: merge, insert, overlap, rooms, arrows | sort by start or end | 26 Intervals |
| “minimum number of jumps / refuels / changes”, a local choice that is safe | greedy | 27 Greedy |
| “without using +”, “appears once”, powers of two, count set bits | bit manipulation | 28 Bit Manipulation |
| pow, sqrt, primes, digits, points on a line, overflow | math | 29 Math & Geometry |
| “design a… with O(1) get and put”, LRU, LFU, random access, time-based store | data-structure design | 30 Data-Structure Design |
By the constraint
The input size tells you the complexity the interviewer expects. A Python solution does roughly 10⁷ simple operations a second, so the limits below are for Python; in C++ or Java each row stretches about ten times further.
| n is about | Expected time | Patterns that fit |
|---|---|---|
| ≤ 20 | O(2ⁿ) or O(n!) | backtracking, bitmask over subsets |
| ≤ 200 | O(n³) | interval DP, Floyd–Warshall |
| ≤ 3 000 | O(n²) | 2-D DP, brute-force pairs, expand around centre |
| ≤ 10⁵ or 10⁶ | O(n log n) or O(n) | sorting, heaps, binary search, hashing, two pointers, sliding window, prefix sums, monotonic stack |
| ≤ 10⁹ or more | O(log n) or O(1) | binary search on the answer, math, bit tricks |
Two cues that override everything
- “Contiguous” (subarray, substring) → sliding window or prefix sums. “Not necessarily contiguous” (subsequence) → DP or greedy.
- “Sorted” in the input → two pointers or binary search before anything else. If it is not sorted and the answer does not need the original order, ask whether you may sort it.
When two patterns fit
Prefer the one with the better complexity for the constraint, then the one with less code. Say both to the interviewer: “This could be a heap or quickselect; quickselect is O(n) average, the heap is O(n log k) but simpler. Which would you like?”
This is page 107 of Think in Patterns. Each of these 30 patterns has its own chapter, with a template, worked problems and exercises, and the six AI-era chapters have a cue table of their own.