Stage 1 · Code
Interview Synthesis
The Pattern Decision Map
Connect every course family to its strongest input signals, maintained invariant, complexity target, and rejection test.
12 min readLeetCode Patterns for InterviewsCode
Start With the Problem Shape
This map is not a checklist to scan from top to bottom. First classify the problem's shape: lookup, contiguous range, ordered elimination, nested structure, hierarchy, relationship graph, choice tree, repeated state, interval ordering, stream statistic, or bounded selection. Then use constraints to choose the smallest family whose invariant proves the result.
A family is an invariant, not a code template
Hashing preserves facts seen so far; a window preserves facts inside a contiguous range; a monotonic stack preserves unresolved candidates; DP preserves answers to named states. Remember what the state means and you can rebuild the implementation.
Linear, Ordered & Pointer Families
| Family | Strong signals | Invariant and typical target | Reject when |
|---|---|---|---|
| Hash maps and frequency state | Complement lookup, counting, grouping, last-seen position | Stored entries summarize the processed prefix; usually O(n) expected time | Key range supports a simpler fixed array, or ordering—not membership—is the core structure |
| Sets and deduplication | Existence, uniqueness, sequence starts | Membership answers whether a value has been seen or belongs to the domain; O(n) expected time | Multiplicity or ordering must be preserved |
| Prefix sums and prefix state | Many range queries, subarray totals, balance or remainder equality | Prefix i summarizes everything before i; a range becomes a difference; O(n) preprocessing or scan | The aggregate cannot be combined or inverted appropriately |
| Sorting, buckets, and counting | Order unlocks grouping or elimination; values or frequencies are bounded | Equal or ordered items become adjacent; O(n log n), or O(n+r) with bounded range r | Original order is semantically required and indices cannot be carried along |
| Matrix traversal and in-place layers | Rows, columns, rings, neighbor coordinates | Every cell or boundary layer is visited under explicit bounds; usually O(rows·cols) | The grid is actually a graph with distance, reachability, or path-state requirements |
| Opposite-end pointers | Sorted input, pair/triple target, endpoint area | Each comparison proves one endpoint cannot improve the answer; O(n) after any sorting | There is no ordering argument that safely discards an endpoint |
| Fast and slow pointers | Cycle, midpoint, repeated state in a deterministic transition | Runners advance at different speeds through the same successor relation; O(n) time and O(1) space | Each state has multiple outgoing choices or random access history is required |
| Fixed sliding window | Every contiguous segment has exact width k | State describes exactly the current k items and updates by one add plus one remove; O(n) | Window width changes with validity |
| Dynamic sliding window | Longest or shortest valid contiguous range with monotonic validity | Expand to discover candidates, shrink to restore validity; each boundary moves forward at most n times | Negative or otherwise non-monotonic effects make discarded boundaries potentially useful again |
| Monotonic deque | Maximum or minimum for every window; candidates expire by index | Front is the current extreme; back removes candidates dominated for all future overlapping windows; O(n) | Dominance is not permanent or queries are not aligned with forward-moving windows |
| Monotonic stack | Next greater/smaller, span, histogram, unresolved positions | The stack keeps unresolved candidates in value order; each item is pushed and popped once | The question is an ordered yes/no boundary rather than a next-resolution relationship |
| Parsing stack | Nesting, matching delimiters, deferred operators | The top represents the most recent unmatched or incomplete context; usually O(n) | No last-opened-first-closed dependency exists |
| Classic, boundary, rotated, and matrix binary search | Sorted data or a partitioned predicate | The answer remains inside an explicit half-open or closed interval; O(log n) | The predicate does not switch monotonically or duplicates erase the needed ordering without a fallback |
| Binary search on the answer | Minimize a feasible capacity or maximize a valid threshold | A monotonic feasibility predicate divides impossible and possible answers; O(check·log range) | Feasibility can flip back and forth as the candidate changes |
Recursive, Relational & Choice Families
| Family | Strong signals | Invariant and typical target | Reject when |
|---|---|---|---|
| Linked-list pointer manipulation | Reverse, merge, reorder, remove relative to the end | Named pointers delimit processed and unprocessed chains without losing the next node; O(n), often O(1) space | Random access is required repeatedly |
| Tree DFS and traversal order | Subtree result, root-to-leaf path, hierarchy | Each call returns a precisely defined answer for its subtree; O(n) | Shortest unweighted level distance is the primary output and BFS is simpler |
| Tree BFS | Levels, nearest node, right-side view | The queue holds exactly the next frontier, often processed one level at a time; O(n) | The answer combines child results bottom-up |
| Binary-search-tree ordering | Ordered lookup, kth value, range validation | Every node is constrained by ancestor bounds, or inorder order is monotonic; O(h) lookup on balanced trees | The tree does not preserve BST order |
| Tree construction and path aggregation | Rebuild from traversals, diameter, serialization, path sum | Traversal partitions or recursive return values define each subtree exactly; usually O(n) | Input traversals are ambiguous under the stated duplicate rules |
| Tries | Prefix lookup, dictionary branching, autocomplete | A path from the root represents a prefix; operations cost O(word length) | Only whole-key lookup is required and hashing is simpler |
| Graph BFS and DFS | Reachability, components, grids, unweighted shortest path | Visited nodes are fully scheduled once; O(V+E) | Edge weights affect shortest distance or state must include more than the node |
| Topological sort | Prerequisites, dependency ordering, directed cycle | Every emitted node has no remaining unmet prerequisite; O(V+E) | The graph is undirected or a total order cannot be inferred or requested |
| Union-find | Repeated connectivity and component merging | Each element points toward a component representative; near-constant amortized operations | Paths, traversal order, or edge weights—not only connectivity—must be reported |
| Shortest-path algorithms | Minimum cost or distance in a weighted state graph | BFS finalizes unweighted layers; Dijkstra finalizes the smallest non-negative tentative distance | Dijkstra has negative edges, or a simpler BFS covers unit weights |
| Backtracking | Enumerate choices, arrangements, paths, or constraint assignments | The active path owns temporary state; choose, explore, and unchoose restore it exactly | Only an optimum or count is needed and repeated states can be merged with DP |
Optimization & Specialized Families
| Family | Strong signals | Invariant and typical target | Reject when |
|---|---|---|---|
| 1-D and 2-D dynamic programming | Overlapping choices over an index, grid, amount, or pair of indices | Each state stores the complete answer to a smaller subproblem; target is number of states times transitions | States do not repeat or the state definition omits information needed for future choices |
| Knapsack-style DP | Choose or skip under capacity, target sum, or limited items | State combines progress through items with remaining or used capacity | Items are reusable but the iteration order still models 0/1 use, or vice versa |
| String and interval DP | Two sequences, substrings, palindromes, split points | State answers a prefix pair or interval [left,right]; transitions extend, match, or split | A greedy local match has a proof, or a simpler linear string algorithm fits |
| Greedy choice | Need one optimum; sorting reveals a safe local decision | An exchange argument shows an optimal solution can include the local choice | A counterexample shows today's best-looking choice blocks tomorrow's optimum |
| Interval ordering and merging | Overlapping ranges, meeting rooms, insert or intersect intervals | After sorting, the active boundary summarizes every interval merged so far; O(n log n) | Intervals arrive online and require a dynamic structure |
| Index placement | Values come from an index-sized domain and mutation is allowed | Each swap places at least one value at its target index; O(n) time and O(1) auxiliary space | Values lack a deterministic destination or input mutation is forbidden |
| Two heaps | Running median or a dynamic split around a rank | A max-heap owns the lower partition, a min-heap owns the upper, and sizes differ by at most one | Only one extreme or a fixed k boundary is needed |
| Bounded heap for top k | Keep the best k without sorting every candidate | Heap root is the weakest retained candidate; O(n log k) | The value range supports linear buckets or all results must be fully sorted anyway |
| K-way frontier heap | Several independently sorted lists, rows, or streams | The heap contains the smallest unseen item from each active source; O(N log k) | Inputs are not individually ordered |
| XOR cancellation | Paired values plus one or two exceptions; bit parity | Equal bits cancel because x XOR x = 0 and order does not matter; O(n) time, O(1) space | Multiplicity does not match the cancellation model or the actual values must be reconstructed beyond available parity information |
Use the Map Under Pressure
For a new prompt, produce a compact decision record: signal, candidate, invariant, target complexity, and rejection test. If two families remain plausible, compare the assumptions they need. This prevents both premature coding and endless brainstorming.
Applied exercise
Build a personal decision map from misses
Choose six previously attempted problems: two solved cleanly, two solved after a hint, and two solved with the wrong first pattern.
- For each problem, record the decisive constraint that should have guided classification.
- Write the chosen family's invariant without referring to code.
- Name one adjacent family and the precise acceptance test it failed.
- Record the achieved and target time and space complexity.
- Turn each miss into a one-sentence trigger phrased as evidence, not a keyword.
Deliverable
A six-row decision journal suitable for review before the next practice session.
Completion checks
- Every row includes a rejection reason tied to monotonicity, ordering, repeated state, output shape, or complexity.
- No trigger says only “when you see X, use Y.”
- Complexity includes the cost of sorting, heap operations, recursion depth, or output where relevant.
- At least one row records that the original candidate was correct but the invariant or boundary convention was wrong.
Quiz & Practice
Question 1 / 2
You need the k largest values from a stream and k is much smaller than n. Which invariant best describes a bounded min-heap?
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.