17 — Patterns Cheatsheet

The single page you'll come back to most often. Read a problem → identify the pattern → reach for the template.

The Trigger Lookup Table
Decision tree: which pattern?
Templates at a glance
Complexity targets per input size
Pattern → Pattern dependencies

1. The Trigger Lookup Table

Read the problem statement and look for these key phrases.

Phrase / shape	Pattern	File
"Two Sum"-style lookup, "find pair with property"	Hashmap (or two pointers if sorted)	01, 02
"anagram", "duplicate", "frequency"	Counter / hash	01
"sum of subarray", "range sum query"	Prefix sums	01
"find pair / triplet sum" in sorted array	Two pointers (opposing)	02
"in-place modify, keep order"	Two pointers (same direction)	02
"longest/shortest substring with property"	Sliding window	03
"window of size k" / "k consecutive"	Fixed sliding window	03
"max/min of every k-window"	Monotonic deque	03
"next greater / previous smaller / span / largest rectangle"	Monotonic stack	04
"matching parens / brackets / RPN"	Stack (LIFO)	04
"find target in sorted" / "rotation point"	Binary search	05
"minimize max" / "maximize min" with a feasibility check	Binary search on answer	05
"cycle in linked list / find middle"	Fast & slow pointers	06
"Nth from end of linked list"	Two-pointer gap	06
"build / mutate / reverse linked list"	Dummy head + four-line reversal	06
"LRU / O(1) get-set-evict cache"	Doubly linked list + hashmap	06
"level order / right side view / minimum depth"	BFS on tree	07
"compute X for each subtree"	Postorder DFS	07
"diameter / max path sum"	Local + global tracker	07
"validate BST / kth smallest in BST"	Inorder + bounds	07
"autocomplete / prefix dictionary / starts-with"	Trie	08
"word search II (multiple words on grid)"	Trie + grid DFS	08
"K largest / smallest / closest / frequent"	Heap of size k	09
"running median / two halves"	Two heaps	09
"merge K sorted lists / arrays"	Heap of heads	09
"schedule tasks with cooldown"	Heap + queue	09
"all subsets / permutations / combinations"	Backtracking	10
"n-queens / sudoku / word search (grid)"	Backtracking with constraints	10
"shortest path in unweighted graph / grid"	BFS	11
"shortest in grid where blocked / walls"	BFS	11
"all reachable / connected components / islands"	DFS / BFS	11
"course prerequisites / topological order"	Topological sort (Kahn or DFS)	11
"shortest path with non-negative weights"	Dijkstra	12
"shortest path with negative weights"	Bellman-Ford	12
"shortest with at most k edges/stops"	Bellman-Ford with k iterations	12
"merge sets / detect cycle in undirected"	Union-Find	12
"minimum spanning tree"	Kruskal (Union-Find) or Prim (heap)	12
"count ways / number of paths"	DP	13, 14
"min cost / max profit with overlapping subproblems"	DP	13, 14
"knapsack / subset sum / target sum"	0/1 knapsack DP	14
"edit distance / LCS / interleave"	2D string DP	14
"burst balloons / matrix chain"	Interval DP	14
"merge / overlap / schedule intervals"	Sort + greedy sweep	15
"all sources spread simultaneously"	Multi-source BFS	11
"find single element among duplicates"	XOR	16
"n ≤ 20 with subsets / states"	Bitmask DP	16

2. Decision tree: which pattern?

START
  │
  ├── Linked list given? ───────────── 06-linked-list.md
  │     ├── needs in-place reverse? → 4-line reversal
  │     ├── cycle? middle? Nth?       → fast/slow pointers
  │     └── O(1) cache?               → DLL + hashmap (LRU)
  │
  ├── Tree given? ────────────────── 07-trees.md
  │     ├── BST?                       → inorder gives sorted
  │     ├── level-by-level?            → BFS
  │     ├── compute for each subtree?  → postorder DFS
  │     └── diameter / max path?       → local + global
  │
  ├── Graph or grid? ───────────────── 11/12
  │     ├── unweighted shortest?       → BFS
  │     ├── weighted, ≥0?              → Dijkstra
  │     ├── weights with negatives?    → Bellman-Ford
  │     ├── all reachable?             → DFS / BFS
  │     ├── ordering of dependencies?  → topo sort
  │     └── merge groups / cycle in undirected? → Union-Find
  │
  ├── Sorted array / monotonic answer? ─ 05-binary-search.md
  │     ├── find element / boundary?   → binary search
  │     └── "min X to do Y" feasibility? → BS on answer
  │
  ├── "Best subarray / substring with property"? ─ 02 / 03
  │     ├── pair / triplet sum (sorted)? → two pointers
  │     └── window with constraint?    → sliding window
  │
  ├── "Top K / kth / median"? ──────── 09-heaps.md
  │     └── heap (size k) or two heaps
  │
  ├── "All subsets / permutations / combinations"? ── 10
  │     └── backtracking
  │
  ├── "Min/max cost or count of ways"
  │   with overlapping sub-decisions? ─ 13/14 (DP)
  │     ├── 1D state (linear)?         → 13-dp-1d.md
  │     ├── 2D state (two indices, knapsack)? → 14-dp-2d.md
  │     └── intervals?                 → interval DP
  │
  ├── "Schedule / overlap / merge intervals"? ── 15
  │     └── sort by start or end + greedy sweep
  │
  ├── "Find unique / count bits / power of 2"? ── 16
  │     └── bit tricks
  │
  └── (none of the above)
        ├── n ≤ 12         → maybe brute force / backtracking
        ├── n ≤ 1e3        → O(n²) DP / two-loops fine
        └── n ≤ 1e5        → must be O(n log n) or better

