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 as a target shape: TL;DR -> Core Basics -> recognition cues -> Diagram (Mermaid) -> optional step-by-step visual enrichment -> Understanding -> generic recipe -> complexity -> Memory Hooks -> Study Pattern (SDE3+) -> Go + JS template -> variants -> representative problems -> anti-patterns.
How to read a pattern page for clarity
- Read TL;DR and Core Basics — one minute to know what object you are maintaining (indices, queue, heap, trie node, …).
- Skim Recognition Cues — tie phrases from problem statements to this pattern.
- Study the Diagram — it is the fastest way to rebuild the algorithm from memory.
- Walk the Generic Recipe out loud with a tiny example before looking at code.
- Use Anti-patterns to see the common wrong turns (off-by-one, wrong heap order, missing undo in backtracking).
Code at the bottom is for fluency; Understanding + Diagram are what make the concept stick.
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 or sorted after preprocessing? -> Two Pointers, Binary Search, Merge Intervals, or Greedy by sorted key.
- Contiguous substring/subarray with a maintained condition? -> Sliding Window.
- Linked list with "cycle/middle/k-from-end"? -> Fast & Slow; with "reverse/sublist/k-group"? -> Linked List Reversal.
- Values are supposed to live in
[1..n]or index positions? -> Cyclic Sort. - "kth ...", "top k", streaming rank, or repeated next-best candidate? -> Top-K / Heap, Monotonic Queue, or Divide & Conquer for partition-based selection.
- Tree / graph traversal? -> BFS for shortest/levels; DFS for all paths, components, post-order, or backtracking.
- Dependency / ordering / prerequisites? -> Topological Sort.
- Dynamic connectivity / groups / redundant edge? -> Union-Find.
- Prefix queries on strings or dictionary pruning? -> Trie.
- "Next greater / smaller", span, histogram, or window max? -> Monotonic Stack / Queue.
- Range sum, repeated subarray sum, or range update? -> Prefix Sum / Difference Array.
- XOR, bit count, bitmask subsets, or arithmetic without operators? -> Bit Manipulation.
- "Optimize/count ways with overlapping subproblems"? -> Dynamic Programming.
- "Make local choice" with a provable exchange/frontier argument? -> Greedy.
- Split into independent halves/ranges and combine results? -> Divide & Conquer.
Mark this page when you finish learning it.
Last updated on
Spotted something unclear or wrong on this page?