10 Algorithm Patterns That Crack Most Coding Problems, Visualized

Two pointers, sliding window, fast and slow pointers, prefix sums, binary search on the answer, monotonic stack, BFS, backtracking, heaps and dynamic programming: how to recognise each one, a live visualization you can poke, and a classic problem solved with it.

48 min read

TL;DR: Most coding problems are not new problems. They are one of about ten patterns wearing a costume. This post covers the ten I reach for most often. For each one you get the signals that give it away, an interactive visualization of it running, a classic problem with a tested Python solution, and why it works, with the complexity.

Every sketch is live: watch it run, then click it to get fresh input.

Table of Contents

  1. Why patterns beat memorising problems
  2. Which pattern? A cheat sheet
  3. Pattern 1: Two pointers
  4. Pattern 2: Sliding window
  5. Pattern 3: Fast and slow pointers
  6. Pattern 4: Prefix sum and hash map
  7. Pattern 5: Binary search on the answer
  8. Pattern 6: Monotonic stack
  9. Pattern 7: BFS by levels
  10. Pattern 8: Backtracking
  11. Pattern 9: Top K with a heap
  12. Pattern 10: Dynamic programming
  13. Complexity at a glance
  14. Honourable mentions
  15. How to practise

Why patterns beat memorising problems

There are thousands of problems on LeetCode and only a handful of ideas underneath them. "Longest substring without repeating characters", "minimum window substring" and "max consecutive ones III" look different, but they are the same algorithm: a window that grows on the right and shrinks on the left.

So the useful skill isn't remembering 500 solutions. It's reading a problem statement and noticing the signal: contiguous, sorted, k-th largest, all combinations, minimum number of steps. Each one points at a pattern, and each pattern comes with a template you've already debugged.

Every pattern below follows the same shape:

  • Signals: the words in a problem that should make you think of it.
  • The idea: the one insight that makes it work.
  • Visualization: a live sketch you can click.
  • Sample problem: a classic, with a Python solution.
  • Why it's correct and how fast it is.

All ten sample solutions in this post were run against LeetCode's own examples and thousands of random inputs checked by brute force, so you can trust them as templates.

Which pattern? A cheat sheet

flowchart LR
  P(["the problem mentions..."])
  P --> A["a pair in a sorted array"] --> TP["1. Two pointers"]
  P --> B["longest / shortest contiguous<br/>subarray or substring"] --> SW["2. Sliding window"]
  P --> C["a linked list cycle,<br/>or its middle"] --> FS["3. Fast and slow pointers"]
  P --> D["count subarrays with sum k,<br/>negatives allowed"] --> PS["4. Prefix sum + hash map"]
  P --> E["the minimum value that works,<br/>or a sorted search"] --> BS["5. Binary search"]
  P --> F["the next greater or<br/>smaller element"] --> MS["6. Monotonic stack"]
  P --> G["fewest steps on a grid<br/>or unweighted graph"] --> BF["7. BFS by levels"]
  P --> H["all subsets, permutations<br/>or combinations"] --> BT["8. Backtracking"]
  P --> I["top k, k-th largest,<br/>k closest"] --> HP["9. Heap"]
  P --> J["fewest / most / number of ways,<br/>with overlapping subproblems"] --> DP["10. Dynamic programming"]

Pattern 1: Two pointers

Signals: the array is sorted, and you're looking for a pair (or triplet) that meets a target. Also: reversing in place, partitioning, or merging two sorted arrays.

The idea: put one pointer at each end. Because the array is sorted, comparing the current sum with the target tells you exactly which pointer to move. If the sum is too small, only moving the left pointer right can make it bigger. If it's too big, only moving the right pointer left can shrink it. Every comparison throws away one element for good, which turns an O(n²) pair search into O(n).

let arr, target, L, R, done, doneAt, t, msg;
function setup() { createCanvas(windowWidth, 274); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 274); }
function reset() {
  const s = new Set();
  while (s.size < 12) s.add(floor(random(1, 60)));
  arr = [...s].sort((a, b) => a - b);
  const i = floor(random(0, 11)), j = floor(random(i + 1, 12));
  target = arr[i] + arr[j];
  L = 0; R = arr.length - 1; done = false; doneAt = -1; t = 0;
  msg = 'start at both ends';
}
function step() {
  const sum = arr[L] + arr[R];
  if (sum === target) { done = true; doneAt = t; msg = arr[L] + ' + ' + arr[R] + ' = ' + target + '  found it'; return; }
  if (sum < target) { msg = arr[L] + ' + ' + arr[R] + ' = ' + sum + ' < ' + target + ': too small, move L right'; L++; }
  else { msg = arr[L] + ' + ' + arr[R] + ' = ' + sum + ' > ' + target + ': too big, move R left'; R--; }
}
function draw() {
  background(22, 24, 29);
  t++;
  if (!done && t % 55 === 0) step();
  if (done && t - doneAt > 160) reset();
  const n = arr.length, cw = min(52, (width - 40) / n), x0 = (width - cw * n) / 2, y = 100;
  textAlign(CENTER, CENTER);
  for (let i = 0; i < n; i++) {
    const out = i < L || i > R, hit = done && (i === L || i === R);
    noStroke();
    fill(hit ? color(42, 157, 143) : out ? color(34, 38, 46) : color(52, 58, 70));
    rect(x0 + i * cw + 2, y, cw - 4, 44, 6);
    fill(out ? 90 : 235); textSize(min(15, cw / 2.6));
    text(arr[i], x0 + i * cw + cw / 2, y + 22);
    fill(100); textSize(9); text(i, x0 + i * cw + cw / 2, y + 56);
  }
  pointer(x0 + L * cw + cw / 2, y - 8, 'L', color(255, 209, 102));
  pointer(x0 + R * cw + cw / 2, y - 8, 'R', color(239, 71, 111));
  noStroke(); fill(235); textAlign(LEFT, TOP); textSize(constrain(width / 46, 11, 14));
  text('target = ' + target, 16, 12);
  fill(200); text(msg, 16, height - 84, width - 32);
  fill(110); textSize(11); text('every step throws away one element for good: O(n). click for a new array', 16, height - 36, width - 32);
}
function pointer(x, y, label, c) {
  noStroke(); fill(c);
  triangle(x - 7, y - 12, x + 7, y - 12, x, y);
  textAlign(CENTER, BOTTOM); textSize(12); text(label, x, y - 14);
}
function mousePressed() { reset(); }

Sample problem: Two Sum II (LeetCode 167)

Given a 1-indexed, sorted array numbers and a target, return the indices of the two numbers that add up to target. Exactly one solution exists, and you may not use the same element twice.

