18 — Patterns and how to choose

The earlier chapters are organized by data structure and by algorithm. Problems are not. A problem statement names a goal and some constraints, and the work of choosing a technique is matching features of the statement (the input size, whether the data is sorted, whether the question asks for a count, an optimum or every solution) against the techniques that exploit those features. This chapter is the map for that matching. Each entry gives the idea in a sentence or two, the signals that suggest it, its cost, a minimal tested skeleton where one helps, and a link to the chapter that covers it in depth.

Every skeleton below was run and checked against a brute-force reference on random inputs. Measurements were taken with Python 3.14 on one Mac (Apple silicon) using timeit and time.perf_counter, best of several runs; exact numbers will differ elsewhere.

Reading the input size first

The input limits in a problem statement are the most reliable signal there is, because they bound the complexity that can finish in time. To use them, the budget has to be calibrated: how many basic steps per second does the language actually execute?

Measured: Python 3.14 operations per second

Each row runs a loop of $10^7$ iterations inside a function (local variables, which are faster than globals), and reports iterations per second:

And some whole algorithms, to see what a “step” costs inside real code:

The useful conclusion: in pure Python, a loop body doing a few operations runs at roughly $10^7$ to $5 \times 10^7$ iterations per second on this machine, and anything that pushes the loop into C (sorted, sum, list comprehensions to a lesser degree, bytes and str methods) is several times faster. A budget of about $10^7$ algorithm steps per second is a safe planning figure for Python. Compiled languages are commonly budgeted at $10^8$ to $10^9$ simple operations per second; that figure is a widely used rule of thumb, not something measured here.

Input size to feasible complexity

Using about $10^7$ steps per second for Python and the conventional $10^8$ for compiled code, for a time limit around one second:

How to read it: if $n \le 20$, an exponential algorithm is probably intended; if $n = 10^5$, anything quadratic ($10^{10}$ steps) will not finish, and the target is $O(n \log n)$ or better. Limits on values matter as much as limits on length. A DP over a value dimension (knapsack capacity, coin amount) is $O(n \cdot W)$, which is fine for $W = 10^4$ and hopeless for $W = 10^9$, where the value is better handled by binary search on the answer or a different formulation. Two dimensions together, like ”$n \le 15$ and $m \le 10^4$”, usually mean exponential in one and polynomial in the other (bitmask DP over $n$, linear in $m$).

The core patterns

These are recurring solution shapes rather than algorithms. Each one exploits a specific structural property of the input, and the signal list is the way to recognize that property in a statement.

Two pointers

Idea. Two indices move through a sequence under a rule that guarantees every pair or position that could matter is examined, so an $O(n^2)$ search over pairs becomes $O(n)$. On a sorted array, the opposite-ends version discards one element per step with a proof that it cannot be part of a better answer.

def pair_with_sum(nums, target):
    """nums sorted ascending; return indices (i, j), i < j, or None."""
    i, j = 0, len(nums) - 1
    while i < j:
        s = nums[i] + nums[j]
        if s == target:
            return i, j
        if s < target:
            i += 1          # nums[i] is too small for every remaining j
        else:
            j -= 1          # nums[j] is too large for every remaining i
    return None

print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))

(2, 3)

Signals. Sorted array or a statement that allows sorting; pairs or triplets with a target sum (Two Sum II, 3Sum, 4Sum); “in place” with O(1) extra space (remove duplicates, move zeros, partition); comparing from both ends (palindromes, Container With Most Water, Trapping Rain Water); merging two sorted sequences.

Cost. $O(n)$ after an $O(n \log n)$ sort if one is needed; $O(1)$ extra space. Covered in chapter 4 (opposite ends, same direction, read/write pointers) and chapter 16 (the proof for Container With Most Water).

Sliding window

Idea. A contiguous range [left, right] whose right end advances one step at a time and whose left end advances only as far as needed to restore an invariant (“at most $k$ distinct”, “sum at most $S$”, “no repeated character”). Each index enters and leaves the window once, so the total work is $O(n)$ even though there is an inner loop.

from collections import Counter


def longest_window_at_most_k_distinct(s, k):
    count, left, best = Counter(), 0, 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while len(count) > k:              # restore the invariant by shrinking
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_window_at_most_k_distinct("eceba", 2))

3

Signals. “Contiguous subarray” or “substring”; longest or shortest range satisfying a condition; fixed window size $k$ (moving averages, max of each window); “at most $k$” of something.

