Pattern Checklist
The handful of patterns behind most interview problems — what triggers each one, the shape of the solution, and what it costs.
Recognise, Then Recall
The productive way to practise is therefore not "solve 500 problems" but "recognise 20 patterns and solve enough of each to know their edges". After that, an unseen problem is usually a familiar pattern wearing different words.
This page is a checklist to work down: the trigger that tells you a pattern applies, the shape of the solution, and its cost. Each links to the topic that teaches it properly.
Array & String Patterns
| Trigger in the problem | Pattern | Cost |
|---|---|---|
| Sorted array, find a pair or a target | Two pointers from both ends | O(n) |
| Contiguous subarray of size k, or "longest substring with…" | Sliding window | O(n) |
| Repeated range sums | Prefix sums computed once | O(n) build, O(1) query |
| "Have I seen this before" | Hash map of seen values | O(n) |
| Sorted input, find one value | Binary search | O(log n) |
| Next greater or smaller element | Monotonic stack | O(n) |
| In-place rearrangement | Read and write pointers | O(n), O(1) space |
Tree & Graph Patterns
| Trigger in the problem | Pattern | Cost |
|---|---|---|
| Shortest path in an unweighted graph | BFS with a queue | O(V+E) |
| Explore every path, detect a cycle | DFS with recursion or a stack | O(V+E) |
| Weighted shortest path, no negative edges | Dijkstra with a heap | O(E log V) |
| Ordering with prerequisites | Topological sort | O(V+E) |
| Sorted output from a BST | In-order traversal | O(n) |
| Level-by-level processing | BFS tracking the queue size per level | O(n) |
| Prefix matching over many strings | Trie | O(length) |
Optimisation Patterns
| Trigger in the problem | Pattern | Cost |
|---|---|---|
| "Maximum", "minimum" or "count the ways", with overlapping subproblems | Dynamic programming | Usually O(n·m) |
| A locally best choice is provably globally best | Greedy | Often O(n log n) with a sort |
| Generate every combination or permutation | Backtracking on a recursive tree | Exponential — expected |
| Top or bottom k elements | Heap of size k | O(n log k) |
| Repeated merging of groups | Union-find | Near O(1) amortised |
The dynamic-programming tell is worth memorising: overlapping subproblems plus optimal substructure. If a brute-force recursion recomputes the same state, memoise it — that step alone converts most exponential solutions into polynomial ones.
A Method For The Interview
| Step | What to say and do |
|---|---|
| Clarify | Input size, ranges, duplicates, empty input, what to return on no answer |
| State a brute force | Give its complexity out loud — it shows you know what you are improving on |
| Name the pattern | "This is a sliding window because we want the longest contiguous…" |
| Walk one example | On paper, before writing code — most bugs are caught here |
| Write it | Talking through the invariant as you go |
| Test the edges | Empty, single element, all duplicates, maximum size |
| State the complexity | Time and space, and where the bound comes from |
When stuck: sort the input and see what becomes possible, try a hash map for the lookup, ask whether the input structure hints at binary search, or solve a smaller version and look for the recurrence. See Big-O Notation for stating the bound precisely.
Interview Questions
How do you decide between sliding window and two pointers?
Both walk an array once. Sliding window maintains a contiguous range with a running aggregate; two pointers converge from the ends, typically on sorted input, to find a pair or partition.
What tells you a problem is dynamic programming?
Overlapping subproblems and optimal substructure — a brute-force recursion that recomputes the same state. Memoising that recursion is usually the whole solution.
When is greedy safe?
Only when you can argue the locally optimal choice is globally optimal. Without that argument greedy passes the examples and fails on a case nobody tried.
How do you recognise a graph problem in disguise?
Grids, dependencies, word ladders and state machines are all graphs. If states connect to neighbouring states, BFS or DFS applies regardless of how the problem is phrased.
What is the first thing to do with a new problem?
Clarify the constraints, then state a brute force with its complexity. It gives a baseline, buys thinking time, and makes the optimisation conversation concrete.
How do you find the top k elements efficiently?
A heap of size k in O(n log k), rather than sorting everything in O(n log n) — and it works on a stream, where sorting does not.