3. Templates at a glance

Two pointers (opposing)

l, r = 0, len(arr) - 1
while l < r:
    if arr[l] + arr[r] == target: ...
    elif arr[l] + arr[r] < target: l += 1
    else: r -= 1

Sliding window (variable longest)

l = 0
state = init()
best = 0
for r, x in enumerate(arr):
    add(x)
    while not valid(state):
        remove(arr[l]); l += 1
    best = max(best, r - l + 1)

Binary search (predicate / lower_bound)

lo, hi = 0, len(arr)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if P(mid): hi = mid
    else: lo = mid + 1
return lo

BFS

from collections import deque
q = deque([start])
visited = {start}
while q:
    n = q.popleft()
    for nbr in neighbors(n):
        if nbr not in visited:
            visited.add(nbr)
            q.append(nbr)

DFS (iterative or recursive)

def dfs(node):
    if base_case: return
    visited.add(node)
    for nbr in neighbors(node):
        if nbr not in visited: dfs(nbr)

Backtracking

def bt(state):
    if is_solution(state):
        record(state); return
    for choice in choices(state):
        if not valid(choice, state): continue
        apply(choice, state)
        bt(state)
        undo(choice, state)

Heap (top-K largest)

import heapq
h = []
for x in nums:
    if len(h) < k: heapq.heappush(h, x)
    elif x > h[0]: heapq.heapreplace(h, x)
return list(h)

Topological sort (Kahn)

indeg = [...]
q = deque(v for v in nodes if indeg[v] == 0)
order = []
while q:
    v = q.popleft(); order.append(v)
    for nbr in graph[v]:
        indeg[nbr] -= 1
        if indeg[nbr] == 0: q.append(nbr)
# valid if len(order) == n

Dijkstra

import heapq
dist = {start: 0}
pq = [(0, start)]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist.get(u, float('inf')): continue
    for v, w in graph[u]:
        nd = d + w
        if nd < dist.get(v, float('inf')):
            dist[v] = nd
            heapq.heappush(pq, (nd, v))

Union-Find

parent = list(range(n))
rank = [0] * n

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return False
    if rank[rx] < rank[ry]: rx, ry = ry, rx
    parent[ry] = rx
    if rank[rx] == rank[ry]: rank[rx] += 1
    return True

DP (1D / 2D)

# Bottom-up template
dp = [base for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i] = recurrence(dp, i)
return dp[n]

# Top-down template
@lru_cache(maxsize=None)
def f(state):
    if base_case(state): return base_value
    return combine(f(smaller_state) for ...)

Monotonic stack (next greater)

stack = []                 # decreasing values, top-down
res = [0] * n
for i, x in enumerate(arr):
    while stack and arr[stack[-1]] < x:
        j = stack.pop()
        res[j] = x or i - j
    stack.append(i)

4. Complexity targets per input size

n upper bound	acceptable complexity	typical algorithm
10	O(n!)	brute permutations
20	O(2ⁿ)	bitmask, backtracking
100	O(n⁴)	obscure DPs
500	O(n³)	Floyd-Warshall, MCM
5,000	O(n²)	DP, two-loops
100,000	O(n log n)	sort + scan, heap, balanced tree
10⁶+	O(n)	linear scan, hash, single-pass
10⁸+	O(log n) per query	binary search, segment tree

If you find your solution exceeds the budget, that's the signal to change patterns.

5. Pattern → Pattern dependencies

foundations
   │
   ├── arrays-hashing ──────┐
   ├── two-pointers         │
   ├── sliding-window       │
   ├── stack                │
   ├── binary-search ◄──────┤  (BS-on-answer reuses arrays)
   ├── linked-list          │
   ├── trees ◄──────────────┤  (use stack / queue)
   ├── tries ◄──────────────┤  (use trees)
   ├── heaps ◄──────────────┤  (use trees)
   ├── backtracking         │
   ├── graphs ◄─────────────┤  (BFS uses queue, DFS uses stack)
   ├── advanced-graphs ◄────┤  (Dijkstra = heap; Union-Find = forest)
   ├── dp-1d ◄──────────────┤  (foundations + recursion)
   ├── dp-2d ◄──────────────┤  (extends dp-1d)
   ├── greedy-intervals     │
   └── bit-manipulation

Master the linear chain top-to-bottom and you can read any LeetCode problem.

6. The 60-second decision

When you read a problem, give yourself 60 seconds:

00–20s   Read carefully. Identify input shape and size.
20–40s   Match against this cheatsheet's triggers.
40–60s   Articulate (out loud, even alone) the chosen pattern + complexity.

If at 60s you have no candidate, state that to the interviewer and ask clarifying questions while you think.

If you have one, sketch the template and start filling in.

TL;DR ✅

This file is the TL;DR.

But if you must memorize three things:

Two pointers + sliding window solves most array/string subproblems.
BFS / DFS / topological sort plus Dijkstra / Union-Find covers all graphs.
DP = optimal substructure + overlapping subproblems, written top-down or bottom-up.

Everything else is variation.

Next: 18-interview-strategy.md.