numbers = [2, 7, 11, 15], target = 9 → [1, 2]

def two_sum(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]  # the problem is 1-indexed
        if s < target:
            lo += 1  # need a bigger sum: only lo can grow it
        else:
            hi -= 1  # need a smaller sum: only hi can shrink it
    return []

Why it's correct: when numbers[lo] + numbers[hi] < target, pairing numbers[lo] with any element left of hi gives an even smaller sum, so numbers[lo] can't be in the answer. Discarding it is safe. The same argument mirrors for hi. O(n) time, O(1) space.

Practise: 3Sum (15), Container With Most Water (11), Valid Palindrome (125).

Pattern 2: Sliding window

Signals: contiguous subarray or substring, plus longest, shortest, at most k, or without repeating.

The idea: keep a window [L, R) that is always valid. Grow it on the right. When adding a character breaks the rule, shrink it from the left until it's valid again. Both pointers only ever move right, so the total work is linear, even though there's a loop inside a loop.

const WORDS = ['abcabcbb', 'pwwkew', 'abcdeafbdgcbb', 'dvdfxyzd'];
let wi = 0, s, L, R, seen, best, bestL, t, doneAt, msg;
function setup() { createCanvas(windowWidth, 284); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 284); }
function reset() {
  s = WORDS[wi]; L = 0; R = 0; seen = new Set(); best = 0; bestL = 0; t = 0; doneAt = -1;
  msg = 'window [L, R) starts empty';
}
function step() {
  if (R >= s.length) { doneAt = t; msg = 'R reached the end: longest = ' + best + ' ("' + s.slice(bestL, bestL + best) + '")'; return; }
  const c = s[R];
  if (!seen.has(c)) {
    seen.add(c); R++;
    if (R - L > best) { best = R - L; bestL = L; }
    msg = "'" + c + "' is new: grow the window to " + (R - L);
  } else {
    msg = "'" + c + "' is already inside: shrink from the left, drop '" + s[L] + "'";
    seen.delete(s[L]); L++;
  }
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 45 === 0) step();
  if (doneAt >= 0 && t - doneAt > 170) { wi = (wi + 1) % WORDS.length; reset(); }
  const n = s.length, cw = min(48, (width - 40) / n), x0 = (width - cw * n) / 2, y = 92;
  // best window so far
  noFill(); stroke(42, 157, 143); strokeWeight(2);
  if (best > 0) rect(x0 + bestL * cw, y + 54, best * cw, 6, 3);
  // current window
  stroke(255, 209, 102); strokeWeight(2);
  if (R > L) rect(x0 + L * cw, y - 6, (R - L) * cw, 56, 8);
  noStroke(); textAlign(CENTER, CENTER);
  for (let i = 0; i < n; i++) {
    const inside = i >= L && i < R, next = i === R && doneAt < 0;
    fill(next ? color(239, 71, 111, 120) : inside ? color(52, 58, 70) : color(34, 38, 46));
    rect(x0 + i * cw + 3, y, cw - 6, 44, 6);
    fill(inside || next ? 235 : 110); textSize(min(18, cw / 2.2));
    text(s[i], x0 + i * cw + cw / 2, y + 22);
  }
  textAlign(LEFT, TOP); textSize(constrain(width / 46, 11, 14)); fill(235);
  text('window = "' + s.slice(L, R) + '"   set = {' + [...seen].join(', ') + '}   best = ' + best, 16, 12, width - 32);
  fill(200); text(msg, 16, height - 84, width - 32);
  fill(110); textSize(11);
  text('yellow: current window   green bar: best window   red: next character. R and L only move right: O(n)', 16, height - 36, width - 32);
}
function mousePressed() { wi = (wi + 1) % WORDS.length; reset(); }

Sample problem: Longest Substring Without Repeating Characters (LeetCode 3)

Given a string s, find the length of the longest substring without repeating characters.

"abcabcbb" → 3 ("abc"), "pwwkew" → 3 ("wke")

The sketch shrinks one character at a time to make the idea visible. In real code you can jump L straight past the duplicate by remembering where you last saw each character:

def length_of_longest_substring(s):
    last = {}  # char -> index where we last saw it
    best = left = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1  # jump past the duplicate in one move
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Why it's linear: each index enters the window once (when right reaches it) and leaves at most once (when left passes it). That's at most 2n pointer moves in total, so O(n) time, and O(alphabet) space for the map.

Practise: Minimum Window Substring (76), Longest Repeating Character Replacement (424), Max Consecutive Ones III (1004).

Pattern 3: Fast and slow pointers

Signals: a linked list (or anything with a next function) where you need to find a cycle, where it starts, or the middle, using O(1) extra memory.

The idea: move a slow pointer one step at a time and a fast pointer two. If there's no cycle, fast falls off the end. If there is one, fast gains one node per step inside the cycle, so it must eventually land on slow. That's Floyd's algorithm. The clever bit is phase 2: put one pointer back at the head, move both one step at a time, and they meet exactly where the cycle begins.

