Patterns — Recognition Layer
The 20 patterns that recur across ~90% of MAANG/MNC SDE3+ DSA interviews. Master these, and 80% of new problems become "oh, this is just X with a twist".
Each pattern file follows the pattern template: TL;DR → recognition cues → Diagram (Mermaid) → mental model → generic recipe → Go + JS template → variants → representative problems → anti-patterns.
The 20 patterns
| # | Pattern | When you see it | Guide |
|---|---|---|---|
| 01 | Two Pointers | sorted array, pair/triplet sums, in-place dedupe | Two Pointers |
| 02 | Sliding Window | longest/shortest substring with property, fixed-size subarray | Sliding Window |
| 03 | Fast & Slow Pointers | linked list cycle, find middle, duplicate number | Fast & Slow Pointers |
| 04 | Binary Search | sorted array, "find smallest X such that ..." (search on answer) | Binary Search |
| 05 | BFS | shortest path in unweighted graph, level-order tree | BFS |
| 06 | DFS / Backtracking | combinations/permutations, all paths, "is there a way" | DFS / Backtracking |
| 07 | Top-K / Heap | "k largest/smallest/most frequent" | Top-K / Heap |
| 08 | Merge Intervals | intervals input, overlap/merge | Merge Intervals |
| 09 | Cyclic Sort | numbers in [1..N], find missing/duplicate in O(n) O(1) | Cyclic Sort |
| 10 | In-place Linked List Reversal | reverse list / sublist / k-group | In-place Linked List Reversal |
| 11 | Tree DFS / DP-on-Trees | path sums, diameter, LCA, serialize | Tree DFS / DP-on-Trees |
| 12 | Topological Sort | ordering with prerequisites, DAG | Topological Sort |
| 13 | Union-Find (DSU) | dynamic connectivity, count components, redundant edges | Union-Find (DSU) |
| 14 | Trie | prefix queries, word search, autocomplete | Trie |
| 15 | Monotonic Stack / Queue | "next greater / smaller", sliding-window max | Monotonic Stack / Queue |
| 16 | Prefix Sum / Difference Array | range sums, range updates | Prefix Sum / Difference Array |
| 17 | Bit Manipulation | XOR tricks, subsets, single number | Bit Manipulation |
| 18 | Dynamic Programming | optimal substructure + overlapping subproblems | Dynamic Programming |
| 19 | Greedy | local choice -> global optimum, exchange argument | Greedy |
| 20 | Divide & Conquer | recurse halves + merge (sort, search) | Divide & Conquer |
Decision tree (cheat)
See Pattern recognition cheatsheet for a flowchart.
Quick triage:
- Sorted input? -> Two Pointers / Binary Search
- Substring/subarray with constraint? -> Sliding Window
- Linked list with "cycle/middle/k-from-end"? -> Fast & Slow
- "kth ..." or "top k"? -> Heap (or Quickselect)
- Tree / graph traversal? -> BFS (shortest, levels) vs DFS (all paths, post-order)
- Dependency / ordering? -> Topo Sort
- Dynamic connectivity / groups? -> Union-Find
- Prefix queries on strings? -> Trie
- "Next greater / smaller"? -> Monotonic Stack
- Range sum / update? -> Prefix Sum / Difference Array
- "Optimize X with overlapping subproblems"? -> DP
- "Make local greedy choice"? -> Greedy
Last updated on
Spotted something unclear or wrong on this page?