Coding Patterns A Cheat Sheet

A coding pattern is a reusable shape that a family of problems shares: the same access pattern on data (sliding window, two ends closing in, a stack of pending candidates, DFS marking visited nodes) recurs whether the values are integers, strings, or graph nodes. Recognizing the shape lets you retrieve an already-optimal template instead of re-deriving an algorithm from scratch under interview time pressure.

Recognize the pattern

Brute force to optimal, worked on Monotonic Queue

Take the sliding-window-maximum family (e.g. Continuous Subarrays, Sum of Subarray Minimums). The brute force recomputes the extremum of every window from scratch: for each of the n-k+1 windows, scan k elements, giving O(n·k) time and O(1) extra space. The optimal approach keeps a deque of indices whose values are monotonically decreasing (for a max-window); each element enters and leaves the deque at most once, so the whole pass is O(n) time, O(k) space for the deque.

Complexity derived from first principles

Let each array element be pushed onto the deque exactly once (n pushes total). Once pushed, an element leaves the deque in exactly one of two mutually exclusive ways: it is popped from the back when a later, strictly larger element arrives and makes it useless as a future maximum, or it is popped from the front once its index falls outside the current window. It can never suffer both fates — whichever removal happens first takes it out of the structure for good. So total removals across the whole run are ≤n, not 2n (n from the back plus n from the front would double-count elements that are never actually in the deque long enough to be evicted twice). Total deque operations = n pushes + ≤n pops = O(n), not O(n·k). Amortized cost per array element is O(1) even though a single step can pop several elements, because each pop is paid for by that same element's one earlier push. Space is O(k) for the deque (at most one entry per index currently in the window).

Traced example

Array = [5, 3, 4, 1, 2], window k = 3. Deque stores indices; we keep values decreasing. This trace is chosen specifically so the front-pop branch actually fires at i=3, not just the back-pop branch.