let T, C, pos, slow, fast, phase, t, doneAt, msg, steps;
function setup() { createCanvas(windowWidth, 384); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 384); layout(); }
function reset() {
  T = floor(random(2, 6)); C = floor(random(5, 10));
  slow = 0; fast = 0; phase = 1; t = 0; doneAt = -1; steps = 0;
  msg = 'phase 1: slow moves 1, fast moves 2';
  layout();
}
function next(i) { return i < T + C - 1 ? i + 1 : T; }
function layout() {
  const r = min(95, (height - 140) / 2, (width - 80 - T * 34) / 2), gap = min(54, (width - 2 * r - 80) / max(T, 1));
  const total = T * gap + 2 * r;
  const cx = (width - total) / 2 + T * gap + r, cy = 160;
  pos = [];
  for (let i = 0; i < T; i++) pos.push([cx - r - (T - i) * gap, cy]);
  for (let k = 0; k < C; k++) {
    const a = PI + (TWO_PI * k) / C;
    pos.push([cx + r * cos(a), cy + r * sin(a)]);
  }
}
function step() {
  steps++;
  if (phase === 1) {
    slow = next(slow); fast = next(next(fast));
    if (slow === fast) { phase = 2; msg = 'they met at node ' + slow + ' after ' + steps + ' steps. phase 2: reset one pointer to the head'; fast = slow; slow = 0; }
    else msg = 'phase 1: slow -> ' + slow + ', fast -> ' + fast;
  } else if (phase === 2) {
    if (slow === fast) { phase = 3; doneAt = t; msg = 'both arrive at node ' + slow + ': that is where the cycle starts'; return; }
    slow = next(slow); fast = next(fast);
    msg = 'phase 2: both move 1 step: ' + slow + ' and ' + fast;
  }
}
function arrow(a, b) {
  const [x1, y1] = pos[a], [x2, y2] = pos[b], ang = atan2(y2 - y1, x2 - x1), rr = 15;
  const sx = x1 + cos(ang) * rr, sy = y1 + sin(ang) * rr, ex = x2 - cos(ang) * rr, ey = y2 - sin(ang) * rr;
  stroke(80); strokeWeight(1.5); line(sx, sy, ex, ey);
  noStroke(); fill(80);
  triangle(ex, ey, ex - cos(ang - 0.4) * 8, ey - sin(ang - 0.4) * 8, ex - cos(ang + 0.4) * 8, ey - sin(ang + 0.4) * 8);
}
function draw() {
  background(22, 24, 29);
  t++;
  if (phase < 3 && t % 50 === 0) step();
  if (phase === 3 && t - doneAt > 170) reset();
  for (let i = 0; i < T + C; i++) arrow(i, next(i));
  textAlign(CENTER, CENTER); textSize(11);
  for (let i = 0; i < T + C; i++) {
    const [x, y] = pos[i];
    noStroke();
    fill(phase === 3 && i === T ? color(42, 157, 143) : color(52, 58, 70));
    circle(x, y, 28);
    fill(220); text(i, x, y);
  }
  ring(slow, color(255, 209, 102), 36, 'slow');
  ring(fast, color(239, 71, 111), 44, phase === 1 ? 'fast' : 'meet');
  noStroke(); fill(235); textAlign(LEFT, TOP); textSize(constrain(width / 46, 11, 14));
  text('tail ' + T + ' nodes, cycle ' + C + ' nodes   step ' + steps, 16, 12);
  fill(200); text(msg, 16, height - 84, width - 32);
  fill(110); textSize(11); text('O(1) extra memory: no visited set. click for a new list', 16, height - 36, width - 32);
}
function ring(i, c, d, label) {
  const [x, y] = pos[i];
  noFill(); stroke(c); strokeWeight(3); circle(x, y, d);
  noStroke(); fill(c); textSize(10); textAlign(CENTER, BOTTOM); text(label, x, y - d / 2 - 2);
}
function mousePressed() { reset(); }

Sample problem: Linked List Cycle II (LeetCode 142)

Given the head of a linked list, return the node where the cycle begins, or None if there is no cycle. Use O(1) memory.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:  # phase 1: they met somewhere inside the cycle
            slow = head  # phase 2: one pointer back to the head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow  # where they meet again is the cycle's entry
    return None

Why phase 2 works: say the tail has \mu nodes, the cycle has \lambda, and they meet a steps past the cycle's entry. Slow walked \mu + a steps and fast walked twice that. The extra distance fast covered is whole laps of the cycle:

2(\mu + a) - (\mu + a) = \mu + a = m\lambda \quad\Longrightarrow\quad \mu = m\lambda - a

So walking \mu more steps from the meeting point is m full laps minus a, which lands exactly on the entry. A pointer walking \mu steps from the head lands there too. O(n) time, O(1) space.

Practise: Middle of the Linked List (876), Happy Number (202), Find the Duplicate Number (287).

Pattern 4: Prefix sum and hash map

Signals: count (or find) subarrays whose sum equals k, especially when the array has negative numbers. Sliding window breaks here, because adding a negative can shrink a sum, so a window can't know which way to move.

The idea: a running prefix sum turns "sum of a range" into "difference of two prefixes":

\text{sum}(i..j) = P_j - P_{i-1} = k \quad\Longleftrightarrow\quad P_{i-1} = P_j - k

So as you scan, the number of subarrays ending at j with sum k is just how many earlier prefixes equal P_j - k. A hash map of prefix counts answers that in O(1).

let a, k, i, prefix, pre, seen, count, found, t, doneAt, msg;
const COLORS = [[255, 209, 102], [42, 157, 143], [100, 181, 246], [239, 71, 111], [181, 131, 224]];
function setup() { createCanvas(windowWidth, 344); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 344); }
function reset() {
  a = []; for (let j = 0; j < 10; j++) a.push(floor(random(-3, 6)));
  const s = floor(random(0, 8)), e = floor(random(s + 1, 10));
  k = 0; for (let j = s; j <= e; j++) k += a[j];
  i = -1; prefix = 0; pre = []; seen = new Map([[0, [-1]]]); count = 0; found = []; t = 0; doneAt = -1;
  msg = 'seen = {0: once}: the empty prefix, so a subarray may start at index 0';
}
function step() {
  i++;
  if (i >= a.length) { doneAt = t; msg = 'done: ' + count + ' subarray(s) sum to ' + k + ', in one pass'; return; }
  prefix += a[i]; pre.push(prefix);
  const need = prefix - k, hits = seen.get(need) || [];
  for (const j of hits) found.push([j + 1, i]);
  count += hits.length;
  msg = 'i=' + i + ': prefix ' + prefix + ', need prefix - k = ' + need + (hits.length ? ' -> seen ' + hits.length + 'x, +' + hits.length : ' -> not seen');
  if (!seen.has(prefix)) seen.set(prefix, []);
  seen.get(prefix).push(i);
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 60 === 0) step();
  if (doneAt >= 0 && t - doneAt > 180) reset();
  const n = a.length, cw = min(52, (width - 90) / n), x0 = 70, y = 110;
  textAlign(CENTER, CENTER);
  noStroke(); fill(120); textSize(10); textAlign(RIGHT, CENTER);
  text('nums', x0 - 8, y + 18); text('prefix', x0 - 8, y + 66);
  textAlign(CENTER, CENTER);
  for (let j = 0; j < n; j++) {
    fill(j === i ? color(255, 209, 102, 90) : j < i ? color(52, 58, 70) : color(34, 38, 46));
    rect(x0 + j * cw + 2, y, cw - 4, 36, 5);
    fill(j <= i ? 235 : 120); textSize(min(14, cw / 2.6)); text(a[j], x0 + j * cw + cw / 2, y + 18);
    if (j < pre.length) { fill(160); text(pre[j], x0 + j * cw + cw / 2, y + 66); }
  }
  found.forEach(([s, e], m) => {
    const c = COLORS[m % COLORS.length], yy = y - 12 - (m % 5) * 9;
    stroke(c); strokeWeight(3); line(x0 + s * cw + 4, yy, x0 + (e + 1) * cw - 4, yy);
  });
  noStroke(); textAlign(LEFT, TOP); textSize(11); fill(150);
  const chips = [...seen.entries()].map(([p, v]) => p + ':' + v.length).join('   ');
  text('seen prefix counts   ' + chips, 16, y + 92, width - 32);
  fill(235); textSize(constrain(width / 46, 11, 14));
  text('k = ' + k + '   count = ' + count, 16, 12);
  fill(200); text(msg, 16, height - 84, width - 32);
  fill(110); textSize(11); text('sum(i..j) = prefix[j] - prefix[i-1]. each coloured bar is a subarray found. click for new data', 16, height - 36, width - 32);
}
function mousePressed() { reset(); }

