Leetcode Problems Cheatsheet
Pattern recognition guide for coding interviews — identify which algorithm or data structure to use based on problem keywords
If the problem says... → Use...
| If the problem says... | → Use... |
|---|---|
| subarray / prefix / in-place / two pointers | Arrays & Strings |
| count / frequency / duplicates / anagram | Hash Table / Counter |
| next/prev pointer / reverse / cycle | Linked List |
| k-th / top-k / stream median / merge k lists | Heap (often 1 or 2 heaps) |
| shortest path / hops / weighted graph | BFS (unweighted) / Dijkstra (pos weights) / Bellman-Ford (neg or "≤k edges") |
| prereqs / ordering / DAG | Topological sort (Kahn) |
| connected components / provinces | Union-Find (Disjoint Set) |
| #ways / min cost / max profit / longest | Dynamic Programming |
| all combinations / generate all / choose | Backtracking |
| If the problem says... | → Use... |
|---|---|
| tree traversal / depth / validate BST | Tree recursion / BFS levels |
| O(log n) | Binary Search (templates) |
| Contiguous subarray/substring | Sliding Window |
| Next greater/smaller element | Monotonic Stack |
| Meetings / Time intervals | Sorting + Interval Merge |
| Prefix / Word search | Trie (Prefix Tree) |
| Bitwise / Set bits | Bit Manipulation |
| Smallest missing positive / Duplicate | Cyclic Sort |
| Find the middle / Cycle detection | Fast & Slow Pointers (Tortoise/Hare) |
Pattern Deep Dives
- Two pointers (ends): reverse, palindrome, swap-to-middle
- Two pointers (slow/fast): remove elements in-place, dedupe
- Prefix sums: pivot index, subarray sums
- Use for: counts, membership, mapping to indices
- Collision is a detail; your job is using dict/set/Counter effectively.
- Patterns: fast/slow cycle, reverse, swap pairs
- Best for: top-k, merge-k, stream median (two heaps)
- Array index math:
left = 2*i + 1
right = 2*i + 2
parent = (i-1) // 2- Node stores "next pointers" + end flag
- Replace Words pattern:
- Build trie from roots
- For each word, walk until end==True → replace with that prefix
- Pre/In/Post order: (Root-L-R) / (L-Root-R) / (L-R-Root)
- BFS-level order for depth, layers, shortest path in tree
- BFS: unweighted shortest path
- DFS: explore / connected components / all paths (careful: "all paths" can blow up)
- Union-Find: connectivity merges (provinces)
- Toposort: ordering with prereqs (DAG)
- Dijkstra vs Bellman-Ford:• Dijkstra: positive weights• Bellman-Ford: negative weights or "relax edges with iteration control"; copy trick for "≤k edges"
- Selection: in-place, not stable, O(n²)
- Bubble: stable, O(n²)
- Insertion: stable, good for small/nearly-sorted
- Merge sort: stable, O(n log n), extra O(n)
- Quick sort: avg O(n log n), worst O(n²), in-place-ish (stack)
- Counting/Radix/Bucket: special constraints (bounded keys / digit-based / distributions)
Pro-Tip: The 'Constraint' Pattern
Sometimes the pattern isn't in the words, but in the Time Complexity required. Look at the input size constraint to narrow down the approach:
→ Backtracking
Exponential time is acceptable for small N. Think DFS with exploration.
→ O(N³)
Often Floyd-Warshall (all-pairs shortest path) or triple-nested DP.
→ O(N log N) or O(N)
Sorting/Heap for O(N log N), or Two Pointers/Sliding Window/Hash Table for O(N).
→ O(log N)
Almost always Binary Search. Massive N means you can't iterate linearly.
Quick Reference by Category
Data Structures
Algorithms
Common Interview Patterns
Contiguous subarray/substring with a condition. Move right to expand, left to contract.
Two indices moving through data. Often on sorted arrays or linked lists.
Cycle detection, finding middle element. Tortoise and hare algorithm.
Next/previous greater/smaller element. Stack maintains increasing/decreasing order.
Sort by start time, then merge overlapping intervals. Classic meeting rooms problem.
Array contains numbers in range [1, N]. Place each number at its correct index.
Preorder, inorder, postorder. Path sums, tree diameter, validate BST.
Subarray sum queries in O(1). Build cumulative sum array first.
'Find first/last', 'minimize maximum', 'maximize minimum'. Master the templates.