Precondition. The condition must be monotone in the window: if a window is valid, every window inside it is valid (or, for minimum-length problems, every window containing it). Sums with negative numbers break this, and then the tool is prefix sums with a hash map or a monotonic deque, not a plain window. “Exactly $k$” problems are usually solved as $\text{atMost}(k) - \text{atMost}(k-1)$. Covered in chapter 4 and chapter 5; the monotonic deque for window maxima is in chapter 7.

Fast and slow pointers

Idea. Two pointers move through a linked structure at different speeds. If there is a cycle, the fast one laps the slow one inside it; if not, the fast one reaches the end when the slow one is at the middle. Floyd’s algorithm then finds the cycle’s entry: after they meet, a pointer restarted from the head and the meeting pointer, both moving one step, meet at the entry.

The structure does not have to be a linked list. Any function $f$ from a finite set to itself defines one, and iterating $f$ from a start value must eventually cycle. Find the Duplicate Number uses $i \to \text{nums}[i]$:

def find_duplicate(nums):
    """nums has n + 1 values in 1..n; Floyd's cycle detection on i -> nums[i]."""
    slow = fast = nums[0]
    while True:
        slow, fast = nums[slow], nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow

print(find_duplicate([1, 3, 4, 2, 2]))

2

Signals. Linked list with “cycle”, “loop”, “middle”, “k-th from the end” (a gap of $k$ rather than a speed difference); a sequence defined by repeatedly applying a function (Happy Number); finding a duplicate in O(1) space without modifying the input.

Cost. $O(n)$ time, $O(1)$ space, which is the reason to use it over a visited set. Covered in chapter 6.

Frequency counter

Idea. Replace repeated scanning with a table of counts built in one pass. Two variants: a fixed-size array indexed by character code ([0] * 26 for lowercase letters, [0] * 128 for ASCII) and a hash map (Counter, dict) for arbitrary keys. The array is faster and has no hashing cost, but works only for a small known alphabet; the hash map works for anything hashable.

def is_anagram(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

Signals. Anagrams, permutations of a string, “same characters”, ransom note; “first unique”, “most frequent”, “appears more than $n/k$ times”; pair or complement lookups (Two Sum on unsorted input: store each value’s index, look up target - x); counting subarrays with a property via prefix sums stored in a map (Subarray Sum Equals K).

Cost. $O(n)$ expected time; $O(\sigma)$ space for an alphabet of size $\sigma$, or $O(n)$ for a hash map. Comparing two 26-entry arrays is $O(26)$, constant. Covered in chapter 8 and chapter 5. Frequency counts combined with a sliding window give Find All Anagrams and Minimum Window Substring.

Cyclic sort

Idea. When the values are known to lie in a range of the same size as the array (typically $1..n$), each value has a “home” index. Swap each value into its home; every swap places at least one value permanently, so the total is at most $n$ swaps. Afterwards, any index not holding its own value reveals a missing or duplicated number.

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        # keep swapping nums[i] into its home index nums[i] - 1
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

print(first_missing_positive([3, 4, -1, 1]))

2

Signals. “Numbers in the range 1 to $n$” (or 0 to $n$); find the missing, duplicated, or all missing numbers; O(1) extra space and O(n) time required together, and modifying the input is allowed.

Cost. $O(n)$ time despite the nested while, $O(1)$ space. The condition nums[nums[i] - 1] != nums[i] (not nums[i] != i + 1) is what prevents an infinite loop on duplicates. If the input must not be modified, the alternatives are XOR or sum formulas for a single missing number (chapter 17) and fast and slow pointers for a single duplicate. Covered in chapter 4.

Modified binary search

Idea. Binary search applies to any predicate that is false then true (monotone) over an ordered range, not only to finding a value in a sorted array. Two common modifications: searching a rotated sorted array, where at each step one half is sorted and can be tested directly; and binary search on the answer, where the “array” is the range of possible answers and the predicate is “is this answer feasible?”.

def min_capacity(weights, days):
    """Ship Within Days: smallest capacity that ships everything in order."""
    def feasible(cap):
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used, load = used + 1, 0
            load += w
        return used <= days
    lo, hi = max(weights), sum(weights)
    while lo < hi:                       # first cap where feasible(cap) is True
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))

15

Signals. Sorted or rotated sorted input; “find the first/last position”, “insert position”; peak element, minimum in rotated array; and, most often missed, “minimize the maximum” or “maximize the minimum” (Koko Eating Bananas, Split Array Largest Sum, Magnetic Balls, Ship Within Days), where checking a candidate answer is cheap but constructing the best one is not. A huge value range ($10^9$) with a cheap feasibility check is the other giveaway.