Sample problem: Subarray Sum Equals K (LeetCode 560)

Given an integer array nums (which may contain negatives) and an integer k, return the total number of contiguous subarrays whose sum equals k.

nums = [1, 1, 1], k = 2 → 2

from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1  # the empty prefix: lets a subarray start at index 0
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen[prefix - k]  # every earlier prefix p with prefix - p == k
        seen[prefix] += 1
    return count

The one line people forget is seen[0] = 1. Without it, a subarray that starts at index 0 has no earlier prefix to match against and is never counted. O(n) time, O(n) space.

Practise: Continuous Subarray Sum (523), Contiguous Array (525), Range Sum Query: Immutable (303).

Pattern 5: Binary search on the answer

Signals: a sorted array, obviously. But also, and more usefully: find the minimum speed, capacity, or size such that something is possible. If a value works and every larger value also works, the answer space is monotonic, and you can binary search it even though nothing is sorted.

The idea: every binary search is really one question: where does a boolean flip from false to true? Write feasible(x), then shrink [lo, hi] by half each step until lo == hi. That's at most \lceil \log_2 n \rceil probes instead of n.

In the sketch, each cell is a candidate eating speed k. Red means too slow and green means fast enough. You never need to check most of them:

let piles, h, maxK, lo, hi, probed, t, doneAt, msg, iters;
function setup() { createCanvas(windowWidth, 324); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 324); }
function reset() {
  piles = []; const n = floor(random(3, 6));
  const cap = constrain(floor((width - 40) / 16), 8, 25);
  for (let j = 0; j < n; j++) piles.push(floor(random(3, cap)));
  maxK = max(piles); h = n + floor(random(1, 8));
  lo = 1; hi = maxK; probed = {}; t = 0; doneAt = -1; iters = 0;
  msg = 'speeds 1..' + maxK + ': too slow on the left, fast enough on the right';
}
function hours(k) { let s = 0; for (const p of piles) s += ceil(p / k); return s; }
function step() {
  if (lo >= hi) { doneAt = t; msg = 'lo == hi: the minimum speed is ' + lo + ' (' + iters + ' probes instead of ' + maxK + ')'; return; }
  const mid = floor((lo + hi) / 2), hs = hours(mid), ok = hs <= h;
  probed[mid] = ok; iters++;
  if (ok) { msg = 'k=' + mid + ': ' + hs + ' hours <= ' + h + ', fast enough -> hi = ' + mid; hi = mid; }
  else { msg = 'k=' + mid + ': ' + hs + ' hours > ' + h + ', too slow -> lo = ' + (mid + 1); lo = mid + 1; }
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 60 === 0) step();
  if (doneAt >= 0 && t - doneAt > 180) reset();
  noStroke(); textAlign(LEFT, TOP); fill(235); textSize(constrain(width / 46, 11, 14));
  text('piles [' + piles.join(', ') + ']   hours allowed h = ' + h, 16, 12, width - 32);
  const cw = (width - 40) / maxK, x0 = 20, y = 120;
  textAlign(CENTER, CENTER);
  for (let k = 1; k <= maxK; k++) {
    const x = x0 + (k - 1) * cw, inRange = k >= lo && k <= hi;
    const p = probed[k];
    fill(p === true ? color(42, 157, 143) : p === false ? color(239, 71, 111) : inRange ? color(52, 58, 70) : color(30, 33, 40));
    rect(x + 1, y, max(1, cw - 2), 40, 3);
    if (cw > 14) { fill(inRange || p !== undefined ? 230 : 90); textSize(min(12, cw / 2)); text(k, x + cw / 2, y + 20); }
  }
  mark(x0 + (lo - 0.5) * cw, y + 46, 'lo', color(255, 209, 102));
  mark(x0 + (hi - 0.5) * cw, y + 64, 'hi', color(100, 181, 246));
  if (doneAt >= 0) { noFill(); stroke(255); strokeWeight(2); rect(x0 + (lo - 1) * cw, y - 4, cw, 48, 4); }
  noStroke(); fill(200); textAlign(LEFT, TOP); textSize(constrain(width / 46, 11, 14));
  text(msg, 16, height - 84, width - 32);
  fill(110); textSize(11); text('green: fast enough, red: too slow. each probe halves the range. click for new piles', 16, height - 36, width - 32);
}
function mark(x, y, label, c) { noStroke(); fill(c); triangle(x - 6, y + 10, x + 6, y + 10, x, y); textSize(10); textAlign(CENTER, TOP); text(label, x, y + 11); }
function mousePressed() { reset(); }

Sample problem: Koko Eating Bananas (LeetCode 875)

Koko has piles of bananas and h hours. Each hour she picks one pile and eats k bananas from it (or the whole pile if it has fewer). Return the minimum integer k that lets her finish within h hours.

piles = [3, 6, 7, 11], h = 8 → 4

def min_eating_speed(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)  # ceil without floats

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid  # mid works: the answer is mid or smaller
        else:
            lo = mid + 1  # mid is too slow: the answer is bigger
    return lo

Why it's correct: \text{hours}(k) = \sum_i \lceil p_i / k \rceil can only go down as k goes up, so feasible is false, false, …, true, true. The loop keeps the first true inside [lo, hi] at every step. O(n log m) time, where m is the largest pile.

The template to memorise is the lo < hi, hi = mid / lo = mid + 1 form. It never loops forever and it always lands on the first true.

Practise: Capacity To Ship Packages Within D Days (1011), Search in Rotated Sorted Array (33), Split Array Largest Sum (410).

Pattern 6: Monotonic stack

Signals: the next greater element, the next smaller element, how many days until warmer, the largest rectangle. Anything that asks each element about the nearest element to its right (or left) that beats it.

The idea: keep a stack of indices that are still waiting for an answer. Their values are always in decreasing order, which is what makes it "monotonic". When a new element is bigger than the top of the stack, it is the answer for the top, so pop it and record the distance. Keep popping while it's still bigger, then push the new element so it can wait too.

