Cheatsheet
Pattern Tips
Trigger words in the problem statement → the technique they usually point to. Scan this before every practice session.
sorted
Binary search O(log n) or two pointers O(n) — never start with a linear scan.
subarray / substring
All-positive or monotonic window → sliding window. Sums can dip negative → prefix sum + hashmap.
top K / Kth
Size-K min-heap → O(n log k). Kth only, order irrelevant → quickselect, O(n) average.
tree
Paths, subtree values → DFS recursion. Levels, min depth, views → BFS queue.
shortest path
Unweighted → BFS. Weights ≥ 0 → Dijkstra. Negative edges → Bellman-Ford.
all possibilities
Backtracking: choose → recurse → undo. Prune invalid branches before recursing.
overlapping subproblems
DP: define state, recurrence, base case. Write top-down memo first, tabulate after.
parentheses / nesting
Stack: push openers, match on closers. Next greater/smaller → monotonic stack.
connected components
Edges arrive over time → Union Find. Static grid/graph → DFS/BFS flood fill.
frequency / duplicates
HashMap counts; int[26] for lowercase letters; a seen-set for existence checks.
in-place, O(1) space
Two pointers + swap, or encode extra state inside the array (signs, index mapping).
linked list middle / cycle
Fast & slow pointers: they meet → cycle; fast hits null → slow is at the middle.
exactly K distinct
exactly(K) = atMost(K) − atMost(K−1), each a standard O(n) sliding window.
stuck? start brute force
State the O(n²) solution and its bottleneck, then cut it with sort / hash / window / heap.
complexity from constraints
n ≤ 20 → O(2ⁿ) fine; n ≤ 10⁵ → O(n log n); n ≥ 10⁶ → O(n) or O(log n).