DSA & Algorithms
Part 1 of 21 · DSA Interview PatternsDSA for Interviews — Pattern Map, Complexity & How to Drill
Interview DSA pattern map, Big-O cheat sheet, how to pick a pattern, and drill pacing for 20 core patterns.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The prompt is a new LeetCode-style problem
Prefer
Name the pattern, then the template
Constraints and a few examples pick the family. The template is the thing you practice until it is boring.
- You say the target complexity before the first line.
- Brute force is a checkpoint, not the answer you stop on.
- The same skeleton comes back in Python and TypeScript.
Alternative
Memorize three hundred solutions
A grab-bag of tricks with no cue for which one this prompt is.
- A new wording stalls you even when the pattern is one you have solved.
- You cannot explain why the complexity is what you claim.
- Follow-ups (streaming, negatives, duplicates) have nowhere to attach.
From prompt to pattern
The diagram is the interview order: read, classify, then only then code.
- 1
Read constraints and examples
Empty input, duplicates, negatives, and the size of n. - 2
Name the family
Window, search, graph, heap, DP, or search tree. - 3
State brute force, then the target
Say the complexity you are aiming at before you type. - 4
Code the invariant
Window valid, stack monotone, or what dp[i] means.
Overview
Interview DSA pattern map, Big-O cheat sheet, how to pick a pattern, and drill pacing for 20 core patterns.
Twenty pattern pages follow this hub. Each one has recognition cues, a top-down diagram, Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
Why this series
- This is the foundation track for coding interviews: a pattern map, with Big-O, templates, and drills.
- Goal: walk into coding interviews with a pattern map, not a grab-bag of tips.
- Drill order: Arrays/Hashing → Windows/Pointers → Trees/Graphs → Heaps/UF → DP → Backtracking.
Pattern map (Hub cycle)
| # | Pattern | Focus |
|---|---|---|
| 1 | Arrays & Two Pointers | Arrays & Two Pointers |
| 2 | Sliding Window | Sliding Window |
| 3 | Prefix Sums & Difference Arrays | Prefix Sums & Difference Arrays |
| 4 | Binary Search & Search-on-Answer | Binary Search & Search-on-Answer |
| 5 | Sorting, Intervals & Sweep Line | Sorting, Intervals & Sweep Line |
| 6 | Stack & Monotonic Stack | Stack & Monotonic Stack |
| 7 | Queue, Deque & Monotonic Queue | Queue, Deque & Monotonic Queue |
| 8 | Linked Lists — Reverse, Merge, Cycle | Linked Lists — Reverse, Merge, Cycle |
| 9 | Binary Trees — DFS | Binary Trees — DFS |
| 10 | Binary Trees — BFS / Level Order | Binary Trees — BFS / Level Order |
| 11 | Binary Search Trees | Binary Search Trees |
| 12 | Heaps, Priority Queues & Top-K | Heaps, Priority Queues & Top-K |
| 13 | Hashing, Frequency Maps & Counting | Hashing, Frequency Maps & Counting |
| 14 | Graphs — DFS & BFS Traversal | Graphs — DFS & BFS Traversal |
| 15 | Graphs — Topological Sort & DAGs | Graphs — Topological Sort & DAGs |
| 16 | Union-Find (Disjoint Set Union) | Union-Find (Disjoint Set Union) |
| 17 | Shortest Paths | Shortest Paths |
| 18 | Dynamic Programming — 1D Patterns | Dynamic Programming — 1D Patterns |
| 19 | Dynamic Programming — 2D, Knapsack & Grids | Dynamic Programming — 2D, Knapsack & Grids |
| 20 | Backtracking & Search Trees | Backtracking & Search Trees |
Nav cycle: Hub → 1 → 2 → … → 20 → Hub.
How to pick a pattern
Decisions
- 1
Step 1 Read constraints - n size, sorted, graph, optimize
- nextStep 2 Contiguous range or sorted input?
- ?
Step 2 Contiguous range or sorted input?
- sorted, monotone predicateStep 3a Binary search or search-on-answer
- contiguous, incremental stateStep 3b Sliding window or prefix sums
- noStep 4 Graph, tree, or grid?
- 3
Step 3a Binary search or search-on-answer
- 4
Step 3b Sliding window or prefix sums
- ?
Step 4 Graph, tree, or grid?
- yesStep 5 DFS or BFS, union-find, topo sort on a DAG
- noStep 6 Optimal over choices?
- 6
Step 5 DFS or BFS, union-find, topo sort on a DAG
- ?
Step 6 Optimal over choices?
- overlapping subproblemsStep 7a DP - define the state, then transitions
- enumerate all answersStep 7b Backtracking with pruning
- top-K or next greaterStep 7c Heap or monotonic stack
- no cue fitsFailure path - state brute force, then find the repeated work
- 8
Step 7a DP - define the state, then transitions
- 9
Step 7b Backtracking with pruning
- 10
Step 7c Heap or monotonic stack
- 11
Failure path - state brute force, then find the repeated work
Lesson map
DSA for Interviews — Pattern Map, Complexity & How to Drill
Interview DSA pattern map, Big-O cheat sheet, how to pick a pattern, and drill pacing for 20 core patterns.
Architecture. Step 1 Read constraints - n size, sorted, graph, optimize Ready. Step 2 Contiguous range or sorted input? Ready. Step 3a Binary search or search-on-answer Ready. Step 3b Sliding window or prefix sums Ready. Step 4 Graph, tree, or grid? Ready. Step 5 DFS or BFS, union-find, topo sort on a DAG Ready. Step 6 Optimal over choices? Ready. Step 7a DP - define the state, then transitions Ready. Step 7b Backtracking with pruning Ready. Step 7c Heap or monotonic stack Ready. Failure path - state brute force, then find the repeated work Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Q["Step 1 Read constraints - n size, sorted, graph, optimize Ready"] A["Step 2 Contiguous range or sorted input? Ready"] BS["Step 3a Binary search or search-on-answer Ready"] SW["Step 3b Sliding window or prefix sums Ready"] B["Step 4 Graph, tree, or grid? Ready"] G["Step 5 DFS or BFS, union-find, topo sort on a DAG Ready"] C["Step 6 Optimal over choices? Ready"] DP["Step 7a DP - define the state, then transitions Ready"] BT["Step 7b Backtracking with pruning Ready"] HS["Step 7c Heap or monotonic stack Ready"] BF["Failure path - state brute force, then find the repeated work Ready"] Q -->|continues| A A -->|sorted, monotone predicate| BS A -->|contiguous, incremental state| SW A -->|no| B B -->|yes| G B -->|no| C C -->|overlapping subproblems| DP C -->|enumerate all answers| BT C -->|top-K or next greater| HS C -->|no cue fits| BF
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Cue cheat sheet
- contiguous subarray / substring → sliding window or prefix sums
- sorted array / find boundary → binary search
- merge overlapping ranges → sort + intervals
- next greater / daily temperatures → monotonic stack
- connected components / islands → DFS/BFS or Union-Find
- course prerequisites → topological sort
- shortest path weighted → Dijkstra (non-negative weights) / Bellman-Ford (negative edges OK; detects reachable negative cycles)
- maximize/minimize with choices → DP or greedy (prove greedy!)
- all subsets / permutations → backtracking
The sandbox names a pattern from a cue. It is a drill, not a judge.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Big-O cheat sheet
| Structure / Algo | Time (typical) | Space | Notes |
|---|---|---|---|
| Array scan / two pointers | O(n) | O(1) | Sorted often required |
| Sliding window | O(n) | O(k) alphabet | Hash for counts |
| Binary search | O(log n) | O(1) | Monotonic predicate; search-on-answer = O(log range x check cost) |
| Sort + scan | O(n log n) | O(1)-O(n) | Intervals, sweep |
| Hash map ops | O(1) avg | O(n) | Worst O(n) rare |
| Stack / mono stack | O(n) | O(n) | Each index push/pop once |
| Heap top-K | O(n log k) | O(k) | Prefer over full sort |
| Tree DFS/BFS | O(n) | O(h) / O(w) | h height, w width |
| Graph DFS/BFS | O(V+E) | O(V) | Adjacency list |
| Dijkstra (binary heap) | O((V+E) log V) | O(V) | Non-negative weights |
| Bellman-Ford | O(VE) | O(V) | Neg edges; detect neg cycle |
| Union-Find | ~O(alpha(n)) amortized (path compression + union by rank/size) | O(n) | Nearly constant |
| 1D DP | O(n)-O(n*state) | O(state) | Roll arrays |
| 2D / knapsack | O(nW) pseudo-polynomial in capacity W, or O(nm) for grids | O(W) or O(nm) | Space-opt often |
| Backtracking | O(b^d) | O(d) | Prune hard |
Interview pacing (45-min coding)
- 0-3 min - Restate, constraints, examples, edge cases (empty, n=1, duplicates, negatives).
- 3-8 min - Name the pattern aloud; sketch brute force then optimal complexity target.
- 8-25 min - Code the template; narrate invariants (window valid, stack mono, DP meaning).
- 25-35 min - Dry-run 1-2 examples; fix off-by-ones.
- 35-45 min - Complexity, follow-ups (stream, parallel, memory), tests.
If stuck at 10 min: fall back to correct brute force, then optimize with the pattern map above.
How to drill
- Read sibling When to use + template once.
- Solve 2 Easy + 2 Medium from that doc's LeetCode list timed (25 min each Med).
- Re-implement the template from memory in both Python and TypeScript.
- Spaced repeat: revisit Hard after finishing Graphs + DP hubs.
Cluster map
- Arrays & Two Pointers — Opposite Ends, Same Direction & Partition
- Sliding Window — Fixed & Variable Windows for Subarrays
- Prefix Sums & Difference Arrays — Range Queries in O(1)
- Binary Search & Search-on-Answer — Predicates, Bounds & Feasibility
- Sorting, Intervals & Sweep Line — Merge, Overlap & Events
- Stack & Monotonic Stack — Next Greater, Histograms & Parsing
- Queue, Deque & Monotonic Queue — Sliding Extrema & BFS Helpers
- Linked Lists — Reverse, Merge, Cycle Detection & Dummy Heads
- Binary Trees — DFS (Preorder, Inorder, Postorder; Recursion & Stack)
- Binary Trees — BFS / Level Order — Layers, Width & Zigzag
- Binary Search Trees — Inorder, Bounds, LCA & Validate
- Heaps, Priority Queues & Top-K — n-largest, Merge K & Streaming
- Hashing, Frequency Maps & Counting — Two Sum Family & Anagrams
- Graphs — DFS & BFS Traversal — Components, Cycles & Grid Flood
- Graphs — Topological Sort & DAGs — Kahn, DFS Finish Times & Cycles
- Union-Find (Disjoint Set Union) — Connectivity, Components & Kruskal
- Shortest Paths — Dijkstra, Bellman-Ford & When Not To Use Them
- Dynamic Programming — 1D Patterns — Climb, House Robber, LIS Families
- Dynamic Programming — 2D, Knapsack & Grids — Paths, Subsets & LCS
- Backtracking & Search Trees — Subsets, Permutations, Combinations & Pruning
Go deeper
- LeetCode Explore - curated tracks
- NeetCode roadmap - pattern-ordered practice
- CP-Algorithms - deeper theory (graphs, DSU, shortest paths)
- VisuAlgo - animated DS/algos
- CLRS / Competitive Programming 4 - textbooks for depth (buy/borrow; no piracy links)
Interview Q&A
How do you choose between sliding window and prefix sums?
Answer
Window when constraint is on a contiguous live range you can expand/shrink; prefix when you need many static range sums or difference updates.
When is DFS better than BFS on a graph?
Answer
Path existence / components / topo via finish times; BFS when shortest path in unweighted graphs or level order matters.
Why say search on answer?
Answer
Binary search the answer value when feasible(mid) is monotonic, even if the array is not sorted.
Heap vs sort for top-K?
Answer
Heap O(n log k) and streaming-friendly; full sort O(n log n) if you need total order.
DP vs greedy?
Answer
Greedy needs a proof (exchange/optimal substructure without recomputation); else DP or search.
What do you say first in an interview?
Answer
Constraints, I/O sizes, and the pattern name + target complexity.
Continue to Advanced
The core 20 patterns are this series. Company favorites that sit past them are wave-2: tries, bits, greedy proofs, strings, advanced DP, design, and timed mocks.