let temps, ans, stack, i, arcs, t, doneAt, msg;
function setup() { createCanvas(windowWidth, 354); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 354); }
function reset() {
  temps = []; for (let j = 0; j < 10; j++) temps.push(floor(random(60, 80)));
  ans = temps.map(() => null); stack = []; i = 0; arcs = []; t = 0; doneAt = -1;
  msg = 'the stack holds days still waiting for a warmer day, temperatures decreasing';
}
function step() {
  if (i >= temps.length) {
    for (const j of stack) ans[j] = 0;
    doneAt = t; msg = 'end: days left on the stack never get warmer, answer 0. each day pushed and popped once: O(n)'; return;
  }
  const top = stack[stack.length - 1];
  if (stack.length && temps[i] > temps[top]) {
    stack.pop(); ans[top] = i - top; arcs.push([top, i]);
    msg = 'day ' + i + ' (' + temps[i] + ') is warmer than day ' + top + ' (' + temps[top] + '): pop, answer = ' + (i - top);
  } else {
    stack.push(i);
    msg = 'push day ' + i + ' (' + temps[i] + ')' + (stack.length > 1 ? ': not warmer than the top, so it waits too' : '');
    i++;
  }
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 45 === 0) step();
  if (doneAt >= 0 && t - doneAt > 180) reset();
  const n = temps.length, area = width * 0.74, cw = min(54, (area - 30) / n), x0 = 20, base = 230;
  for (const [a, b] of arcs) {
    noFill(); stroke(42, 157, 143, 160); strokeWeight(1.5);
    const xa = x0 + a * cw + cw / 2, xb = x0 + b * cw + cw / 2, ya = base - (temps[a] - 55) * 5;
    arc((xa + xb) / 2, ya - 6, xb - xa, (xb - xa) * 0.5, PI, TWO_PI);
  }
  textAlign(CENTER, CENTER);
  for (let j = 0; j < n; j++) {
    const hgt = (temps[j] - 55) * 5, x = x0 + j * cw;
    noStroke();
    fill(j === i && doneAt < 0 ? color(255, 209, 102) : stack.includes(j) ? color(100, 181, 246) : color(52, 58, 70));
    rect(x + 3, base - hgt, cw - 6, hgt, 4, 4, 0, 0);
    fill(230); textSize(min(11, cw / 3)); text(temps[j], x + cw / 2, base - hgt + 10);
    fill(ans[j] === null ? 80 : color(42, 157, 143)); textSize(12);
    text(ans[j] === null ? '?' : ans[j], x + cw / 2, base + 16);
  }
  fill(120); textSize(10); textAlign(LEFT, CENTER); text('answer', x0, base + 32);
  // the stack
  const sx = x0 + n * cw + 24, sw = width - sx - 16;
  if (sw > 40) {
    fill(150); textSize(10); textAlign(CENTER, BOTTOM); text('stack', sx + sw / 2, base + 2 - stack.length * 22 - 4);
    stack.forEach((j, m) => {
      fill(100, 181, 246); rect(sx, base - (m + 1) * 22, sw, 20, 4);
      fill(20); textAlign(CENTER, CENTER); textSize(11); text('d' + j + ' ' + temps[j], sx + sw / 2, base - (m + 1) * 22 + 10);
    });
  }
  noStroke(); fill(200); textAlign(LEFT, TOP); textSize(constrain(width / 48, 10, 13));
  text(msg, 16, 12, width - 32);
  fill(110); textSize(11); text('yellow: today   blue: waiting on the stack   arcs: answered. click for new temperatures', 16, height - 36, width - 32);
}
function mousePressed() { reset(); }

Sample problem: Daily Temperatures (LeetCode 739)

Given daily temperatures, return an array where answer[i] is the number of days after day i until a warmer temperature, or 0 if there is none.

[73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]

def daily_temperatures(temps):
    ans = [0] * len(temps)
    stack = []  # indices still waiting, temperatures decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

Why it's O(n): there's a while inside a for, but every index is pushed once and popped at most once. That's at most 2n stack operations in total, so O(n) time, O(n) space, instead of the O(n²) "scan right from every day" approach.

Practise: Next Greater Element I (496), Largest Rectangle in Histogram (84), Online Stock Span (901).

Pattern 7: BFS by levels

Signals: the fewest steps, minimum moves or shortest path in a grid or a graph where every edge costs the same. Also anything that spreads one ring at a time: fire, infection, rotting.

The idea: a queue processes nodes in order of distance. Process the queue one whole level at a time (for _ in range(len(q))) and the level counter is the distance. Several starting points? Put them all in the queue at the start. That's a multi-source BFS, and it costs nothing extra.

const COLS = 9, ROWS = 6;
let g, stamp, frontier, minute, t, doneAt, msg;
function setup() { createCanvas(windowWidth, 354); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 354); }
function reset() {
  g = []; stamp = [];
  for (let r = 0; r < ROWS; r++) {
    g.push([]); stamp.push([]);
    for (let c = 0; c < COLS; c++) {
      const x = random();
      g[r].push(x < 0.14 ? 0 : x < 0.2 ? 2 : 1);
      stamp[r].push(g[r][c] === 2 ? 0 : -1);
    }
  }
  g[floor(random(ROWS))][floor(random(COLS))] = 2;
  frontier = [];
  for (let r = 0; r < ROWS; r++) for (let c = 0; c < COLS; c++) if (g[r][c] === 2) { frontier.push([r, c]); stamp[r][c] = 0; }
  minute = 0; t = 0; doneAt = -1;
  msg = 'minute 0: every rotten orange goes into the queue at once (' + frontier.length + ' sources)';
}
function step() {
  const next = [];
  for (const [r, c] of frontier) {
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS && g[nr][nc] === 1) {
        g[nr][nc] = 2; stamp[nr][nc] = minute + 1; next.push([nr, nc]);
      }
    }
  }
  if (!next.length) {
    const fresh = g.flat().filter((v) => v === 1).length;
    doneAt = t;
    msg = fresh ? 'queue empty with ' + fresh + ' fresh orange(s) unreachable: answer -1' : 'queue empty, nothing fresh left: answer ' + minute + ' minutes';
    frontier = []; return;
  }
  minute++; frontier = next;
  msg = 'minute ' + minute + ': ' + next.length + ' orange(s) rot. a whole level of the BFS per minute';
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 55 === 0) step();
  if (doneAt >= 0 && t - doneAt > 180) reset();
  const cs = min(40, (width - 40) / COLS, (height - 150) / ROWS), x0 = (width - cs * COLS) / 2, y0 = 50;
  textAlign(CENTER, CENTER); textSize(min(12, cs / 3));
  for (let r = 0; r < ROWS; r++) for (let c = 0; c < COLS; c++) {
    const v = g[r][c], x = x0 + c * cs, y = y0 + r * cs;
    noStroke(); fill(30, 33, 40); rect(x + 1, y + 1, cs - 2, cs - 2, 4);
    if (v === 1) { fill(120, 190, 90); circle(x + cs / 2, y + cs / 2, cs * 0.7); }
    if (v === 2) {
      const fresh = stamp[r][c] === minute && doneAt < 0;
      fill(fresh ? color(239, 120, 60) : color(140, 95, 50)); circle(x + cs / 2, y + cs / 2, cs * 0.7);
      fill(240); text(stamp[r][c], x + cs / 2, y + cs / 2);
    }
  }
  for (const [r, c] of frontier) { noFill(); stroke(255, 209, 102); strokeWeight(2); circle(x0 + c * cs + cs / 2, y0 + r * cs + cs / 2, cs * 0.85); }
  noStroke(); fill(235); textAlign(LEFT, TOP); textSize(constrain(width / 46, 11, 14));
  text('minute ' + minute + '   queue ' + frontier.length, 16, 12);
  fill(200); text(msg, 16, height - 84, width - 32);
  fill(110); textSize(11); text('green: fresh  brown: rotten (number = minute it rotted)  ring: current queue. click for a new grid', 16, height - 36, width - 32);
}
function mousePressed() { reset(); }

