Algorithm Cheatsheet
A field guide to the mental models behind every major algorithmic technique — the invariant that makes each one correct, a diagram to make it stick, and runnable code so the idea isn't abstract.
These are the six questions to ask before you pick a technique. Almost every "which pattern do I use?" confusion disappears once you answer them.
1. Monotonicity is the master key
If some quantity only ever moves in one direction as you change an input — a window grows and its sum only grows, an index grows and a predicate flips false → true exactly once — you can almost certainly replace brute force with binary search, two pointers, or a monotonic stack.
predicate(x): F F F F T T T T
index: 0 1 2 3 4 5 6 7
^
the flip point is all you need —
binary search finds it in O(log n)Ask this first, always: "What's monotone here?" Before you write a single line of code, name the thing that only grows, only shrinks, or only flips once. If nothing is monotone, brute force (or DP) is probably unavoidable — but check twice, because monotonicity is often hidden (e.g. "minimum days to ship all packages" isn't obviously monotone until you realize feasibility at capacity C implies feasibility at any capacity > C).
2. Loop invariant
State, in one sentence, what is true at the top of every iteration:
- "Everything left of
iis sorted." - "The stack holds indices with strictly increasing values."
- "
seencontains every value fromnums[0..i-1]."
If you can't write that sentence, the code is probably wrong. If you can, the correctness proof (and the edge cases) fall out almost for free — the invariant tells you what must hold before the loop starts (base case) and what the loop body must preserve (inductive step).
3. State = what you must remember to continue
For DP, BFS, backtracking, and memoization, the state is the minimum information that makes the rest of the problem independent of how you got there (the Markov property — the path to a state doesn't matter, only the state itself).
Choices at Step i
/ \
Option A Option B
\ /
Reaches State (i+1, remaining=5) <-- same state, same future,
regardless of path taken.
Cache the result ONCE.- Too much state → you recompute nothing, cache hit rate is zero, TLE (Time Limit Exceeded).
- Too little state → two genuinely different situations collide in the cache, wrong answers.
The design skill of DP is finding the smallest state that's still sufficient.
4. Complement counting
"Count things with property P" is often easier as:
count(has property P) = total − count(does NOT have property P)
The same idea, run in reverse, turns hard problems easy: deleting edges from a graph one at a time is hard to reason about incrementally; adding them back in reverse order with Union-Find is easy, because Union-Find only knows how to merge, never split. So process queries backwards.
5. Reduce to something known
Many "novel" problems are a classic problem wearing a costume:
| Disguised as… | Really is… |
|---|---|
| "Minimum swaps to sort an array" | Cycle counting in the permutation graph |
| "Schedule jobs to minimize missed deadlines" | Greedy + max-heap (or min-heap of finish times) |
| "Shortest path with at most K stops" | BFS/Bellman-Ford on the state (node, stops_used) |
| "Word Ladder" | BFS on an implicit graph where nodes are words |
Before designing a new algorithm, spend 30 seconds asking "have I seen this shape before, under a different name?"
6. Brute force first, then ask what's repeated
Always write the O(n²) or O(2ⁿ) brute force in your head (or on paper) first. Then ask exactly one question:
- "Where am I recomputing the same thing?" → prefix sums, memoization, hashing.
- "Which branches can never win, so I can stop exploring them?" → pruning, greedy, monotonic stacks.
The optimized algorithm is almost always the brute force with one of those two questions answered.
Each technique below follows the same shape: the invariant, a diagram, the mental trick, and runnable code.
1. Sliding Window — The Accordion Principle
Invariant: monotonic expansion until valid, monotonic contraction until optimal. This only works when validity is monotone in window size (Principle #1 above).
[ L . . . . . R ] ---> expand R to reach validity
[ L . . R ] ---> shrink L to eliminate redundancy,
re-checking optimality at every valid stepMental trick: ask "if I move the right pointer right, does my metric change in only one direction?" If yes — sliding window beats brute force O(n²) scanning.
| 1 | def min_window_length_at_least_k_distinct(s: str, k: int) -> int: |
| 2 | """Smallest window containing at least k distinct characters.""" |
| 3 | from collections import defaultdict |
| 4 | |
| 5 | counts = defaultdict(int) |
| 6 | left = 0 |
| 7 | best = float("inf") |
| 8 | distinct = 0 |
| 9 | |
| 10 | for right, ch in enumerate(s): |
| 11 | counts[ch] += 1 |
| 12 | if counts[ch] == 1: |
| 13 | distinct += 1 |
| 14 | |
| 15 | # Shrink while the window is still valid, to find the minimum. |
| 16 | while distinct >= k: |
| 17 | best = min(best, right - left + 1) |
| 18 | counts[s[left]] -= 1 |
| 19 | if counts[s[left]] == 0: |
| 20 | distinct -= 1 |
| 21 | left += 1 |
| 22 | |
| 23 | return best if best != float("inf") else -1 |
One-time trick — "exactly K" from "at most K":
| 1 | # "Subarrays with exactly K distinct integers" |
| 2 | # is hard to track directly, but: |
| 3 | # exactly(K) == at_most(K) - at_most(K - 1) |
| 4 | # and at_most(K) is a standard shrinking window. |
| 5 | |
| 6 | def subarrays_with_exactly_k_distinct(nums, k): |
| 7 | def at_most(k): |
| 8 | from collections import defaultdict |
| 9 | count = defaultdict(int) |
| 10 | left = 0 |
| 11 | total = 0 |
| 12 | for right, num in enumerate(nums): |
| 13 | count[num] += 1 |
| 14 | while len(count) > k: |
| 15 | count[nums[left]] -= 1 |
| 16 | if count[nums[left]] == 0: |
| 17 | del count[nums[left]] |
| 18 | left += 1 |
| 19 | total += right - left + 1 # every subarray ending at `right` |
| 20 | return total |
| 21 | |
| 22 | return at_most(k) - at_most(k - 1) |
2. Two Pointers — The Monotonic Squeeze
Invariant: moving a pointer inward permanently eliminates an entire row or column of impossible combinations — you never have to check them again.
sorted array: [1, 3, 5, 7, 9, 11]
L R sum too big →
decrementing R eliminates EVERY
pair (L, anything > R) at once,
because array[L] only grows
as L increases.Mental trick: on a sorted array, if array[left] + array[right] > target, moving left right only makes the sum bigger — so right can never pair validly with anything to its own right again. Decrement right and you've eliminated an entire set of candidates in O(1).
| 1 | def two_sum_sorted(nums: list[int], target: int) -> list[int]: |
| 2 | left, right = 0, len(nums) - 1 |
| 3 | while left < right: |
| 4 | total = nums[left] + nums[right] |
| 5 | if total == target: |
| 6 | return [left, right] |
| 7 | elif total < target: |
| 8 | left += 1 # need a bigger sum |
| 9 | else: |
| 10 | right -= 1 # need a smaller sum |
| 11 | return [] |
3. Binary Search — The Monotonic Light Switch
Invariant: binary search does not require a sorted array. It requires a monotonic predicate — a true/false condition that flips exactly once and stays flipped.
Search space: [ F, F, F, T, T, T ]
^
the boundary you're hunting forBinary search on the answer: if checking "is X achievable?" is cheap and monotone, binary search X even when nothing in the input is literally sorted (minimum max-load, minimum days to ship, minimum eating speed…).
Mental trick — the guardrail invariant: keep lo pointing at a known-invalid value and hi at a known-valid value. Loop while lo < hi. You will never hit an infinite loop or an off-by-one.
| 1 | def ship_within_days(weights: list[int], days: int) -> int: |
| 2 | """Minimum ship capacity so all packages ship within `days` days |
| 3 | (LeetCode 1011). Classic binary-search-on-the-answer.""" |
| 4 | |
| 5 | def days_needed(capacity: int) -> int: |
| 6 | days_used, current_load = 1, 0 |
| 7 | for w in weights: |
| 8 | if current_load + w > capacity: |
| 9 | days_used += 1 |
| 10 | current_load = 0 |
| 11 | current_load += w |
| 12 | return days_used |
| 13 | |
| 14 | lo, hi = max(weights), sum(weights) # lo: too small to be feasible in general |
| 15 | while lo < hi: # hi: always feasible (ship everything in 1 day) |
| 16 | mid = (lo + hi) // 2 |
| 17 | if days_needed(mid) <= days: |
| 18 | hi = mid # mid works — try to do even better |
| 19 | else: |
| 20 | lo = mid + 1 # mid fails — need more capacity |
| 21 | return lo |
4. Dynamic Programming — The State Snapshot Rule
Invariant: how you arrived at a state doesn't matter — only what resources remain at that state matters (see Principle #3).
Mental trick — finding the recurrence: think about the last decision, not the first. "What is the final choice in an optimal solution?" usually hands you the recurrence directly: the last item taken or skipped, the last cut position, the last character matched.
| 1 | def coin_change(coins: list[int], amount: int) -> int: |
| 2 | """Fewest coins to make `amount`. dp[a] = min coins to make amount a.""" |
| 3 | INF = float("inf") |
| 4 | dp = [0] + [INF] * amount |
| 5 | |
| 6 | for a in range(1, amount + 1): |
| 7 | for c in coins: |
| 8 | if c <= a and dp[a - c] + 1 < dp[a]: |
| 9 | dp[a] = dp[a - c] + 1 # "last decision": use coin c last |
| 10 | |
| 11 | return dp[amount] if dp[amount] != INF else -1 |
Space trick: if dp[i] only ever depends on dp[i-1] (or a fixed window of previous rows), you don't need the full table — keep only the last one or two rows.
| 1 | def climb_stairs(n: int) -> int: |
| 2 | """dp[i] = dp[i-1] + dp[i-2]. Only need the last two values.""" |
| 3 | prev2, prev1 = 1, 1 # dp[0], dp[1] |
| 4 | for _ in range(2, n + 1): |
| 5 | prev2, prev1 = prev1, prev1 + prev2 |
| 6 | return prev1 |
Workflow: write the top-down version with @lru_cache first — it mirrors the recurrence directly and is nearly bug-free. Convert to bottom-up only when you need the space optimization or to shave the recursion constant factor.
| 1 | from functools import lru_cache |
| 2 | |
| 3 | def coin_change_topdown(coins: list[int], amount: int) -> int: |
| 4 | @lru_cache(maxsize=None) |
| 5 | def dp(remaining: int) -> int: |
| 6 | if remaining == 0: |
| 7 | return 0 |
| 8 | if remaining < 0: |
| 9 | return float("inf") |
| 10 | return 1 + min(dp(remaining - c) for c in coins) |
| 11 | |
| 12 | result = dp(amount) |
| 13 | return result if result != float("inf") else -1 |
5. Backtracking — Choose → Explore → Unchoose
Invariant: at every recursive call, the state is exactly what it was before the call once the call returns — nothing leaks between sibling branches.
Pruning tricks:
- Sort first, then you can
breakinstead ofcontinue, and skip duplicate branches withif i > start and a[i] == a[i - 1]: continue. - Check the cheapest constraint first — fail fast before paying the cost of recursing.
| 1 | def subsets_with_dup(nums: list[int]) -> list[list[int]]: |
| 2 | nums.sort() # required for duplicate-skipping to work |
| 3 | result = [] |
| 4 | path = [] |
| 5 | |
| 6 | def backtrack(start: int) -> None: |
| 7 | result.append(path.copy()) # every node of the decision tree is a valid subset |
| 8 | |
| 9 | for i in range(start, len(nums)): |
| 10 | # Skip a sibling that repeats the previous value at this level — |
| 11 | # it would produce a subset identical to one already emitted. |
| 12 | if i > start and nums[i] == nums[i - 1]: |
| 13 | continue |
| 14 | |
| 15 | path.append(nums[i]) # CHOOSE |
| 16 | backtrack(i + 1) # EXPLORE |
| 17 | path.pop() # UNCHOOSE — the state must return to exactly |
| 18 | # what it was before this iteration began |
| 19 | |
| 20 | backtrack(0) |
| 21 | return result |
The 3 Dimensions of Backtracking, and the One-Way Door Principle
Every backtracking call is really making three independent decisions at once. Naming them separately is what makes a broken backtracking solution debuggable:
┌─────────────────────────────────────────────┐
│ 1. DECISION SPACE — what are my choices │
│ at this node? (which index, which │
│ candidate, which branch of the tree) │
├─────────────────────────────────────────────┤
│ 2. PRUNING GATE — is this choice still │
│ legal given everything chosen so far? │
│ Check BEFORE recursing, not after. │
├─────────────────────────────────────────────┤
│ 3. STATE MUTATION & REVERSAL — apply the │
│ choice, recurse into it, then physically │
│ undo it so the parent's state is restored │
│ bit-for-bit. │
└─────────────────────────────────────────────┘- Decision space — enumerate the branches (the
forloop's range). - Pruning gate — the
ifthat decides whether a branch is even worth entering (duplicate skip, capacity check, validity check). - State mutation & reversal —
path.append(x)paired withpath.pop();board[r][c] = 'X'paired withboard[r][c] = '.';visited.add(node)paired withvisited.remove(node).
The One-Way Door Principle: borrowed from decision-making frameworks that distinguish reversible decisions ("two-way doors" — walk through, don't like it, walk back) from irreversible ones ("one-way doors" — no going back).
Every mutation inside a backtracking call must be a two-way door. The entire algorithm depends on being able to undo a choice and try the next sibling as if the first choice never happened. The instant a mutation becomes a one-way door — it can't be cleanly reversed — backtracking degrades into a single irreversible walk down one path of the tree, and every sibling branch silently inherits corrupted state.
BROKEN — a one-way door hiding in the recursion:
def backtrack(start):
if some_condition:
result.append(path.copy())
return # <-- early return SKIPS path.pop()!
for i in range(start, n):
path.append(nums[i])
backtrack(i + 1)
path.pop() # never reached for the early-return case
# above — path now leaks into every
# sibling branch that runs afterward.How to audit any backtracking function for a one-way door: for every mutation (append, dict/set insert, grid write, counter increment), trace every exit path out of the recursive call — the normal fall-through, every early return, every continue, every exception — and confirm the matching undo runs on all of them. If even one exit path skips the undo, that mutation is a one-way door and the algorithm is silently wrong, usually in a way that only shows up on inputs where that early-exit branch actually fires.
6. Greedy — The Exchange Argument
Invariant: making the locally optimal choice never restricts your ability to reach the globally optimal solution.
How to verify greedy is even legal — the exchange argument: "If I swap my greedy choice for whatever an optimal solution chose instead, does the outcome ever get worse?" If swapping never hurts, greedy is provably correct. If swapping can restrict future flexibility, you need DP instead — greedy is not "DP's lazy cousin," it's a much stronger claim that requires its own proof.
Almost every correct greedy starts with a sort. Ask "sort by what?" first — by end time, by ratio, by deadline.
| 1 | def max_non_overlapping_intervals(intervals: list[list[int]]) -> int: |
| 2 | """Classic interval scheduling. Greedy: always keep the interval |
| 3 | that finishes earliest — it leaves the most room for the future. |
| 4 | Exchange argument: swapping it for any other choice can only |
| 5 | finish later, never leaving MORE room.""" |
| 6 | intervals.sort(key=lambda iv: iv[1]) # sort by END time |
| 7 | |
| 8 | count = 0 |
| 9 | last_end = float("-inf") |
| 10 | for start, end in intervals: |
| 11 | if start >= last_end: |
| 12 | count += 1 |
| 13 | last_end = end |
| 14 | |
| 15 | return count |
7. Monotonic Stack / Deque — The Waiting Line ("Bully") Principle
Invariant: elements wait in the stack, in sorted order, until a "dominant" element arrives and evicts them. The instant an element is popped, the element that popped it is the answer for it.
Stack: [8, 6, 4] <-- new element 7 arrives Pop 4: next-greater(4) = 7 Pop 6: next-greater(6) = 7 Push 7: Stack is now [8, 7] (8 survives — nothing has beaten it yet)
| 1 | def next_greater_element(nums: list[int]) -> list[int]: |
| 2 | result = [-1] * len(nums) |
| 3 | stack = [] # holds INDICES, values strictly decreasing bottom→top |
| 4 | |
| 5 | for i, num in enumerate(nums): |
| 6 | # `num` bullies every smaller element waiting in line. |
| 7 | while stack and nums[stack[-1]] < num: |
| 8 | popped_index = stack.pop() |
| 9 | result[popped_index] = num # the popping moment IS the answer |
| 10 | stack.append(i) |
| 11 | |
| 12 | return result |
A monotonic deque is the same idea generalized to sliding windows: it holds the candidates that could still possibly win, in decreasing order, and pops from the front once a candidate ages out of the window.
| 1 | from collections import deque |
| 2 | |
| 3 | def sliding_window_maximum(nums: list[int], k: int) -> list[int]: |
| 4 | dq = deque() # holds indices, nums[dq[0]] is always the current max |
| 5 | result = [] |
| 6 | |
| 7 | for i, num in enumerate(nums): |
| 8 | while dq and nums[dq[-1]] < num: |
| 9 | dq.pop() # anyone smaller can never win again |
| 10 | dq.append(i) |
| 11 | |
| 12 | if dq[0] <= i - k: |
| 13 | dq.popleft() # front has aged out of the window |
| 14 | |
| 15 | if i >= k - 1: |
| 16 | result.append(nums[dq[0]]) |
| 17 | |
| 18 | return result |
8. Graphs
Reflexes:
| If the problem is… | Use… |
|---|---|
| Shortest path, all edge weights equal | BFS |
| Shortest path, non-negative weights | Dijkstra |
| Shortest path, weights are only 0 or 1 | 0-1 BFS (deque: push 0-weight edges to front, 1-weight to back) |
| "Process in dependency order" | Topological sort (if you can't finish, there's a cycle) |
The graph is often implicit — states are nodes, moves are edges, and you never build an adjacency list explicitly. Word Ladder, sliding-puzzle, knight's-move problems are all just BFS over an implicit state graph.
| 1 | from collections import deque |
| 2 | |
| 3 | def word_ladder_length(begin: str, end: str, word_list: set[str]) -> int: |
| 4 | """BFS over an IMPLICIT graph: nodes are words, edges are |
| 5 | 'differs by exactly one letter'. We never build the adjacency list — |
| 6 | we generate neighbors on the fly.""" |
| 7 | if end not in word_list: |
| 8 | return 0 |
| 9 | |
| 10 | queue = deque([(begin, 1)]) |
| 11 | visited = {begin} |
| 12 | alphabet = "abcdefghijklmnopqrstuvwxyz" |
| 13 | |
| 14 | while queue: |
| 15 | word, steps = queue.popleft() |
| 16 | if word == end: |
| 17 | return steps |
| 18 | |
| 19 | for i in range(len(word)): |
| 20 | for ch in alphabet: |
| 21 | candidate = word[:i] + ch + word[i + 1:] |
| 22 | if candidate in word_list and candidate not in visited: |
| 23 | visited.add(candidate) |
| 24 | queue.append((candidate, steps + 1)) |
| 25 | |
| 26 | return 0 |
9. Union-Find (DSU) — The Representative Rule
Invariant: dynamic connectivity without ever storing explicit edges. Every node points toward a single representative ("the boss") for its group.
Mental trick — merging companies, not employees: you don't link every employee to every other employee in their department. You just merge the two CEOs at the top. Everyone underneath is still "connected" through the chain of parent pointers.
find(x): follow parent pointers up to the root
path compression: flatten the chain so every node it visited
now points DIRECTLY at the root — future
find() calls on those nodes are O(1)-ish
union(x, y): link one root under the other| 1 | class UnionFind: |
| 2 | def __init__(self, n: int): |
| 3 | self.parent = list(range(n)) |
| 4 | self.rank = [0] * n |
| 5 | |
| 6 | def find(self, x: int) -> int: |
| 7 | if self.parent[x] != x: |
| 8 | self.parent[x] = self.find(self.parent[x]) # path compression |
| 9 | return self.parent[x] |
| 10 | |
| 11 | def union(self, x: int, y: int) -> bool: |
| 12 | root_x, root_y = self.find(x), self.find(y) |
| 13 | if root_x == root_y: |
| 14 | return False # already connected — this edge would create a cycle |
| 15 | |
| 16 | # union by rank: attach the shorter tree under the taller one |
| 17 | if self.rank[root_x] < self.rank[root_y]: |
| 18 | root_x, root_y = root_y, root_x |
| 19 | self.parent[root_y] = root_x |
| 20 | if self.rank[root_x] == self.rank[root_y]: |
| 21 | self.rank[root_x] += 1 |
| 22 | return True |
Complement-counting callback (Principle #4): if a problem asks you to delete edges and track connectivity, it's usually easier to process deletions in reverse — start from the fully-deleted graph and add edges back with Union-Find, since Union-Find can merge but never split.
10. Data-Structure Reflexes
Quick lookup table for "I recognize this shape, what tool do I reach for?"
| Shape of the problem | Reach for… |
|---|---|
| Range-sum queries, static array | Prefix sums — O(1) per query after O(n) build |
Range updates (add X to every element in [l, r]) | Difference array — O(1) per update, O(n) to materialize |
| "K largest/smallest elements from a stream" | Heap of size K (min-heap for K largest, max-heap for K smallest) |
| Connectivity that only ever grows (edges only added) | Union-Find |
| "Does this substring/subarray exist / repeat?" | Hashing — rolling hash, or hash of prefix sums for subarray-sum problems |
| 1 | def prefix_sum_range_query(nums: list[int]): |
| 2 | """O(n) build, O(1) per range-sum query.""" |
| 3 | prefix = [0] * (len(nums) + 1) |
| 4 | for i, num in enumerate(nums): |
| 5 | prefix[i + 1] = prefix[i] + num |
| 6 | |
| 7 | def range_sum(left: int, right: int) -> int: # inclusive [left, right] |
| 8 | return prefix[right + 1] - prefix[left] |
| 9 | |
| 10 | return range_sum |
| 11 | |
| 12 | |
| 13 | def difference_array_range_update(n: int, updates: list[tuple[int, int, int]]) -> list[int]: |
| 14 | """Apply `add` to every index in [l, r] for each (l, r, add) in O(1) each, |
| 15 | then materialize the final array in one O(n) pass.""" |
| 16 | diff = [0] * (n + 1) |
| 17 | for l, r, add in updates: |
| 18 | diff[l] += add |
| 19 | diff[r + 1] -= add |
| 20 | |
| 21 | result = [0] * n |
| 22 | running = 0 |
| 23 | for i in range(n): |
| 24 | running += diff[i] |
| 25 | result[i] = running |
| 26 | return result |
Quick-Reference: Technique → Trigger Phrase
| You hear / see… | Think… |
|---|---|
| "Contiguous subarray/substring", "at most K", "longest/shortest window" | Sliding window |
| "Sorted array", "pair that sums to…" | Two pointers |
| "Minimize the maximum" / "maximize the minimum" | Binary search on the answer |
| "Number of ways to…", "minimum cost to reach…" | Dynamic programming |
| "All subsets/permutations/combinations" | Backtracking |
| "Interval scheduling", "minimum number of X to cover Y" | Greedy (prove it with an exchange argument first) |
| "Next greater/smaller element" | Monotonic stack |
| "Sliding window maximum/minimum" | Monotonic deque |
| "Shortest path", "fewest steps" | BFS (unweighted) / Dijkstra (weighted, non-negative) |
| "Are these connected?", "will adding this edge create a cycle?" | Union-Find |
| "Range sum", "range update" | Prefix sums / difference array |