At i=3 the back-check finds nothing to pop (1 is smaller than the back element, so it's just appended), yet index 0 has aged out of the window and must be evicted from the front — this is the mechanism the amortized-cost argument depends on, now actually exercised rather than asserted.

Mechanism sketch: the other eight patterns

Counting

Anagram check on "aab" vs "aba": one pass increments a 26-slot counter for the first string, a second pass decrements it for the second; if every slot ends at zero, they're anagrams. O(n) time, O(alphabet) space.

count[26] = 0
for c in s: count[c - 'a']++
for c in t: count[c - 'a']--
return all(x == 0 for x in count)

Simulation

Robot moves on a grid with obstacles: for each instruction, compute the candidate next cell; if it's not an obstacle, commit the move, otherwise stay put and continue. No shortcut exists because state depends on the exact path taken, so cost is O(total steps).

pos = (0,0)
for instr in instructions:
  next = apply(pos, instr)
  if next not in obstacles: pos = next

Linear Sort (Counting Sort)

Sorting heights bounded to 1–100: tally each value into a 101-slot bucket array, then rewrite the array by walking buckets in order. No comparisons are made, so the O(n log n) comparison-sort floor doesn't apply — cost is O(n + k) where k is the value range.

count[101] = 0
for h in heights: count[h]++
out = []
for v in 1..100: append v to out, count[v] times

Meet in the Middle

Subset-sum with target T over n≤40 items: split into halves A and B, enumerate all 2^(n/2) subset sums of A and sort them, then for each of the 2^(n/2) subset sums of B binary-search for T−sum(B) in the sorted A sums. Total O(2^(n/2)·n). This only works because the two halves combine by simple addition — there's no per-element state to carry across the split.

Mo's Algorithm

Given offline range queries (l, r) where the aggregate can't be decomposed into prefix sums (e.g. "how many distinct values in [l,r]"), sort queries by (l / blockSize, r), then move l and r pointers one step at a time between consecutive queries, incrementally updating a running answer as elements enter/leave the window. Total pointer movement across all queries is O((n+q)·√n) because each block's queries share a nearly-fixed l.

Serialize/Deserialize

Encode a binary tree by a pre-order DFS that writes each node's value, using a sentinel like "#" for null children, comma-separated. Decoding replays the same DFS order, consuming tokens left to right and recursively rebuilding left-then-right subtrees. Both directions are O(n).

serialize(node): if node is null: return "#"
  return node.val + "," + serialize(node.left) + "," + serialize(node.right)

Clone

Deep-copying a graph with a random/cross pointer: DFS or BFS from the start node, keeping a map from old node to its clone. Before recursing into a neighbor, check the map first — if the neighbor is already cloned, reuse that clone instead of recursing again. This map lookup is what prevents infinite recursion on cycles.

clone(node, map):
  if node in map: return map[node]
  copy = new Node(node.val); map[node] = copy
  for nbr in node.neighbors: copy.neighbors.append(clone(nbr, map))
  return copy

Articulation Point/Bridge (Tarjan)

DFS from any node, assigning each node a discovery time disc[u] and a low-link low[u] = the smallest discovery time reachable from u's subtree via at most one back edge. u is an articulation point if it's the DFS root with ≥2 tree children, or if some child v has low[v] ≥ disc[u] (v's subtree can't reach above u without going through u). A bridge is the edge (u,v) itself when low[v] > disc[u]. Single DFS pass, O(V+E).

Pitfalls

• Counting: forgetting that a hash map's O(1) is amortized and hashing itself costs O(key length) — not free for long strings.
• Monotonic Queue: popping from the back on the wrong comparison direction (use ≤ vs <) silently breaks ties and drops valid candidates.
• Meet in the Middle: forgetting to sort one half before binary-searching it, or double-counting the empty subset in both halves.
• Mo's Algorithm: only valid when queries are offline (all known upfront) and the array is static; it fails outright on online or mutating-array queries, and it's the wrong tool whenever the aggregate is decomposable enough for a Fenwick/segment tree.
• Clone / Serialize: missing the case of already-visited nodes causes infinite recursion on cyclic graphs.

When to use / when not, with trade-offs

Use pattern-matching when the problem's constraints (n size, value range, query count, whether queries are offline, whether state must be tracked per-subset) point unambiguously at one template — it turns a 45-minute derivation into a 5-minute retrieval. Two trade-offs are easy to state wrong, so state them carefully:

Mo's Algorithm vs Fenwick/segment tree. For a query type a Fenwick or segment tree CAN decompose (range sum, range min, etc.), the tree is asymptotically better at every scale: O(log n) per query beats Mo's O((n+q)√n) total whenever the batch is large, since √n grows faster than log n. Mo's real justification is not raw speed on ordinary range queries — it's that it handles aggregates a tree structure cannot maintain incrementally at all, such as count-distinct or mode-of-range, where there is no cheap merge operation to build a tree on. Reach for Mo's only when that decomposition genuinely doesn't exist, and never on a mutating array (Mo's has no efficient update path).

Meet in the Middle vs DP over bitmask. These are not competing solutions to the same problem, so comparing their complexities head-to-head is the wrong frame. Meet in the Middle (O(2^(n/2)·n)) applies when the answer for the whole set can be recovered by combining two independently-enumerated halves via a simple operation like addition-then-binary-search (subset-sum, partition into equal halves) — it is asymptotically far cheaper than DP over bitmask (O(2^n·n)) at every n, not just large n (n=20: ~2×10^3 vs ~2×10^7). DP over bitmask is chosen instead only when the problem needs per-subset state that can't be split cleanly — e.g. TSP or Hamiltonian path, where the best cost to reach node v depends on the exact set of nodes already visited, and that set can't be decided independently in two halves and merged afterward. This is also why bitmask DP's practical n cap (~20–22) is much lower than meet-in-the-middle's (~40): its cost genuinely is worse, which is exactly why it's reserved for problems meet-in-the-middle structurally cannot express.

Takeaways

• A pattern is defined by its structural tell in the constraints (range size, query count, mutability, need for per-subset state), not by surface wording.
• Monotonic structures (queue/stack) get amortized O(n) because each element is pushed once and removed at most once total, from exactly one end.
• Two techniques with different complexities aren't automatically "competing" — Mo's vs Fenwick and Meet-in-the-Middle vs bitmask DP are each pairs solving different problem shapes, not the same problem at different sizes.

Recall: In the trace on [5,3,4,1,2] with k=3, why did index 0 get removed from the deque at i=3 even though no back-pop condition was triggered that step?

Compiled from standard interview-pattern references (sliding window / monotonic deque, meet-in-the-middle, Mo's algorithm, Tarjan's articulation-point/bridge algorithm) and the original course pattern list.