Sample problem: Rotting Oranges (LeetCode 994)

In a grid, 0 is empty, 1 is a fresh orange and 2 is a rotten one. Every minute, each fresh orange next to a rotten one (up, down, left or right) becomes rotten. Return the minutes until no fresh orange is left, or -1 if that's impossible.

[[2,1,1],[1,1,0],[0,1,1]] → 4

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))  # every source starts in the queue
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):  # one whole BFS level = one minute
            r, c = q.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return -1 if fresh else minutes

Why BFS and not DFS: DFS dives down one path and finds a path, not the shortest one. BFS visits everything at distance 1 before anything at distance 2, so the first time it reaches a cell is via a shortest path. O(rows × cols) time and space.

Practise: Number of Islands (200), Shortest Path in Binary Matrix (1091), Word Ladder (127).

Pattern 8: Backtracking

Signals: return all subsets, permutations, combinations or partitions; place N queens; solve a sudoku. Any problem where the answer is every valid arrangement rather than a count of them.

The idea: every answer is a sequence of choices, so the search space is a decision tree. Walk it depth-first with one shared path: choose (append), recurse, un-choose (pop). The un-choose step is the "backtrack". It restores the state so the sibling branch starts clean. Pruning, i.e. skipping branches that can't lead to a valid answer, is what makes the harder versions fast.

const NUMS = [1, 2, 3], N = NUMS.length;
let events, ei, out, visited, t, doneAt;
function setup() { createCanvas(windowWidth, 364); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 364); }
function reset() {
  events = []; out = []; visited = new Set(); ei = 0; t = 0; doneAt = -1;
  (function dfs(path) {
    events.push({ path, type: 'enter' });
    if (path.length === N) { events.push({ path, type: 'emit' }); return; }
    dfs(path + '1'); events.push({ path, type: 'back' });
    dfs(path + '0'); events.push({ path, type: 'back' });
  })('');
}
function setOf(path) { return '{' + NUMS.filter((_, d) => path[d] === '1').join(',') + '}'; }
function nodeXY(path) {
  const d = path.length, leaves = 1 << N, span = leaves >> d;
  let idx = 0; for (const ch of path) idx = idx * 2 + (ch === '1' ? 0 : 1);
  const lw = (width - 40) / leaves;
  return [20 + (idx * span + span / 2) * lw, 60 + d * 62];
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 28 === 0) {
    const e = events[ei++];
    visited.add(e.path);
    if (e.type === 'emit') out.push(setOf(e.path));
    if (ei >= events.length) doneAt = t;
  }
  if (doneAt >= 0 && t - doneAt > 180) reset();
  const cur = events[max(0, ei - 1)];
  // edges
  const all = [];
  (function walk(p) { all.push(p); if (p.length < N) { walk(p + '1'); walk(p + '0'); } })('');
  for (const p of all) {
    if (!p.length) continue;
    const [x1, y1] = nodeXY(p.slice(0, -1)), [x2, y2] = nodeXY(p);
    const onPath = cur && cur.path.startsWith(p);
    stroke(onPath ? color(255, 209, 102) : visited.has(p) ? color(90) : color(48)); strokeWeight(onPath ? 2.5 : 1.2);
    line(x1, y1, x2, y2);
    noStroke(); fill(110); textSize(9); textAlign(CENTER, CENTER);
    text(p.endsWith('1') ? '+' + NUMS[p.length - 1] : 'skip', (x1 + x2) / 2 + (p.endsWith('1') ? -12 : 12), (y1 + y2) / 2);
  }
  for (const p of all) {
    const [x, y] = nodeXY(p), isCur = cur && cur.path === p;
    noStroke();
    fill(isCur ? color(255, 209, 102) : visited.has(p) ? color(70, 78, 92) : color(40, 44, 52));
    circle(x, y, 16);
    if (p.length === N && visited.has(p)) { fill(42, 157, 143); textSize(min(12, (width - 40) / 8 / 4)); textAlign(CENTER, TOP); text(setOf(p), x, y + 12); }
  }
  noStroke(); fill(235); textAlign(LEFT, TOP); textSize(constrain(width / 46, 11, 14));
  const verb = cur ? (cur.type === 'emit' ? 'record ' : cur.type === 'back' ? 'undo the last choice, back to ' : 'choose: ') : '';
  text(verb + (cur ? setOf(cur.path) : ''), 16, 12, width - 32);
  fill(200); textSize(12); text('output: ' + out.join(' '), 16, height - 84, width - 32);
  fill(110); textSize(11); text('choose, recurse, un-choose. 2^n leaves, one per subset. click to restart', 16, height - 36, width - 32);
}
function mousePressed() { reset(); }

Sample problem: Subsets (LeetCode 78)

Given an array of unique integers nums, return all possible subsets (the power set), in any order.

