DSA Patterns — Interview Cheat Sheet
14 essential patterns — recognize the signal, apply the template, solve in 20 minutes.
Interview tip Say the pattern aloud: "Sorted array + pair sum → two pointers from both ends."
① Master pattern table — 14 patterns
| # | Pattern | Signal | Template idea |
|---|---|---|---|
| 1 | Two pointers | Sorted array, pairs, palindrome | Left/right converge based on condition |
| 2 | Sliding window | Subarray/substring with constraint | Expand R, shrink L while invalid |
| 3 | Binary search | Monotonic answer space | Mid, discard half where property fails |
| 4 | Fast & slow pointers | Linked list cycle, middle | Tortoise/hare meet or fast reaches end |
| 5 | Merge intervals | Overlapping ranges | Sort by start, merge if overlap |
| 6 | Cyclic sort | Array 1..n, missing/duplicate | Place num at index num-1 |
| 7 | In-place reversal | Reverse list/subarray | Prev/curr/next pointer swap |
| 8 | Tree BFS | Level order, shortest path tree | Queue level-by-level |
| 9 | Tree DFS | Paths, sums, validate BST | Recursion with state passed down/up |
| 10 | Two heaps | Stream median, balance | Max-heap lower half + min-heap upper |
| 11 | Subsets / backtracking | Combinations, permutations | Include/exclude each element |
| 12 | Modified BFS | Grid shortest path | Queue + visited matrix + 4/8 dirs |
| 13 | Topological sort | Dependencies, prerequisites | Kahn indegree zero or DFS post-order |
| 14 | Dynamic programming | Optimal substructure + overlap | Define state, recurrence, base, order |
② Two pointers & sliding window
Sliding window [L ... R]
L→window→R
Two pointers: 3Sum — sort, fix i, two pointers on rest for sum zero. O(n²).
Sliding window: expand R until constraint violated → shrink L until valid → track best. Longest substring without repeat — HashMap of last index. O(n).
Sliding window: expand R until constraint violated → shrink L until valid → track best. Longest substring without repeat — HashMap of last index. O(n).
| Problem type | Pattern | Complexity |
|---|---|---|
| Pair sum sorted | Two pointers | O(n) |
| Container most water | Two pointers | O(n) |
| Min size subarray sum ≥ K | Sliding window | O(n) |
| Max in each window of size K | Deque monotonic queue | O(n) |
③ Binary search & monotonic space
Not just sorted arrays: binary search on answer space — e.g. "minimum capacity to ship in D days" where feasible(cap) is monotonic false→true.
- Identify monotonic predicate can(x) or cannot(x)
- Lo = min possible, Hi = max possible answer
- While lo < hi: mid = lo + (hi-lo)/2; shrink range
- Watch off-by-one: lower vs upper bound variants
| Classic | Search space |
|---|---|
| Search rotated sorted array | Index in array |
| Koko eating bananas | Eating speed k |
| Median of two sorted arrays | Partition position |
④ Linked list & interval patterns
Fast/slow: cycle detection — if slow meets fast, cycle exists. Find cycle start: reset slow to head, advance both 1 step.
Merge intervals: sort by start; if curr.start ≤ prev.end merge else append new.
Merge intervals: sort by start; if curr.start ≤ prev.end merge else append new.
In-place list reversal
prev=null→curr=head→next=curr.next→curr.next=prev
⑤ Tree patterns — BFS vs DFS
| Goal | Pattern | Structure |
|---|---|---|
| Level order | BFS queue | Process size at each level |
| Max depth | DFS | 1 + max(left, right) |
| Validate BST | DFS | Pass min/max bounds down |
| Lowest common ancestor | DFS | Return node if match or both subtrees found |
| Serialize tree | BFS or DFS preorder | Null markers for reconstruction |
BFS = shortest path in unweighted tree/graph. DFS = path enumeration, backtracking on trees.
⑥ Graph — BFS, topo sort, union-find
| Pattern | Algorithm | Problems |
|---|---|---|
| Modified BFS | Queue + visited | Rotting oranges, word ladder, grid islands |
| Topological sort | Kahn BFS or DFS post-order | Course schedule, alien dictionary |
| Union-Find | Parent array + rank | Number of provinces, redundant connection |
| Dijkstra | Min-heap by distance | Weighted shortest path (non-negative) |
Course schedule: build adjacency list + indegree; queue nodes with indegree 0; if processed count < n → cycle.
⑦ Heaps & top-K
Top K largest: min-heap of size K — O(n log K). Top K smallest: max-heap of size K.
Two heaps: max-heap stores lower half, min-heap upper half — median in O(log n) insert.
Two heaps: max-heap stores lower half, min-heap upper half — median in O(log n) insert.
| Problem | Heap type | Size |
|---|---|---|
| Kth largest element | Min-heap | K |
| Merge K sorted lists | Min-heap of heads | K |
| Find median stream | Two heaps | Balanced sizes |
⑧ Backtracking & subsets
Template: choose → explore → unchoose. Subsets: at each index include or skip. Permutations: swap or used[] array.
- Define base case — index == n or path.len == k
- Prune early if invalid partial state
- Copy path when adding to result (new ArrayList<>(path))
- Watch duplicate subsets — sort + skip same value at same depth
⑨ Dynamic programming framework
1. Define state dp[i] or dp[i][j] — what subproblem?
2. Recurrence — how state relates to smaller states
3. Base cases — dp[0], empty string, etc.
4. Order of computation — iterate so dependencies ready
5. Space optimize — rolling array if only dp[i-1] needed
| Type | Examples | State |
|---|---|---|
| 1D linear | Climbing stairs, house robber | dp[i] best at i |
| 2D grid | Unique paths, min path sum | dp[r][c] |
| String DP | LCS, edit distance | dp[i][j] on prefixes |
| Knapsack | 0/1 knapsack, coin change | dp[i][w] capacity |
⑩ Pattern selection cheat sheet
| You see… | Reach for… |
|---|---|
| Sorted + pair/triplet | Two pointers |
| Contiguous + constraint | Sliding window |
| Min/max feasible value | Binary search on answer |
| Linked list cycle/middle | Fast/slow pointers |
| Overlapping intervals | Merge intervals |
| 1..n missing dup | Cyclic sort |
| Dependencies | Topological sort |
| Shortest path grid | BFS |
| All combinations | Backtracking |
| Optimize over choices | DP |