ASAPUtils
DSA Cheat Sheet
Signal to pattern, constraints to complexity, and the core algorithm templates in C++ and JavaScript. Built to be re-readable in ten minutes on the morning of an interview.
Constraints → target complexity
Read n from the constraints before you think about an
algorithm. If your idea is one tier slower than this table allows, it is the wrong idea.
| n up to | Allowed |
|---|---|
| 10–12 | O(n!) |
| 15–22 | O(2ⁿ) |
| 100 | O(n³) |
| 1,000–5,000 | O(n²) |
| 10⁵–10⁶ | O(n log n) |
| 10⁷–10⁸ | O(n) |
| 10⁹+ | O(log n) or O(1) |
Signal → pattern
The lookup table that turns "I have no idea" into "this is a sliding window". If two
patterns fit, prefer the one with better complexity for the given n.
| What the problem says | Reach for |
|---|---|
| "sorted array", find a pair or triplet | Two pointers (opposite ends) |
| "sorted", find a value or a boundary | Binary search |
| "minimum X such that it is possible" / monotone yes-no | Binary search on the answer |
| "subarray or substring of size k" | Fixed sliding window |
| "longest/shortest ... such that" | Variable sliding window |
| "how many subarrays sum to k" | Prefix sum + hash map |
| "count / duplicate / anagram / seen before" | Hash map or set |
| "next greater / next smaller / warmer / histogram" | Monotonic stack |
| "k largest / k smallest / k closest / running median" | Heap of size k (or two heaps) |
| "merge k sorted things" | Heap (k-way merge) |
| "cycle / middle / n-th from end" in a linked list | Fast & slow pointers |
| "reverse a list or sublist" | prev/curr/next in-place reversal |
| numbers are 1..n, find missing or duplicate | Cyclic sort, or XOR |
| anything per-node needing subtree information | Tree DFS (postorder) |
| "level", "depth", "right side view", "min depth" | Tree BFS (queue) |
| "shortest path" unweighted, "fewest steps", spread over time | Graph BFS |
| "connected components / islands / flood fill / reachable" | Graph DFS or union-find |
| "prerequisite / dependency / valid order" | Topological sort |
| edges added over time, "are these connected?", cycle in undirected | Union-find |
| weighted shortest path, min cost to connect | Dijkstra / Prim |
| "all combinations / permutations / subsets / place N of them" | Backtracking |
| "max/min/count of ways" + overlapping subproblems | Dynamic programming |
| "max/min" + a provably safe local choice | Greedy |
| two strings compared position by position | 2-D DP |
| intervals, overlaps, meetings | Sort by start, then sweep |
| "without extra space", "constant space", XOR-ish | Bit manipulation |
The 8 inputs that break solutions
Run these mentally before you say "done".
- Empty input ([], "", null root)
- One element
- Two elements — many two-pointer and midpoint bugs live here
- All identical elements
- Already sorted, and reverse sorted
- Negative numbers and zero — kills "initialise to 0" solutions
- The maximum size in the constraints — does it TLE? does it overflow?
- Duplicates, when the problem never said there were none
Interview script
Say these out loud, in this order.
- Restate the problem in your own words. Confirm one example.
- Clarify: input size? sorted? duplicates? negatives? what if empty?
- State the brute force and its complexity. Never skip this.
- Ask what the brute force is wasting — that is where the optimisation is.
- State the approach and complexity, and get a nod, before writing code.
- Code it, narrating as you go.
- Trace it on the example, out loud, line by line.
- Run the edge cases above.
- State final time and space complexity, and one thing you would improve.
Coming as the weeks land
Templates for two pointers, sliding window, binary search, monotonic stack, tree DFS and BFS, graph BFS and DFS, topological sort, union-find, backtracking, and the DP ladder — each in C++ and JavaScript — get added here in the week that covers them, so this page only ever contains patterns you have actually worked through.
Start with how to read a problem and Big-O & reading constraints.