[1, 2, 3] → [[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []]

def subsets(nums):
    out, path = [], []

    def dfs(i):
        if i == len(nums):
            out.append(path[:])  # a leaf: record a copy
            return
        path.append(nums[i])  # choose
        dfs(i + 1)
        path.pop()  # un-choose
        dfs(i + 1)  # skip

    dfs(0)
    return out

Note the path[:]. Appending path itself would store the same list object eight times, and since it ends empty, you'd get eight empty lists. O(n · 2ⁿ) time: there are 2^n subsets and copying each costs up to n. That's optimal, because the output itself is that big.

Practise: Permutations (46), Combination Sum (39), N-Queens (51).

Pattern 9: Top K with a heap

Signals: the k-th largest or smallest, the top k frequent, the k closest points, or a median of a stream. Anything that needs the best few without fully sorting.

The idea: to keep the k largest, use a min-heap of size k. Its root is the smallest of the k largest, which is exactly the k-th largest. A new number only matters if it beats the root: if it does, evict the root and push the new one; if not, ignore it. The direction feels backwards the first time: largest needs a min-heap, because the root is the gatekeeper.

const K = 4;
let stream, si, heap, touched, t, doneAt, msg;
function setup() { createCanvas(windowWidth, 344); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 344); }
function reset() {
  stream = []; for (let j = 0; j < 12; j++) stream.push(floor(random(1, 100)));
  si = 0; heap = []; touched = new Set(); t = 0; doneAt = -1;
  msg = 'keep only the ' + K + ' largest seen so far. the root is the smallest of them: the k-th largest';
}
function up(i) { while (i > 0) { const p = (i - 1) >> 1; if (heap[p] <= heap[i]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; touched.add(p); i = p; } }
function down(i) {
  for (;;) {
    const l = 2 * i + 1, r = l + 1; let m = i;
    if (l < heap.length && heap[l] < heap[m]) m = l;
    if (r < heap.length && heap[r] < heap[m]) m = r;
    if (m === i) return;
    [heap[m], heap[i]] = [heap[i], heap[m]]; touched.add(m); i = m;
  }
}
function step() {
  if (si >= stream.length) { doneAt = t; msg = 'stream done: ' + K + '-th largest = ' + heap[0] + '. O(n log k) time, O(k) memory'; return; }
  const x = stream[si++]; touched = new Set();
  if (heap.length < K) { heap.push(x); touched.add(heap.length - 1); up(heap.length - 1); msg = 'heap not full: push ' + x; }
  else if (x > heap[0]) { msg = x + ' > root ' + heap[0] + ': evict the root, sift ' + x + ' down'; heap[0] = x; touched.add(0); down(0); }
  else msg = x + ' <= root ' + heap[0] + ': it cannot be in the top ' + K + ', ignore it';
}
function nodeXY(i) {
  const lvl = floor(Math.log2(i + 1)), first = (1 << lvl) - 1, count = 1 << lvl, w = min(width - 40, 420);
  return [(width - w) / 2 + ((i - first + 0.5) / count) * w, 70 + lvl * 64];
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 60 === 0) step();
  if (doneAt >= 0 && t - doneAt > 180) reset();
  for (let i = 1; i < heap.length; i++) { const [x1, y1] = nodeXY((i - 1) >> 1), [x2, y2] = nodeXY(i); stroke(70); strokeWeight(1.5); line(x1, y1, x2, y2); }
  textAlign(CENTER, CENTER);
  for (let i = 0; i < heap.length; i++) {
    const [x, y] = nodeXY(i); noStroke();
    fill(i === 0 ? color(42, 157, 143) : touched.has(i) ? color(255, 209, 102) : color(52, 58, 70));
    circle(x, y, 38); fill(i === 0 || touched.has(i) ? 20 : 230); textSize(13); text(heap[i], x, y);
  }
  const cw = min(40, (width - 40) / stream.length), x0 = (width - cw * stream.length) / 2, y = 250;
  for (let j = 0; j < stream.length; j++) {
    noStroke(); fill(j === si - 1 && doneAt < 0 ? color(255, 209, 102, 110) : j < si ? color(34, 38, 46) : color(52, 58, 70));
    rect(x0 + j * cw + 2, y, cw - 4, 26, 4);
    fill(j < si - 1 ? 100 : 230); textSize(min(12, cw / 2.8)); text(stream[j], x0 + j * cw + cw / 2, y + 13);
  }
  noStroke(); fill(200); textAlign(LEFT, TOP); textSize(constrain(width / 48, 10, 13));
  text(msg, 16, 12, width - 32);
  fill(110); textSize(11); text('green root = current answer. the stream runs left to right. click for a new stream', 16, height - 36, width - 32);
}
function mousePressed() { reset(); }

Sample problem: Kth Largest Element in an Array (LeetCode 215)

Given an integer array nums and an integer k, return the k-th largest element (in sorted order, not the k-th distinct one).

nums = [3, 2, 1, 5, 6, 4], k = 2 → 5

import heapq

def find_kth_largest(nums, k):
    heap = []  # min-heap of the k largest so far
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # pop the smallest, push x
    return heap[0]

Why it beats sorting: sorting is O(n log n). The heap never holds more than k items, so each push or replace costs O(log k), for O(n log k) time and O(k) space. When k is small and n is huge, or the data is a stream you can't sort at all, that difference is the whole point.

Practise: Top K Frequent Elements (347), K Closest Points to Origin (973), Find Median from Data Stream (295).

Pattern 10: Dynamic programming

Signals: the fewest, the most, or the number of ways, where a choice now leaves a smaller version of the same problem, and those smaller problems overlap (the naive recursion keeps solving the same one again).

The idea: define what one cell means, in plain words, before writing any code. Here, dp[x] is the fewest coins that make x. Then write how a cell is built from smaller ones, and fill the table in an order where those smaller cells already exist:

dp[0] = 0, \qquad dp[x] = 1 + \min_{c \,\in\, \text{coins},\ c \le x} dp[x - c]

Watch each cell try every coin, look back at an earlier cell (the arc) and keep the best. When it finishes, the green arcs below trace the coins actually used:

const SETS = [[1, 3, 4], [1, 5, 6, 9], [2, 5, 7], [1, 4, 5]];
let coins, A, dp, used, x, ci, best, bestCoin, t, doneAt, msg, path;
function setup() { createCanvas(windowWidth, 324); textFont('monospace'); reset(); }
function windowResized() { resizeCanvas(windowWidth, 324); }
function reset() {
  coins = random(SETS); A = floor(random(8, 17));
  dp = [0]; used = [null]; x = 1; ci = 0; best = Infinity; bestCoin = null; t = 0; doneAt = -1; path = [];
  msg = 'dp[0] = 0: zero coins make zero. every dp[x] is built from smaller answers';
}
function greedy(n) { let c = 0; for (const coin of [...coins].sort((a, b) => b - a)) while (n >= coin) { n -= coin; c++; } return n ? Infinity : c; }
function step() {
  if (x > A) {
    if (dp[A] !== Infinity) { let v = A; while (v > 0) { path.push(used[v]); v -= used[v]; } }
    doneAt = t;
    const g = greedy(A);
    msg = dp[A] === Infinity ? A + ' cannot be made from these coins: answer -1'
      : 'answer ' + dp[A] + ' coins: ' + A + ' = ' + path.join(' + ') + (g > dp[A] ? '   (greedy would use ' + (g === Infinity ? 'no valid' : g) + ')' : '');
    return;
  }
  if (ci < coins.length) {
    const c = coins[ci++];
    if (c <= x && dp[x - c] + 1 < best) { best = dp[x - c] + 1; bestCoin = c; }
    msg = 'dp[' + x + ']: try coin ' + c + (c > x ? ' (too big)' : ' -> dp[' + (x - c) + '] + 1 = ' + (dp[x - c] === Infinity ? 'inf' : dp[x - c] + 1));
    return;
  }
  dp.push(best); used.push(bestCoin);
  msg = 'dp[' + x + '] = ' + (best === Infinity ? 'inf' : best) + (bestCoin ? ' (last coin ' + bestCoin + ')' : '');
  x++; ci = 0; best = Infinity; bestCoin = null;
}
function draw() {
  background(22, 24, 29);
  t++;
  if (doneAt < 0 && t % 22 === 0) step();
  if (doneAt >= 0 && t - doneAt > 200) reset();
  const n = A + 1, cw = min(44, (width - 40) / n), x0 = (width - cw * n) / 2, y = 150;
  if (doneAt < 0 && x <= A && ci > 0) {
    const c = coins[ci - 1];
    if (c <= x) {
      const xa = x0 + (x - c) * cw + cw / 2, xb = x0 + x * cw + cw / 2;
      noFill(); stroke(255, 209, 102); strokeWeight(2); arc((xa + xb) / 2, y - 16, xb - xa, (xb - xa) * 0.8, PI, TWO_PI);
    }
  }
  if (doneAt >= 0 && path.length) {
    let v = A;
    for (const c of path) {
      const xa = x0 + (v - c) * cw + cw / 2, xb = x0 + v * cw + cw / 2;
      noFill(); stroke(42, 157, 143); strokeWeight(2.5); arc((xa + xb) / 2, y + 40, xb - xa, (xb - xa) * 0.8, 0, PI);
      v -= c;
    }
  }
  textAlign(CENTER, CENTER);
  for (let j = 0; j < n; j++) {
    noStroke();
    fill(j === x && doneAt < 0 ? color(255, 209, 102, 110) : j < dp.length ? color(52, 58, 70) : color(34, 38, 46));
    rect(x0 + j * cw + 2, y, cw - 4, 40, 4);
    fill(230); textSize(min(13, cw / 2.4));
    if (j < dp.length) text(dp[j] === Infinity ? 'inf' : dp[j], x0 + j * cw + cw / 2, y + 20);
    fill(110); textSize(9); text(j, x0 + j * cw + cw / 2, y - 8);
  }
  noStroke(); fill(235); textAlign(LEFT, TOP); textSize(constrain(width / 46, 11, 14));
  text('coins [' + coins.join(', ') + ']   amount ' + A, 16, 12);
  fill(200); text(msg, 16, 36, width - 32);
  fill(110); textSize(11); text('dp[x] = 1 + min over coins c of dp[x - c]. O(amount x coins). click for new coins', 16, height - 36, width - 32);
}
function mousePressed() { reset(); }

Sample problem: Coin Change (LeetCode 322)

Given coin denominations coins and an amount, return the fewest coins that make up that amount, or -1 if it can't be done. You have unlimited coins of each kind.

coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1)

def coin_change(coins, amount):
    INF = amount + 1  # more coins than could ever be needed
    dp = [0] + [INF] * amount  # dp[x] = fewest coins that make x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Why not just be greedy? With coins [1, 3, 4] and amount 6, greedy grabs the biggest coin first: 4 + 1 + 1, three coins. The real answer is 3 + 3, two coins. Greedy decides too early. DP tries every last coin and keeps the best, so it can't be fooled. The sketch prints the greedy count whenever greedy would have lost; click until coins [1, 3, 4] come up. O(amount × coins) time, O(amount) space.

Practise: Climbing Stairs (70), House Robber (198), Longest Common Subsequence (1143).

Complexity at a glance

# Pattern Classic problem Time Extra space
1 Two pointers Two Sum II (167) O(n) O(1)
2 Sliding window Longest Substring Without Repeating (3) O(n) O(alphabet)
3 Fast and slow pointers Linked List Cycle II (142) O(n) O(1)
4 Prefix sum + hash map Subarray Sum Equals K (560) O(n) O(n)
5 Binary search on the answer Koko Eating Bananas (875) O(n log m) O(1)
6 Monotonic stack Daily Temperatures (739) O(n) O(n)
7 BFS by levels Rotting Oranges (994) O(rows × cols) O(rows × cols)
8 Backtracking Subsets (78) O(n · 2ⁿ) O(n) + output
9 Heap (top K) Kth Largest Element (215) O(n log k) O(k)
10 Dynamic programming Coin Change (322) O(amount × coins) O(amount)

Notice how many rows say O(n) where the brute force is O(n²). That's the common thread. Each pattern is a reason why most of the pairs, windows or states you'd naively check can never be the answer, and a way to skip them.

Honourable mentions

Ten covers most problems, but these show up often enough to know by name:

  • Merge intervals: sort by start, then merge each interval into the last one if they overlap. Merge Intervals (56), Insert Interval (57).
  • Topological sort: Kahn's algorithm, BFS over in-degrees, for "order these tasks with dependencies". Course Schedule (207).
  • Union-find: near-O(1) "are these connected?" with path compression. Number of Connected Components (323), Redundant Connection (684).
  • Trie: a prefix tree for "starts with" and word-search problems. Implement Trie (208).
  • Two heaps: a max-heap and a min-heap balanced around the middle, for a running median. Find Median from Data Stream (295).
  • Bit manipulation: XOR tricks, masks and subsets as integers. Single Number (136).

How to practise

  1. Learn the pattern, not the problem. For each pattern, do the sample problem above, then the three practice problems without looking anything up. If they feel like the same problem by the third one, you've got it.
  2. Name the signal before you code. Read the statement and say out loud which word gave it away: "contiguous", "sorted", "k-th", "all combinations", "fewest steps".
  3. Start from the template. Each solution above is small enough to rewrite from memory in a couple of minutes. In an interview, a correct template you trust beats a clever idea you have to debug.
  4. State the complexity and the reason. "O(n), because each index enters and leaves the window once" is the sentence interviewers listen for.
  5. Play with the sketches. Click them until the behaviour stops surprising you. Being able to predict the next step is what understanding feels like.

Happy problem solving! 🧠

Cover photo: "Swiss Army Knife" Abacus by Jccsvq, CC0, via Wikimedia Commons.

Open to hard problems

Got a system worth
building right?

Distributed backends, AI agents, or performance work that needs to go fast. Let's talk.

Get in touchGitHubLinkedIn