Cost. $O(\log R)$ predicate evaluations for a range of size $R$; above, $O(n \log \sum w)$. The rotated-array search that is not shown here is in chapter 2, along with the loop-bound conventions that avoid off-by-one errors.

Top k elements

Idea. To keep the $k$ largest of a stream, hold a min-heap of size $k$: its root is the smallest of the current top $k$, so each new element is compared with the root and replaces it if larger. The opposite heap orientation from what the question asks for is the counter-intuitive part.

import heapq


def k_largest(nums, k):
    heap = []                            # min-heap of the k largest seen so far
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

print(k_largest([3, 2, 1, 5, 6, 4], 2))

[6, 5]

Signals. ”$k$ largest/smallest/most frequent/closest”; “$k$-th largest”; streaming input where the whole set cannot be kept; merging $k$ sorted lists (a heap of the $k$ current heads).

Cost and alternatives. $O(n \log k)$ time, $O(k)$ space. Sorting is $O(n \log n)$ and simpler when everything fits in memory and $k$ is close to $n$. Quickselect finds the $k$-th element in $O(n)$ average time (worst case $O(n^2)$ without a good pivot rule, $O(n)$ with median of medians). For “top $k$ frequent” with bounded counts, bucket sort by frequency is $O(n)$. heapq.nlargest implements the heap approach. Covered in chapter 9 and chapter 3 (quickselect).

Two heaps

Idea. Split the data into a lower half in a max-heap and an upper half in a min-heap, with sizes kept equal or differing by one. The median is then at one or both roots. Every insertion routes the value through one heap into the other so the halves stay ordered.

class RunningMedian:
    def __init__(self):
        self.low = []    # max-heap (negated) of the smaller half
        self.high = []   # min-heap of the larger half

    def add(self, x):
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))   # largest of low moves up
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

rm = RunningMedian()
for x in [5, 15, 1, 3]:
    rm.add(x)
    print(rm.median(), end=" ")

5 10.0 5 4.0 

Signals. Running or sliding median; any problem that needs the boundary between a “smaller” and a “larger” group as items arrive; scheduling problems that pick from two pools (IPO: a min-heap of projects by capital required and a max-heap of affordable projects by profit).

Cost. $O(\log n)$ per insertion, $O(1)$ per median query. Deletions (sliding median) need lazy deletion with a counter of removed values, or a sorted container. Python’s heapq is a min-heap only, so the max-heap stores negated values. Covered in chapter 9.

Intervals

Idea. Sort the intervals, by start for merging and by end for selection, so overlaps can only occur between neighbors in that order; then one linear sweep decides each interval.

def merge_intervals(intervals):
    out = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

print(merge_intervals([(1, 3), (2, 6), (8, 10), (15, 18)]))

[[1, 6], [8, 10], [15, 18]]

Signals. Input is a list of [start, end] pairs: meetings, bookings, ranges, balloons. Merge, insert, intersect two lists, find free time, count rooms, remove the fewest to eliminate overlap.

Choosing the sort key. Merging, inserting and counting rooms sort by start. Maximizing the number of non-overlapping intervals (and the equivalent minimum-removals and minimum-arrows problems) sorts by end; sorting by start there is a wrong greedy rule, with a three-interval counterexample in chapter 16. Decide up front whether touching intervals ([1, 2] and [2, 3]) overlap; the comparison <= versus < encodes that choice. A sweep line over sorted endpoint events (+1 at a start, −1 at an end) answers “maximum overlap” questions without sorting intervals at all.

Cost. $O(n \log n)$ for the sort, $O(n)$ for the sweep. Covered in chapter 4 and chapter 16.

In-place reversal of a linked list

Idea. Walk the list once, pointing each node’s next at the previous node. Three references (prev, head, and the saved next) are all the state needed.

