Core · 04/05 8 min
DSA pattern cheat sheet
Signals in the problem statement → the pattern to reach for, with complexity.
| When you see… | Think | Typical cost |
|---|---|---|
| "pair / complement / seen before" | hash map | O(n) |
| "contiguous subarray sums to k" | prefix sums + map | O(n) |
| "longest/shortest substring with…" | sliding window | O(n) |
| sorted array, pairs/triplets | two pointers | O(n) / O(n²) |
| "minimum capacity / speed such that…" | binary search on the answer | O(n log range) |
| sorted but rotated | modified binary search | O(log n) |
| "next greater / warmer / higher" | monotonic stack | O(n) |
| matching brackets, undo | stack | O(n) |
| "k largest / closest / most frequent" | heap of size k | O(n log k) |
| always combine the two smallest | min-heap (greedy) | O(n log n) |
| overlapping intervals, rooms | sort by start, sweep | O(n log n) |
| grid, shortest steps | BFS | O(R·C) |
| connected regions | DFS/BFS flood fill or union-find | O(R·C) |
| dependencies / ordering | topological sort (Kahn) | O(V+E) |
| "number of ways / minimum cost" with overlapping subproblems | DP | varies |
How to talk through a problem
- Restate it and confirm edge cases (empty input, duplicates, negatives).
- Give the brute force and its complexity, briefly.
- Name the bottleneck, then the pattern that removes it.
- Code it cleanly; walk one example by hand.
- State final time and space complexity.
Practise it now
Next in Core
Building from a spec