def reverse_list(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

print(to_list(reverse_list(from_list([1, 2, 3, 4, 5]))))

[5, 4, 3, 2, 1]

(from_list and to_list convert between Python lists and a minimal Node(val, next) class.) The tuple assignment evaluates the right-hand side fully before assigning left to right, which is why this one line is correct; reordering its targets breaks it, which makes the three-line version with an explicit nxt = head.next the safer form to write by hand.

Signals. Reverse a list, a sublist between positions $m$ and $n$, or every group of $k$ nodes; palindrome linked list (reverse the second half, compare, optionally restore); reorder list ($L_0, L_n, L_1, L_{n-1}, \ldots$: find the middle with fast and slow pointers, reverse the second half, interleave); add two numbers stored most-significant first.

Cost. $O(n)$ time, $O(1)$ space. The recursive version is shorter but uses $O(n)$ stack and hits Python’s recursion limit on lists longer than about a thousand nodes. Covered in chapter 6.

Meet in the middle

Idea. Split $n$ independent choices into two halves, enumerate the $2^{n/2}$ outcomes of each half, sort one side, and combine the two by binary search or two pointers. Time drops from $O(2^n)$ to about $O(n \cdot 2^{n/2})$, at the cost of $O(2^{n/2})$ memory.

Signals. $n$ between roughly 25 and 45 for a subset-style problem (too large for $2^n$, an obvious hint at $2^{n/2}$); the objective splits as a sum or combination of two halves; subset sum, closest subset sum, partition into two equal-size halves with minimum difference; 4-Sum counting (pair sums of the first two arrays against pair sums of the last two).

Cost. In chapter 15, meet in the middle solved closest subset sum for $n = 24$ about 1,000 times faster than enumerating all subsets, and handled $n = 40$ in 0.63 s, where brute force would take hours. Bidirectional BFS (chapter 12) is the same idea applied to a graph search.

The patterns at a glance

The paradigms

Patterns are shapes of code. Paradigms are strategies for decomposing a problem, and they differ in how they handle subproblems: whether subproblems are independent, overlapping, or reduced to a single committed choice.

Divide and conquer. Merge sort, quicksort, binary search, closest pair of points, Karatsuba multiplication and Strassen’s matrix multiplication all split the input into parts that do not share work. Their costs follow recurrences of the form $T(n) = aT(n/b) + f(n)$, solved by the Master Theorem in chapter 1: merge sort’s $T(n) = 2T(n/2) + O(n)$ gives $O(n \log n)$, binary search’s $T(n) = T(n/2) + O(1)$ gives $O(\log n)$. The signal is that a solution for the whole can be assembled from solutions for halves, with the cross-boundary part handled in the combine step (counting inversions, maximum subarray crossing the middle).

Divide and conquer versus dynamic programming. The distinction is overlap. Fibonacci by plain recursion is divide and conquer applied to a problem whose subproblems overlap, and it takes exponential time; storing each subproblem once makes it DP and linear. Merge sort’s subproblems never repeat, so memoizing them would gain nothing.

Dynamic programming versus greedy. Both need optimal substructure. DP tries every first choice and keeps the best; greedy commits to one first choice and needs a proof that it is safe. When a greedy rule has no proof and a brute-force comparison finds a counterexample (0/1 knapsack, coin change with arbitrary coins), the problem is usually a DP.

Backtracking versus dynamic programming. Both explore choices recursively. If different choice sequences lead to the same remaining subproblem, and that subproblem can be described by a small state (an index and a remaining sum), memoization turns the backtracking into DP. If the remaining subproblem depends on the whole history (which squares a knight has visited, the full Sudoku grid), there is no small state, and backtracking with pruning is what remains, unless the history fits in a bitmask, as it does for the Traveling Salesman Problem with $n \le 20$.

What the question asks for narrows the choice further:

Signals to techniques

A lookup table from features of a problem statement to techniques worth trying first. A signal suggests a technique; it does not guarantee it.

Common failure modes

The bugs below are not exotic. They are the ones that make a correct idea produce a wrong answer or time out, and most of them only appear at boundaries or on adversarial inputs, which is why random small tests against a brute-force reference catch so many of them.

Off-by-one errors

Most off-by-one errors come from mixing interval conventions. Picking one convention per loop and stating its invariant prevents them:

Other recurring sources: window length right - left + 1 (closed) versus right - left (half-open); range(n) excluding $n$; the last index of a DP table being $n$ rather than $n - 1$ when the table has an empty-prefix row; the Jump Game II loop that must stop one index early (chapter 16); and whether intervals that touch at an endpoint overlap. Testing sizes 0, 1 and 2 catches most of these, because those sizes exercise every boundary at once.

Overflow in fixed-width languages

Python integers are arbitrary precision, so overflow never happens in Python code, and a Python solution that passes can still be wrong when ported. With 32-bit signed integers, the largest value is $2^{31} - 1 = 2{,}147{,}483{,}647$, and one more wraps to the most negative value. Simulated with ctypes:

import ctypes

print(ctypes.c_int32(2**31 - 1 + 1).value)
lo, hi = 1_500_000_000, 2_000_000_000
print(ctypes.c_int32(lo + hi).value // 2, lo + (hi - lo) // 2)

-2147483648
-397483648 1750000000

The second line is the classic binary search bug: (lo + hi) / 2 overflows when both indices are large, producing a negative midpoint, while lo + (hi - lo) / 2 cannot overflow. The bug sat in widely used library binary searches for years before it was noticed. Other common cases: products of two values up to $10^9$ (use 64-bit), sums of $10^5$ values up to $10^9$ (64-bit), modular arithmetic where a * b % m overflows before the modulo is applied (cast first, or use 128-bit intermediates), abs(INT_MIN), and hash computations that rely on wraparound in one language and not another. In Python, the corresponding hazard is cost rather than correctness: integers that grow without bound (an unreduced counting DP) become slow, which is why problems ask for answers modulo $10^9 + 7$.

Mutation while iterating

Changing a collection while iterating over it either raises an error or silently skips elements:

nums = [2, 4, 4, 5, 6]
for x in nums:
    if x % 2 == 0:
        nums.remove(x)
print(nums)

d = {1: "a", 2: "b"}
try:
    for k in d:
        d[k + 10] = "c"
except RuntimeError as e:
    print("RuntimeError:", e)

[4, 5]
RuntimeError: dictionary changed size during iteration

The list loop removed the 2, which shifted every later element left by one, so the iterator’s next index skipped the first 4. The final 6 was then removed, but the second 4 was never examined. Dictionaries and sets detect size changes and raise; lists do not. Fixes: build a new collection ([x for x in nums if x % 2]), iterate over a copy (for x in nums[:]), or iterate backwards by index when deleting in place. The backtracking equivalent is recording a mutable path without copying it (chapter 15), and the graph equivalent is modifying an adjacency list while traversing it.

Python recursion depth

CPython limits recursion depth to protect its own stack:

import sys

print(sys.getrecursionlimit())
def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)
try:
    depth(10_000)
except RecursionError as e:
    print("RecursionError:", e)

1000
RecursionError: maximum recursion depth exceeded

A recursive DFS on a path-shaped graph, a degenerate (linked-list-shaped) binary tree, a memoized top-down DP with $10^4$ states in a chain, or a recursive linked-list reversal all hit this limit long before running out of memory. Options, in order of preference: rewrite the recursion with an explicit stack (DFS, tree traversals; chapter 12 shows the iterative form); convert top-down DP to bottom-up iteration; or raise the limit with sys.setrecursionlimit, which works for moderate depths but is a workaround rather than a fix: very high limits can still exhaust the underlying C stack on some call paths and crash the interpreter instead of raising an exception. Recursion depth is also part of the space complexity: an $O(1)$-extra-space claim for a recursive algorithm is usually wrong, because the stack is $O(\text{depth})$.

Worst-case inputs for hash maps

A hash map’s $O(1)$ is an expected cost that assumes keys spread evenly over the buckets. If many keys share a hash value, every operation degenerates into a scan through the colliding keys. Python randomizes the hashes of str and bytes per process (controlled by PYTHONHASHSEED), which defeats precomputed string collision attacks. It does not randomize integer hashes: a non-negative int hashes to its value modulo the prime $2^{61} - 1$ on 64-bit builds, so every multiple of that prime hashes to 0. Building a set from such keys, compared with ordinary consecutive integers (best of five runs):

The colliding column quadruples each time $n$ doubles: the set build has become $O(n^2)$, and at 8,000 keys it is about 6,000 times slower. The same applies to any hash table whose hash function an adversary can predict; this is why hash flooding was a practical denial-of-service attack against web servers that parsed request parameters into hash maps, and why languages moved to randomized, keyed hash functions. Java’s HashMap additionally turns long collision chains into balanced trees, bounding the worst case at $O(\log n)$ per operation. Where worst-case guarantees matter, a balanced tree or sorted structure (chapter 10) gives $O(\log n)$ unconditionally. More detail on hash table internals is in chapter 8 and the Redis internals article.

Worst-case inputs for quicksort

Quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case, and the worst case is not rare if the pivot rule is predictable. A quicksort that always pivots on the first element hits the worst case on already sorted input, the most common input there is. Measured with a recursive Lomuto-partition quicksort (best of five runs):

Random input roughly doubles with $n$; sorted input quadruples. The sorted case also recurses $n$ levels deep, and needed the recursion limit raised to run at all, which combines two failure modes from this section. Fixes: choose the pivot at random or by median of three, recurse into the smaller side and loop on the larger (bounding the stack at $O(\log n)$), and use three-way partitioning when there are many equal keys, which otherwise also cause quadratic behavior. Production sorts avoid the issue differently: introsort switches to heapsort when recursion gets too deep, and Python’s own sorted is Timsort, a merge sort that is $O(n \log n)$ in the worst case and $O(n)$ on already sorted runs. Chapter 3 covers all of these.

Other recurring failures

Summary