Computer Science Algorithms

Community Classical Computer Science Algorithms Best Practices

A practitioner-oriented reference for choosing and implementing classical algorithms and data structures correctly. Organized by execution-lifecycle impact: the earliest decisions (asymptotic class, data-structure choice) cascade through everything else, so the rules near the top of the table matter most.

Scope: the patterns that show up in everyday production code review, reasonable interview / contest problems, and the at-scale toolbox (sketches, streaming, distributed primitives) — not an exhaustive cover of CLRS. Topics intentionally outside the current version: network flow, modular arithmetic, Bellman-Ford and Floyd-Warshall as standalone rules, SCC (Tarjan/Kosaraju), computational geometry, FFT, Manacher / Z-function as standalone rules. They're flagged inline in the relevant rules.

Distilled from CLRS (Introduction to Algorithms, 4th ed.), Sedgewick & Wayne (Algorithms, 4th ed., Princeton), Skiena's Algorithm Design Manual, Laaksonen's Competitive Programmer's Handbook, cp-algorithms.com, and the USACO Guide.

When to Apply

Use these rules when:

• Choosing an algorithm or data structure for a new problem ("what's the right way to do X?")
• Reviewing code for hidden O(n²) blowup — repeated in-checks on lists, pop(0) on lists, string concatenation in loops, naive substring search
• Picking a DP state or recurrence, before writing the memoization
• Modeling a problem as a graph (BFS vs Dijkstra vs topological sort)
• Refactoring brute force / naive solutions that work on toy inputs but time out at scale
• Deciding whether greedy applies, or whether DP / branch-and-bound is required

Rule Categories By Priority

Quick Reference

1. Asymptotic Complexity & Algorithm Selection (CRITICAL)

• `comp-pick-algorithm-class-from-input-bound` — Match O() to n before writing code
• `comp-amortize-instead-of-worst-casing` — Total cost, not per-op worst case
• `comp-watch-for-quadratic-blowup-from-membership-in-list` — Linear in checks in loops are O(n²)
• `comp-prefer-iterative-builders-over-string-concatenation` — Join / buffers, not +=
• `comp-derive-recurrences-via-master-theorem` — Write the recurrence before coding recursion
• `comp-treat-space-complexity-as-first-class` — Memory kills services before time does

2. Data Structure Selection (CRITICAL)

• `ds-hash-map-for-keyed-lookup` — Build the index once, then O(1) lookups
• `ds-set-for-uniqueness-and-membership` — Dedup and "have I seen this?" in O(1)
• `ds-heap-for-top-k-and-priority-queues` — O(n log k), priority-queue idioms
• `ds-deque-for-both-end-operations` — O(1) pop-front for BFS queues and sliding windows
• `ds-balanced-bst-or-sorted-container-for-range-queries` — Predecessor / successor / range scan
• `ds-union-find-for-dynamic-connectivity` — Near-O(1) grouping and merging
• `ds-prefix-sums-for-repeated-range-sums` — O(1) range sum after O(n) preprocessing
• `ds-fenwick-or-segment-tree-for-mutable-range-queries` — O(log n) updates + queries

3. Sorting & Searching (HIGH)

• `srch-use-builtin-sort-not-hand-rolled` — Timsort / introsort beat any hand-roll
• `srch-binary-search-on-sorted-data` — bisect, plus binary search on the answer
• `srch-quickselect-for-k-th-element` — O(n) average for k-th / median
• `srch-counting-and-radix-sort-for-bounded-integer-keys` — Beat O(n log n) for integer keys
• `srch-two-pointers-on-sorted-data` — O(n) on sorted arrays, sliding window

4. Dynamic Programming (HIGH)

• `dp-memoize-overlapping-subproblems` — @cache collapses exponentials
• `dp-tabulate-when-recursion-depth-or-order-matters` — Bottom-up + rolling arrays
• `dp-define-state-precisely` — Underspecified state = silent wrong answers
• `dp-knapsack-pattern` — 0/1 vs unbounded; loop direction is correctness
• `dp-bitmask-for-small-set-states` — n! → 2ⁿ · poly for n ≤ ~20
• `dp-prove-optimal-substructure-before-coding` — DP requires substructure; verify before coding

5. Graph Algorithms (HIGH)

• `graph-bfs-for-unweighted-shortest-path` — O(V+E), no heap needed
• `graph-dijkstra-for-non-negative-weights` — Lazy-deletion heap variant
• `graph-topological-sort-for-dependency-order` — Kahn's algorithm + DAG DP
• `graph-represent-as-adjacency-list-not-matrix` — Sparse graphs need lists
• `graph-detect-cycles-during-dfs` — Three-colour scheme for directed graphs
• `graph-kruskal-or-prim-for-mst` — MST with Union-Find or heap

6. Divide & Conquer / Recursion (MEDIUM-HIGH)

• `divide-merge-sort-pattern-for-counting-inversions` — Piggy-back counting onto the merge step
• `divide-watch-recursion-depth-and-stack` — Iterate, or raise the stack
• `divide-meet-in-the-middle-for-subset-problems` — 2ⁿ → 2^(n/2)
• `divide-quickselect-vs-quicksort-partitioning` — Random pivots; 3-way Dutch flag

7. Greedy Algorithms (MEDIUM)

• `greedy-prove-exchange-argument-before-using` — Greedy needs a correctness proof
• `greedy-sort-by-the-right-key-for-scheduling` — Finish time, deadline, value/weight
• `greedy-interval-merge-and-sweep-line` — Events + sort + linear sweep
• `greedy-huffman-and-priority-queue-greedies` — Heap-based "pick smallest repeatedly"

8. String & Sequence Algorithms (MEDIUM)

• `str-kmp-or-builtin-find-not-naive-search` — Linear worst-case substring search
• `str-trie-for-prefix-queries` — Autocomplete in O(|query|)
• `str-rolling-hash-for-multiple-substring-comparisons` — Two independent hashes, please
• `str-suffix-array-or-automaton-for-substring-queries` — Heavy-duty substring tooling

9. Scale & Probabilistic Algorithms (MEDIUM)

The "unusual but valuable at scale" toolbox — sketches that trade tiny accuracy loss for orders-of-magnitude memory wins, streaming primitives for inputs that don't fit in RAM, and distributed structures that survive sharding changes.

• `scale-bloom-filter-for-probabilistic-membership` — 1 bit/element vs 8 bytes, 1% false-positive rate
• `scale-hyperloglog-for-cardinality-estimation` — Count distinct over billions in ~12 KB
• `scale-count-min-sketch-for-frequency-estimation` — Heavy hitters and frequency queries in fixed memory
• `scale-reservoir-sampling-for-streams` — Uniform k-sample from a stream of unknown length
• `scale-consistent-hashing-for-distributed-sharding` — Remap k/n keys (not all keys) on node changes
• `scale-external-merge-sort-for-out-of-memory-data` — Sort 1 TB on 8 GB of RAM
• `scale-aho-corasick-for-multi-pattern-search` — Find all of m patterns in one pass over text
• `scale-minhash-lsh-for-near-duplicate-detection` — Near-duplicate pairs in O(n), not O(n²)

How to Use

Start with the category that matches the question:

• "What's the right algorithm for n = 10⁶?" → comp- (input-bound)
• "I'm looking things up in a list inside a loop" → ds-hash-map-for-keyed-lookup or comp-watch-for-quadratic-blowup-from-membership-in-list
• "My recursion is slow" → dp-memoize-overlapping-subproblems and comp-derive-recurrences-via-master-theorem
• "Shortest path / connectivity / ordering tasks" → graph-
• "Choose items to maximize value" → start with greedy-prove-exchange-argument-before-using; fall back to dp-knapsack-pattern
• "Find / match strings" → str-
• "Memory is the constraint, not time" / "Sample / count / deduplicate at scale" / "Sharding" → scale-

Code examples are in Python (most readable across audiences). The reasoning generalizes to any language — equivalent stdlib primitives are listed where they differ.

Reference Files

Related Skills

• complexity-optimizer — Static analysis that finds the patterns these rules diagnose

classical computer science algorithms

Version 0.2.0 Community May 2026

Note:

This document is mainly for agents and LLMs to follow when maintaining,

generating, or refactoring codebases. Humans may also find it useful,

but guidance here is optimized for automation and consistency by AI-assisted workflows.

---

Abstract

A practitioner-oriented reference of classical algorithms and data structures organized by execution-lifecycle impact. 51 rules across 9 categories — asymptotic complexity, data-structure selection, sorting & searching, dynamic programming, graph algorithms, divide & conquer, greedy algorithms, string/sequence algorithms, and the at-scale toolbox (Bloom filters, HyperLogLog, Count-Min Sketch, reservoir sampling, consistent hashing, external merge sort, Aho-Corasick, MinHash/LSH) — each with incorrect/correct code examples, the cascade rationale, and pointers to canonical sources (CLRS, Sedgewick & Wayne, Skiena, cp-algorithms.com, USACO Guide, Mining of Massive Datasets). Designed for AI agents to consult when choosing or reviewing algorithmic code.

---

Table of Contents

1. Asymptotic Complexity & Algorithm Selection — CRITICAL

• 1.1 Avoid Linear `in` Checks Inside Loops — CRITICAL (O(n²) to O(n) — common 100-1000x speedup)
• 1.2 Build Strings With Join Or Buffers, Not Repeated Concatenation — CRITICAL (O(n²) to O(n) when concatenating in a loop)
• 1.3 Derive Recurrences With The Master Theorem Before Coding Recursion — CRITICAL (prevents shipping accidentally-exponential recursive algorithms)
• 1.4 Pick Algorithm Class From The Input Bound, Not From Familiarity — CRITICAL (O(n²) → O(n log n) or better — orders of magnitude on n ≥ 10⁴)
• 1.5 Reason About Amortized Cost, Not Just Worst-Case Per Operation — CRITICAL (prevents discarding O(1) amortized structures (dynamic arrays, hash tables) for false O(n) fears)
• 1.6 Treat Space Complexity As First-Class, Not An Afterthought — HIGH (prevents OOM kills at production scale even when time complexity is fine)

2. Data Structure Selection — CRITICAL

• 2.1 Use A Balanced BST Or Sorted Container For Order-Sensitive Queries — HIGH (O(n) per range query to O(log n) — required when both order and lookup matter)
• 2.2 Use A Deque For Both-End Operations, Not List Pop-From-Front — HIGH (O(n) per pop-front to O(1) — 100-1000x on queue-heavy workloads)
• 2.3 Use A Fenwick Or Segment Tree For Mutable Range Queries — MEDIUM-HIGH (O(n) per update OR query to O(log n) for both)
• 2.4 Use A Hash Map For Keyed Lookup, Not Repeated Linear Scans — CRITICAL (O(n) per lookup to O(1) average — typically 100-10000x at scale)
• 2.5 Use A Heap For Top-K And Priority Queues, Not Sort-Then-Slice — HIGH (O(n log n) to O(n log k) — huge when k << n)
• 2.6 Use A Set For Uniqueness And Membership, Not A List — CRITICAL (O(n) per membership check to O(1) — dedup goes from O(n²) to O(n))
• 2.7 Use Prefix Sums For Repeated Range Sums — HIGH (O(n) per range sum to O(1) after O(n) preprocessing)
• 2.8 Use Union-Find For Dynamic Connectivity And Grouping — HIGH (O(n) per query to nearly O(1) amortized (inverse-Ackermann))

3. Sorting & Searching — HIGH

• 3.1 Binary Search Sorted Data Instead Of Linear Scan — HIGH (O(n) per query to O(log n) — 1000x at n = 10⁶)
• 3.2 Use Counting Or Radix Sort For Bounded Integer Keys — MEDIUM (O(n log n) to O(n + k) — 5-10x at large n with small key range)
• 3.3 Use Quickselect (Or `nth_element`) For The K-th Element — MEDIUM-HIGH (O(n log n) sort to O(n) average — 20x at n = 10⁶)
• 3.4 Use The Standard-Library Sort, Not A Hand-Rolled One — HIGH (prevents O(n²) bugs and ~3-10x slower implementations)
• 3.5 Use Two Pointers On Sorted Data To Replace Nested Loops — MEDIUM-HIGH (O(n²) to O(n log n) including sort, or O(n) if already sorted)

4. Dynamic Programming — HIGH

• 4.1 Define DP State Precisely Before Writing The Recurrence — HIGH (prevents whole classes of "almost-right" DP bugs and over-large state spaces)
• 4.2 Memoize Recursions With Overlapping Subproblems — HIGH (O(2ⁿ) to O(n) or O(n²) — turns exponential into polynomial)
• 4.3 Prove Optimal Substructure Before Writing The DP — MEDIUM-HIGH (prevents shipping DPs that produce subtly wrong answers)
• 4.4 Recognize The Knapsack Pattern For Subset-Sum Decisions — MEDIUM-HIGH (exponential subset search to pseudo-polynomial O(n·W))
• 4.5 Tabulate Bottom-Up When Recursion Depth Or Eviction Order Matters — HIGH (prevents stack overflow on deep DPs; enables O(1) space via rolling arrays)
• 4.6 Use Bitmask DP When The State Includes A Small Subset — MEDIUM (factorial (n!) to O(2ⁿ·n) — practical up to n ≈ 20)

5. Graph Algorithms — HIGH

• 5.1 Detect Cycles With DFS Colours, Not "Visited" Alone — MEDIUM-HIGH (prevents wrong cycle answers and infinite recursion bugs)
• 5.2 Represent Sparse Graphs As Adjacency Lists, Not Matrices — MEDIUM-HIGH (O(V²) memory and per-iteration cost to O(V+E))
• 5.3 Use BFS For Unweighted Shortest Paths, Not Dijkstra — HIGH (O((V+E) log V) Dijkstra to O(V+E) BFS — 5-50x faster)
• 5.4 Use Dijkstra With A Heap For Non-Negative Weighted Shortest Paths — HIGH (O(V·E) Bellman-Ford to O((V+E) log V) — orders of magnitude on dense graphs)
• 5.5 Use Kruskal Or Prim For Minimum Spanning Trees — MEDIUM (O(E log E) — the only practical algorithms for MST on real graphs)
• 5.6 Use Topological Sort For Dependency Ordering And DAG DP — HIGH (O(V+E) — enables linear-time DP on DAGs and reliable cycle detection)

6. Divide & Conquer and Recursion — MEDIUM-HIGH

• 6.1 Partition Carefully — Pivot Choice Decides Worst Case — MEDIUM (O(n²) to O(n log n) — random or median-of-3 pivots avoid pathological inputs)
• 6.2 Reuse The Merge-Sort Skeleton For Order-Pair Counting Problems — MEDIUM-HIGH (O(n²) to O(n log n) — inversion counting, reverse pairs)
• 6.3 Use Meet-In-The-Middle When 2ⁿ Is Too Big But 2^(n/2) Fits — MEDIUM (O(2ⁿ) to O(2^(n/2) · n) — n = 40 becomes feasible)
• 6.4 Watch Recursion Depth — Convert To Iteration Or Raise The Stack — MEDIUM (prevents RecursionError / stack overflow on deep recursion)

7. Greedy Algorithms — MEDIUM

• 7.1 Prove A Greedy Choice With An Exchange Argument Before Coding It — MEDIUM (prevents shipping greedy algorithms that are silently incorrect)
• 7.2 Sort By The Right Key — Earliest Deadline, Smallest Ratio, Largest Density — MEDIUM (turns O(n!) brute force into O(n log n) for many scheduling problems)
• 7.3 Use A Priority Queue For "Always Pick The Smallest" Greedies — LOW-MEDIUM (O(n²) repeated min-scans to O(n log n) — Huffman, scheduling, merge-k-lists)
• 7.4 Use Sweep-Line For Interval Overlap And Maximum-Concurrency Problems — MEDIUM (O(n²) pairwise checks to O(n log n) sort + linear sweep)

8. String & Sequence Algorithms — MEDIUM

• 8.1 Use A Trie For Prefix Queries Over Many Strings — MEDIUM (O(n·m) per query to O(m) — autocompleter / spellchecker workloads)
• 8.2 Use Rolling Hashes For Many Substring Comparisons — MEDIUM (O(m) per equality check to O(1) — enables O(n) algorithms for hard string problems)
• 8.3 Use Suffix Arrays Or Suffix Automata For Heavy Substring Queries — LOW-MEDIUM (O(n²) substring enumeration to O(n log n) construction + O(m) per query)
• 8.4 Use The Stdlib Or KMP For Substring Search, Not Naive Matching — MEDIUM (O(n·m) worst case to O(n+m) — orders of magnitude on adversarial input)

9. Scale & Probabilistic Algorithms — MEDIUM

• 9.1 Use A Bloom Filter For Cheap Probabilistic Membership At Scale — MEDIUM-HIGH (64x memory reduction vs hash set — 1 bit per element with ~1% false-positive rate)
• 9.2 Use Aho-Corasick For Searching Many Patterns Against The Same Text — MEDIUM-HIGH (O(P · |T|) to O(|T| + |P_total| + matches) — m patterns in one pass)
• 9.3 Use Consistent Hashing For Sharding That Survives Node Changes — MEDIUM-HIGH (~(N-1)/N key remap on node add to ~1/N — 80% to 20% reshuffling for N=5)
• 9.4 Use Count-Min Sketch For Frequency Estimation On Massive Streams — MEDIUM-HIGH (O(n) memory to O(log n) fixed — frequency estimates and heavy hitters in KBs)
• 9.5 Use External Merge Sort When The Input Doesn't Fit In Memory — MEDIUM-HIGH (OOM or thrashing to bounded O(M) memory — sort a 1 TB file on an 8 GB box)
• 9.6 Use HyperLogLog For Cardinality Estimation On Massive Streams — MEDIUM-HIGH (O(n) memory to ~12 KB fixed — count distinct over billions with ~0.81% standard error)
• 9.7 Use MinHash + LSH For Near-Duplicate Detection At Billion-Doc Scale — MEDIUM-HIGH (O(n²) pairwise Jaccard to O(n) — find similar pairs in 10⁹ documents)
• 9.8 Use Reservoir Sampling To Take A Uniform Sample From A Stream Of Unknown Length — MEDIUM-HIGH (O(n) memory to O(k) — uniform k-sample without buffering n)

---

References

1. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ 2. https://algs4.cs.princeton.edu/ 3. http://www.algorist.com/ 4. https://cses.fi/book/book.pdf 5. https://cp-algorithms.com/ 6. https://usaco.guide/ 7. http://www.mmds.org/

---

Source Files

This document was compiled from individual reference files. For detailed editing or extension:

{Title}

{1-3 sentences explaining WHY this matters. What is the cascade — what other code pays the cost? What goes wrong without this pattern? Quantify where possible. This is the highest-signal part of the rule.}

Incorrect ({short problem label}):

{Production-realistic bad code. Not a strawman — show the version someone might actually write.}
{# Comments explaining the cost / where the bug bites.}

Correct ({short solution label}):

{Good code — minimal diff from incorrect.}
{# Comments explaining the benefit.}

{Optional sections — use only if they add signal:}

Alternative ({when relevant}):

{Different valid approach with its own tradeoffs.}

When NOT to use this pattern:

• {Specific scenario}
• {Specific scenario}

Language equivalents:

• Python: ...
• C++: ...
• Java: ...

Reference: {Source Title}

Sections

This file defines all sections, their ordering, impact levels, and descriptions. The section ID (in parentheses) is the filename prefix used to group rules.

---

1. Asymptotic Complexity & Algorithm Selection (comp)

Impact: CRITICAL Description: The single most consequential decision: choosing an algorithm class whose asymptotic cost matches the input size. A wrong choice here (e.g. O(n²) where O(n log n) exists) makes every other optimization irrelevant once inputs grow.

2. Data Structure Selection (ds)

Impact: CRITICAL Description: The container determines which operations are cheap. The wrong data structure forces wrong-complexity algorithms — every read, write, lookup, or iteration pays the structural cost forever.

3. Sorting & Searching (srch)

Impact: HIGH Description: Sorting and searching are the bedrock of higher-level algorithms (greedy, two-pointer, sweep line, binary search on the answer). Reaching for the right library primitive prevents O(n²) hand-rolls and unlocks O(log n) lookups.

4. Dynamic Programming (dp)

Impact: HIGH Description: DP turns exponential recursions into polynomial computations by remembering subproblem answers. Correct state design and transition order separate problems solvable in milliseconds from problems that hang for hours.

5. Graph Algorithms (graph)

Impact: HIGH Description: Networks, dependencies, routing, scheduling, and reachability all reduce to graph problems. Picking the right traversal (BFS vs DFS) or shortest-path algorithm (Dijkstra vs Bellman-Ford vs BFS) changes complexity by orders of magnitude.

6. Divide & Conquer and Recursion (divide)

Impact: MEDIUM-HIGH Description: Recursive decomposition unlocks logarithmic-factor speedups (merge sort, FFT, binary search) but introduces stack-depth and recurrence-relation traps. The Master Theorem and tail-call patterns matter here.

7. Greedy Algorithms (greedy)

Impact: MEDIUM Description: Greedy algorithms are fast and simple when they work — but they only work when the problem has the greedy-choice and optimal-substructure properties. Misapplying greedy where DP is required produces silently wrong answers.

8. String & Sequence Algorithms (str)

Impact: MEDIUM Description: Strings have specialized algorithms (KMP, Z-function, suffix arrays, rolling hash) that beat naive O(nm) pattern matching. Choosing the right one prevents quadratic blowup on adversarial inputs.

9. Scale & Probabilistic Algorithms (scale)

Impact: MEDIUM Description: Unusual algorithms that are situational at small n but decisive at production scale: probabilistic sketches (Bloom, HyperLogLog, Count-Min) trade tiny accuracy loss for orders-of-magnitude memory wins; streaming and external algorithms (reservoir sampling, external merge sort) handle inputs that don't fit in RAM; distributed primitives (consistent hashing, MinHash/LSH) make sharding and similarity tractable at billion-item scale. Category impact is MEDIUM because most workloads never need them; individual rule wins are HIGH when applicable.

Reason About Amortized Cost, Not Just Worst-Case Per Operation

Many fundamental data structures rely on amortized analysis: each individual operation may occasionally be expensive, but the average cost across a sequence is bounded. Dynamic array append, hash-table insert, and union-find with path compression all look "bad" if you only inspect their worst case. Misreading those costs leads engineers to swap a perfectly good O(n) algorithm for a hand-rolled linked-list version that's measurably slower.

The rule: when bounding total work over many operations, use amortized cost. Use worst-case per operation only when a single slow operation would violate a latency SLO.

Incorrect (rejecting `list.append` because "resizing is O(n)"):

# Author worries that occasional resize makes appends O(n) worst case
# and switches to a linked list to "guarantee O(1) per append".
class Node:
    __slots__ = ("val", "next")
    def __init__(self, val):
        self.val, self.next = val, None

def build(values: list[int]):
    # O(1) "guaranteed" — but constant factor is huge, and traversal is now O(n) per access.
    head = tail = None
    for v in values:
        node = Node(v)
        if tail is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head

Correct (use the dynamic array — amortized O(1) append, contiguous memory):

def build(values: list[int]) -> list[int]:
    # Amortized O(1) per append: resizes double capacity, so total resize work
    # across n appends is O(n). Net: O(n) total, O(1) amortized per op.
    # Contiguous storage gives ~10x better iteration speed via cache locality.
    return list(values)

When worst-case matters more than amortized:

• Hard real-time systems (audio, robotics) where any spike is unacceptable
• Latency-sensitive request paths with strict p99 budgets — one O(n) rehash can blow p99 even if amortized is O(1)
• In those cases, prefer pre-sized structures (dict.fromkeys(...) with known capacity, list with [None] * n pre-allocation)

Reference: CLRS Chapter 17 — Amortized Analysis

Derive Recurrences With The Master Theorem Before Coding Recursion

Recursive algorithms hide their complexity inside the recurrence relation. Two recursions that look similar can have wildly different costs: T(n) = 2·T(n/2) + O(n) is O(n log n) (merge sort), T(n) = 2·T(n-1) + O(1) is O(2ⁿ) (naive subset enumeration), T(n) = T(n/2) + O(1) is O(log n) (binary search). The Master Theorem covers T(n) = a·T(n/b) + f(n) — the most common shape — and tells you which of three cases governs the answer.

Always write the recurrence on paper before coding. If you can't derive the recurrence, you don't yet understand the algorithm well enough to ship it.

Incorrect (recursive Fibonacci — recurrence T(n) = T(n-1) + T(n-2) + O(1), exponential):

def fib(n: int) -> int:
    # T(n) ≈ φⁿ — for n = 40 this does ~10⁹ calls and takes seconds.
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Correct (linear DP — recurrence T(n) = T(n-1) + O(1), O(n)):

def fib(n: int) -> int:
    # Each subproblem solved once. O(n) time, O(1) space.
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Master Theorem cheat sheet for T(n) = a·T(n/b) + Θ(n^d):

Worked examples: merge sort T(n)=2T(n/2)+Θ(n) → case 2, Θ(n log n). Binary search T(n)=T(n/2)+Θ(1) → case 2 with d=0, Θ(log n). Karatsuba T(n)=3T(n/2)+Θ(n) → case 3, Θ(n^log₂3) ≈ Θ(n^1.585).

Reference: CLRS Chapter 4 — Divide-and-Conquer

Pick Algorithm Class From The Input Bound, Not From Familiarity

The largest performance wins come from matching the algorithm's asymptotic class to the input size before writing code. A rough rule of thumb for a 1-second budget on commodity hardware: O(n²) is fine up to n ≈ 10⁴, O(n log n) up to n ≈ 10⁶, O(n) up to n ≈ 10⁸. Writing a nested-loop solution when n is 10⁶ produces 10¹² operations — no constant-factor or language optimization recovers that.

Decide the target class from the bound first, then pick a concrete algorithm in that class.

Incorrect (nested loop on a 10⁶ input — will time out):

def has_duplicate(nums: list[int]) -> bool:
    # O(n²) — for n = 10⁶ this is 10¹² comparisons
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Correct (O(n) via hash set, chosen because n is large):

def has_duplicate(nums: list[int]) -> bool:
    # O(n) average — single pass with a hash set
    seen: set[int] = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

When to stay with O(n²):

• n is provably small and bounded (e.g. ≤ 100)
• Constant factors of the O(n²) solution are dramatically lower (cache-friendly contiguous scan) AND inputs are tiny
• The O(n log n) / O(n) variant requires data structures with worse cache behavior on your actual size

Reference: Competitive Programmer's Handbook — Time complexity

Build Strings With Join Or Buffers, Not Repeated Concatenation

Strings are immutable in most languages (Python, Java, JavaScript, C#). s = s + chunk allocates a brand-new string and copies both operands every time. Done in a loop, this is O(n²) in the total output length — the kth iteration copies a string of size proportional to k, summing to ~n²/2 character copies. CPython sometimes optimizes this for plain string locals, but the optimization is fragile (breaks across references, across CPython versions, on PyPy/Jython). Don't rely on it.

Use a list-and-join, an explicit buffer, or a generator — they're O(n) total.

Incorrect (quadratic concatenation):

def render_csv(rows: list[list[str]]) -> str:
    # Each `+=` copies the entire accumulated string. For 10⁵ rows this
    # is ~10¹⁰ character copies — minutes instead of milliseconds.
    out = ""
    for row in rows:
        out += ",".join(row) + "\n"
    return out

Correct (collect then join — linear):

def render_csv(rows: list[list[str]]) -> str:
    # Each row builds a small string in O(|row|); the outer join walks the
    # list once. Total: O(total characters).
    return "\n".join(",".join(row) for row in rows) + "\n"

Language equivalents:

• Java: StringBuilder (not String +)
• C#: StringBuilder (not string +)
• JavaScript: arr.push(...); arr.join("") (V8 is somewhat forgiving, but consistency wins)
• Go: strings.Builder (+ allocates each time)

Reference: Joel on Software — Back to Basics (the Shlemiel the painter problem)

Treat Space Complexity As First-Class, Not An Afterthought

Time complexity dominates undergraduate teaching, but in production, space is what kills services: O(n) auxiliary memory at n = 10⁹ exhausts RAM long before time becomes the issue. Worse, allocating O(n) when O(1) exists creates GC pressure, cache misses, and page faults that also destroy time performance. Always state the algorithm's space complexity alongside its time complexity, and prefer streaming/iterator forms when consuming large inputs.

For DP, this matters doubly: many DP recurrences only depend on the last 1-2 rows, allowing O(n) space to collapse to O(1) without changing the algorithm.

Incorrect (materializes the whole input — O(n) memory, OOM on large files):

def count_long_lines(path: str, min_len: int) -> int:
    # readlines() loads the entire file into a list. For a 10 GB log, this OOMs
    # even though the work is just counting.
    with open(path) as f:
        lines = f.readlines()
    return sum(1 for line in lines if len(line) >= min_len)

Correct (stream — O(1) memory, same O(n) time):

def count_long_lines(path: str, min_len: int) -> int:
    # Iterating a file yields one line at a time. Constant memory regardless
    # of file size.
    with open(path) as f:
        return sum(1 for line in f if len(line) >= min_len)

DP space reduction example:

# O(n) space — keeps every row
def fib_full_table(n: int) -> int:
    f = [0] * (n + 1)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

# O(1) space — only keeps the rolling window the recurrence needs
def fib_rolling(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Reference: Sedgewick & Wayne — Algorithms 4th ed., §1.4 Analysis

Avoid Linear in Checks Inside Loops

A value in some_list check is O(n). When that check sits inside a loop over n items, the whole structure is O(n²) — and it's invisible because each line looks like a single operation. This is the most common accidental quadratic algorithm in code review, and it scales catastrophically: at n = 10⁴ it's tolerable, at n = 10⁵ it's a 10-second pause, at n = 10⁶ it never finishes.

Whenever you check membership repeatedly, the container holding the items must be a set or dict, not a list or tuple.

Incorrect (membership in a list — O(n²) total):

def common_elements(a: list[int], b: list[int]) -> list[int]:
    # `x in b` is O(|b|), called |a| times → O(|a|·|b|)
    return [x for x in a if x in b]

Correct (membership in a set — O(n) total):

def common_elements(a: list[int], b: list[int]) -> list[int]:
    # Build set once: O(|b|). Each `x in b_set` is O(1) average.
    # Total: O(|a| + |b|).
    b_set = set(b)
    return [x for x in a if x in b_set]

Watch for hidden variants:

• if item not in already_processed: where already_processed is a list
• list.index(x) inside a loop (same O(n) cost as in)
• for x in unique_so_far: ... to dedupe — use a set instead
• df['col'].isin(small_list) is fine; df['col'].apply(lambda v: v in small_list) is not (the latter loses vectorization)

Reference: Python Wiki — TimeComplexity

Use Meet-In-The-Middle When 2ⁿ Is Too Big But 2^(n/2) Fits

For NP-hard problems where bitmask DP is too expensive (n > ~20) but the search is naturally exponential, meet-in-the-middle halves the exponent: split the input into two halves of n/2 each, enumerate the 2^(n/2) subsets of each, then combine them via sort + binary search or hash table in O(2^(n/2) · n) time. This makes n = 40 routinely solvable where n = 20 was the ceiling.

Canonical use cases: subset sum on large weights (cannot use O(n·W) DP because W is huge), knapsack with n ≤ 40, finding a tuple of k elements that sum to a target.

Incorrect (full 2ⁿ subset enumeration — n = 40 means 10¹² subsets):

def has_subset_with_sum(arr: list[int], target: int) -> bool:
    # 2ⁿ subsets. For n = 40 this is 10¹² — infeasible.
    n = len(arr)
    for mask in range(1 << n):
        s = sum(arr[i] for i in range(n) if mask >> i & 1)
        if s == target:
            return True
    return False

Correct (meet in the middle — 2^(n/2) work per side, then combine):

def has_subset_with_sum(arr: list[int], target: int) -> bool:
    n = len(arr)
    half = n // 2
    left, right = arr[:half], arr[half:]

    def subset_sums(part: list[int]) -> list[int]:
        sums = [0]
        for x in part:
            sums += [s + x for s in sums]
        return sums

    left_sums = subset_sums(left)            # 2^(n/2) values
    right_sums = sorted(subset_sums(right))  # 2^(n/2) values, sorted
    # For each left sum L, search for `target - L` in right_sums via binary search.
    from bisect import bisect_left
    for L in left_sums:
        idx = bisect_left(right_sums, target - L)
        if idx < len(right_sums) and right_sums[idx] == target - L:
            return True
    return False

Memory cost: 2^(n/2) entries per side. At n = 40 that's ~10⁶ per side — fine. At n = 50, 2²⁵ ≈ 3·10⁷ per side, ~250 MB combined. Push further only if entries are small (e.g. 32-bit ints).

Variants:

• Find the closest subset sum to target → keep both halves sorted, two-pointer sweep
• Knapsack with values → store (weight, max_value) per side and prune dominated entries

Reference: USACO Guide — Meet in the Middle

Reuse The Merge-Sort Skeleton For Order-Pair Counting Problems

Many "count pairs (i, j) with some relationship" problems — counting inversions, reverse pairs, smaller-numbers-after-self, range sum below k — are O(n²) by naive enumeration but O(n log n) when piggy-backed onto a merge sort. During the merge step you already know that the left half is sorted and the right half is sorted; that lets you count cross-pairs in O(n) per merge, totalling O(n log n).

The pattern: do a standard merge sort, but during the merge, when an element from the right half is smaller than the current left, every remaining left-half element forms a counted pair. Same code, one extra accumulator.

Incorrect (count inversions in O(n²)):

def count_inversions(a: list[int]) -> int:
    # n² comparisons. For n = 10⁵ this is 10¹⁰ — many minutes.
    return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])

Correct (count inversions via merge sort — O(n log n)):

def count_inversions(a: list[int]) -> int:
    # Sort a copy; accumulate inversions during merge.
    buf = list(a)

    def sort(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        inv = sort(lo, mid) + sort(mid, hi)
        # Merge two sorted halves a[lo..mid] and a[mid..hi].
        left, right = buf[lo:mid], buf[mid:hi]
        i = j = 0
        for k in range(lo, hi):
            if i < len(left) and (j == len(right) or left[i] <= right[j]):
                buf[k] = left[i]; i += 1
            else:
                buf[k] = right[j]; j += 1
                # Every remaining `left` element is an inversion with right[j-1].
                inv += len(left) - i
        return inv

    return sort(0, len(a))

Same skeleton works for: counting "reverse pairs" (i < j with a[i] > 2·a[j]), counting "range-sum-in-[lo,hi]" using prefix sums + merge sort on prefix arrays, and external sort of huge files (merge sort is the only sort that's I/O-optimal).

Reference: Sedgewick & Wayne — Mergesort

Partition Carefully — Pivot Choice Decides Worst Case

Quicksort and quickselect both rely on partitioning around a pivot. With a deterministic "first element" or "last element" pivot, sorted-or-nearly-sorted input degrades to O(n²) — and adversaries can craft inputs that exploit any fixed pivot rule. Two robust mitigations: (1) randomize the pivot — expected O(n log n) regardless of input; (2) median-of-three (pick the median of first, middle, last) — works well in practice and beats random for nearly-sorted data.

The deeper lesson generalizes beyond partitioning: any divide-and-conquer that splits work unevenly degrades the recursion. If T(n) = T(αn) + T((1-α)n) + O(n) with α very small (e.g. 0.01), the recursion is still O(n log n) (any α < 1 keeps it logarithmic in depth) — but with α = 0 it's O(n²).

Incorrect (first-element pivot — O(n²) on sorted input):

def quicksort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return
    pivot = a[lo]                    # ← deterministic; sorted input is worst case
    i = lo + 1
    for j in range(lo + 1, hi + 1):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]; i += 1
    a[lo], a[i - 1] = a[i - 1], a[lo]
    quicksort(a, lo, i - 2)
    quicksort(a, i, hi)

Correct (random pivot — expected O(n log n)):

import random

def quicksort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return
    # Random pivot: expected O(n log n) regardless of input order.
    p = random.randint(lo, hi)
    a[lo], a[p] = a[p], a[lo]
    pivot = a[lo]
    i = lo + 1
    for j in range(lo + 1, hi + 1):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]; i += 1
    a[lo], a[i - 1] = a[i - 1], a[lo]
    quicksort(a, lo, i - 2)
    quicksort(a, i, hi)

Three-way partitioning (Dutch national flag) for arrays with many duplicate keys:

import random

def quicksort_3way(a, lo, hi):
    # Partitions into < pivot, == pivot, > pivot in one pass.
    # On heavily-duplicated data this beats 2-way partitioning by an order of magnitude.
    if lo >= hi: return
    pivot = a[lo + random.randint(0, hi - lo)]
    lt, i, gt = lo, lo, hi
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
        elif a[i] > pivot:
            a[gt], a[i] = a[i], a[gt]; gt -= 1
        else:
            i += 1
    quicksort_3way(a, lo, lt - 1)
    quicksort_3way(a, gt + 1, hi)

Real-world stdlibs use hybrids: Introsort (C++) starts with quicksort, watches recursion depth, and falls back to heapsort if it exceeds 2·log₂(n) — guaranteed O(n log n) worst case.

Reference: Sedgewick & Wayne — Quicksort

Watch Recursion Depth — Convert To Iteration Or Raise The Stack

Python's default recursion limit is 1000; raising it via sys.setrecursionlimit doesn't raise the C stack, so the process can still segfault around 10⁴-10⁵ frames depending on platform. Other languages have similar limits (JVM default ~10⁴, Node ~10⁴). Recursive algorithms on long chains (linked lists, paths, deep trees) will crash silently in production. The fixes, in order of preference: (1) convert to iteration if the recursion is tail-recursive or has a single recursive call, (2) use an explicit stack for tree-shaped recursion, (3) raise the recursion limit only as a last resort.

The diagnostic: if the input size n is ≥ 10⁴ and the recursion depth scales linearly with n, you'll hit the limit on average inputs.

Incorrect (recursive sum on a long linked list — crashes on n ≥ 1000):

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def sum_list_recursive(head):
    # RecursionError when the list has > ~1000 nodes.
    if head is None: return 0
    return head.val + sum_list_recursive(head.next)

Correct (iterative — no stack at all):

def sum_list(head: "Node | None") -> int:
    total = 0
    while head is not None:
        total += head.val
        head = head.next
    return total

Tree DFS converted to explicit stack (when you must recurse but inputs are deep):

def dfs_iterative(root):
    # Each node is pushed once. No Python frames on the C stack.
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None: continue
        # ... process node ...
        stack.append(node.right)
        stack.append(node.left)

Raising the limit (last resort):

import sys, threading

def run_deep():
    sys.setrecursionlimit(10**6)
    # main work...

# Run on a thread with a larger C stack so the recursion limit is actually usable.
threading.stack_size(64 * 1024 * 1024)  # 64 MB
t = threading.Thread(target=run_deep)
t.start(); t.join()

Mutual recursion is especially dangerous: two functions calling each other halve the effective depth.

Reference: Python docs — sys.setrecursionlimit

Use Bitmask DP When The State Includes A Small Subset

When the natural state is "which subset of these items have I visited / used / assigned" and n ≤ ~20, encode the subset as bits of an integer. The state space becomes 2ⁿ rather than n! — for n = 16 that's 65k states vs 20 trillion permutations. The canonical example is the Travelling Salesman Problem: O(2ⁿ·n²) DP beats the O(n!) brute force decisively at n = 15.

The encoding: mask = 0b1011 means "items 0, 1, and 3 are in the set." Bit ops: mask | (1 << i) adds i; mask & ~(1 << i) removes i; mask & (1 << i) tests i.

Incorrect (permutation enumeration for TSP — O(n!)):

from itertools import permutations

def tsp_brute(dist: list[list[int]]) -> int:
    n = len(dist)
    # (n-1)! permutations starting from 0. n = 12 → ~5x10⁸ ops, n = 15 → infeasible.
    best = float("inf")
    for perm in permutations(range(1, n)):
        cost = dist[0][perm[0]]
        for a, b in zip(perm, perm[1:]):
            cost += dist[a][b]
        cost += dist[perm[-1]][0]
        best = min(best, cost)
    return best

Correct (Held-Karp bitmask DP — O(2ⁿ·n²)):

def tsp_dp(dist: list[list[int]]) -> int:
    # dp[mask][i] = min cost to start at 0, visit exactly the set `mask`, end at i.
    n = len(dist)
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # mask = {0}, ended at 0
    for mask in range(1, 1 << n):
        if not (mask & 1):
            continue  # we always start at 0
        for i in range(n):
            if not (mask & (1 << i)) or dp[mask][i] == INF:
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue
                nmask = mask | (1 << j)
                cand = dp[mask][i] + dist[i][j]
                if cand < dp[nmask][j]:
                    dp[nmask][j] = cand
    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(1, n))

Iterate subsets of a mask (for partitioning problems):

def iter_submasks(mask: int):
    sub = mask
    while sub > 0:
        yield sub
        sub = (sub - 1) & mask
    yield 0

Watch the memory: 2ⁿ × n states with 8-byte ints is 8·n·2ⁿ bytes — n = 22 needs ~700 MB. Stop at n = 20 unless you compress.

Reference: cp-algorithms — Submask enumeration

Define DP State Precisely Before Writing The Recurrence

A DP solution is correct only if the state captures everything the recurrence needs to make a decision without looking at the past. The most common DP bug is an underspecified state — the answer depends on something not in the state, so the cache returns the wrong value for a "matching" key. The second most common bug is an over-specified state — extra dimensions that don't affect the recurrence inflate the cache and slow the algorithm.

Always write the state definition as one English sentence before coding: "f(i, j) is the length of the longest common subsequence of a[0..i] and b[0..j]." If you can't say that sentence cleanly, the recurrence isn't ready.

Incorrect (underspecified state — answer depends on capacity used, but state ignores it):

def can_partition(arr: list[int]) -> bool:
    # "f(i) = can we partition arr[0..i] into two equal-sum halves?"
    # This is wrong — the answer depends on what sum the current half has so far,
    # which isn't in the state. Memoization will return cached wrong answers.
    from functools import cache
    target = sum(arr) // 2

    @cache
    def f(i: int) -> bool:
        if i == 0:
            return arr[0] == target  # ← only checks one specific running sum
        return f(i - 1) or ...  # whatever you write here, the state is broken
    return f(len(arr) - 1)

Correct (state includes the running sum the decision depends on):

def can_partition(arr: list[int]) -> bool:
    # State: f(i, s) = can a subset of arr[0..i] sum to exactly s?
    # Decision at i: take arr[i] (→ f(i-1, s - arr[i])) or skip (→ f(i-1, s)).
    total = sum(arr)
    if total % 2:
        return False
    target = total // 2
    from functools import cache

    @cache
    def f(i: int, s: int) -> bool:
        if s == 0:
            return True
        if i < 0 or s < 0:
            return False
        return f(i - 1, s) or f(i - 1, s - arr[i])

    return f(len(arr) - 1, target)

Heuristic for finding the right state:

Run the brute-force recursion mentally. At each call, ask: "what are all the things that determine the answer of this call?" Every one of those goes into the state. Anything that's a function of those (sum, count, set) gets included only if it can't be re-derived.

Watch for the "set" trap: if the state seems to require "which subset have I chosen," you typically need bitmask DP (state is an integer 0..2ⁿ-1) — feasible only for n ≤ ~20.

Reference: USACO Guide — DP introduction

Recognize The Knapsack Pattern For Subset-Sum Decisions

Many problems reduce to "pick a subset that maximizes value subject to a capacity constraint": 0/1 knapsack, subset-sum, partition into equal halves, coin change (count), bounded ways-to-make-change. They all share the recurrence dp[i][w] = max/min/count of (skip item i, take item i). Recognizing this pattern collapses a 2ⁿ subset enumeration into O(n·W) — pseudo-polynomial because W can itself be exponential in input bits, but practical when W is bounded.

The two flavours:

• 0/1 knapsack: each item once. Inner loop runs downwards in the rolling array to prevent using the same item twice.
• Unbounded knapsack (coin change): items reusable. Inner loop runs upwards.

Incorrect (exponential subset enumeration — O(2ⁿ)):

from itertools import combinations

def max_value(weights, values, capacity):
    best = 0
    for r in range(len(weights) + 1):
        for subset in combinations(range(len(weights)), r):
            w = sum(weights[i] for i in subset)
            if w <= capacity:
                best = max(best, sum(values[i] for i in subset))
    return best

Correct (0/1 knapsack DP — O(n·W) with O(W) rolling array):

def max_value(weights: list[int], values: list[int], capacity: int) -> int:
    # dp[w] = max value achievable with capacity w considering items seen so far.
    # Inner loop descends so each item is used at most once.
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]

Unbounded knapsack (coin change, count of ways):

def count_change(coins: list[int], amount: int) -> int:
    # Inner loop ascends → coins reusable. Outer loop is over coins
    # (not amounts) so each combination is counted once.
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for w in range(c, amount + 1):
            dp[w] += dp[w - c]
    return dp[amount]

Loop order is correctness, not optimization:

• 0/1 descending capacity, items outer: each item considered once
• Unbounded ascending capacity, items outer (for count of combinations) OR amounts outer (for count of permutations) — these give different answers

Reference: cp-algorithms — Knapsack problem

Memoize Recursions With Overlapping Subproblems

The diagnostic for DP is: a recursion explores the same subproblem many times. Naive Fibonacci visits fib(k) ~φ^(n-k) times, blowing up exponentially. Caching each subproblem's answer the first time it's computed collapses that to one visit per distinct subproblem — turning O(2ⁿ) into O(n) or O(n²) depending on how many distinct subproblems exist.

In Python, functools.cache (or lru_cache(maxsize=None)) is the cheapest possible memoization. Write the recurrence naturally, then add one decorator. Don't pre-optimize to a table; let the cache prove the recurrence first.

Incorrect (exponential recursion — `coinChange` revisits every (n) thousands of times):

def min_coins(coins, amount):
    # Each call branches |coins| ways; same `n` reached through many paths.
    # O(|coins|^amount) — TLE for amount = 30.
    if amount == 0: return 0
    if amount < 0:  return float("inf")
    return min(min_coins(coins, amount - c) for c in coins) + 1

Correct (memoize — O(amount · |coins|)):

from functools import cache

def min_coins(coins, amount):
    @cache  # one cache key per distinct `n` value → at most `amount + 1` calls.
    def f(n: int) -> int:
        if n == 0: return 0
        if n < 0:  return float("inf")
        return min(f(n - c) for c in coins) + 1

    ans = f(amount)
    return -1 if ans == float("inf") else ans

Cache key hygiene:

• Arguments must be hashable. Tuple up lists, freeze dicts/sets.
• Avoid passing in mutable globals captured implicitly — if the recursion result depends on a global that changes, the cache returns stale answers.
• @cache on instance methods caches by (self, *args), which prevents garbage collection of self. For long-running objects, use cachetools.cached(LRUCache(...)) keyed on args only.

When to switch to bottom-up (tabulation):

• Recursion depth would overflow the stack (CPython default is 1000)
• You want O(1) space via a rolling window
• The order of subproblem dependence is obvious from the recurrence

Reference: CLRS Chapter 14 — Dynamic Programming

Prove Optimal Substructure Before Writing The DP

DP requires optimal substructure: the optimal answer to a problem must be expressible in terms of optimal answers to subproblems. If this property doesn't hold, your recurrence will be wrong on some inputs — and the bug is invisible until adversarial cases hit production. The classic failure mode: greedy-shaped problems where the locally-optimal choice rules out the globally-optimal one further down.

Before coding, write down: (1) the subproblem definition, (2) why the optimal solution of the full problem must use the optimal solution of some subproblem, (3) which subproblem to combine. If step (2) is hand-wavy, the DP is unsound.

*Incorrect (DP that lacks optimal substructure — longest simple path on a general graph):*

def longest_simple_path(graph, start, end):
    # Sounds like a DP: longest path from u = 1 + max(longest path from each neighbor).
    # WRONG — the neighbor's "longest path" might reuse nodes that the caller has
    # already visited, so combining optima doesn't yield a simple path.
    # (Longest-simple-path is NP-hard for a reason.)
    from functools import cache
    @cache
    def f(u):
        if u == end: return 0
        return 1 + max((f(v) for v in graph[u]), default=-float("inf"))
    return f(start)

Correct (DP only when optimal substructure holds — longest path in a DAG):

def longest_path_dag(graph, start, end):
    # In a DAG, "longest path from u to end" depends only on `u` (no node revisit
    # is possible). Optimal substructure holds — DP is sound.
    from functools import cache
    @cache
    def f(u):
        if u == end: return 0
        return 1 + max((f(v) for v in graph[u]), default=-float("inf"))
    return f(start)

Common substructure-failure smells:

• The subproblem depends on a path / set of nodes already used elsewhere (e.g. longest simple path, Hamiltonian)
• The decision at one stage forecloses choices at distant stages in unpredictable ways
• The problem is known NP-hard (TSP, set cover, bin packing) — DP only works with subset-of-the-state in the state itself (bitmask DP), or as an approximation

When DP doesn't apply, look for: branch-and-bound, ILP, approximation algorithms, or accept exponential blowup on small inputs.

Reference: CLRS Chapter 14, §14.3 — Elements of Dynamic Programming

Tabulate Bottom-Up When Recursion Depth Or Eviction Order Matters

Memoized recursion (top-down) is easiest to write, but bottom-up tabulation has two advantages that often matter: (1) no recursion stack — fills an iterative loop instead, so DPs with depth > 10⁴ don't blow CPython's stack; (2) you control the order, which lets you collapse the table to a rolling 1- or 2-row window for O(1) extra space. For DPs on long strings, large arrays, or grids ≥ 10⁴ × 10⁴, this is the difference between "works" and "OOM kill / stack overflow."

The conversion is mechanical: identify which dimensions appear in the recurrence (the "state"), iterate them in dependency order, and write the same transition.

Incorrect (memoized recursion that overflows the stack on `n = 10⁵`):

from functools import cache

def lis_length(arr: list[int]) -> int:
    # Recurses up to n times. n = 10⁵ → RecursionError in CPython.
    @cache
    def f(i: int) -> int:
        best = 1
        for j in range(i):
            if arr[j] < arr[i]:
                best = max(best, f(j) + 1)
        return best
    return max((f(i) for i in range(len(arr))), default=0)

Correct (bottom-up tabulation — no recursion):

def lis_length(arr: list[int]) -> int:
    # dp[i] = LIS length ending at i. O(n²) time, O(n) space, no recursion.
    n = len(arr)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)

Rolling-array compression (when the recurrence only references the last 1-2 rows):

def edit_distance(a: str, b: str) -> int:
    # Classic DP uses O(|a|·|b|) memory. Rolling 2 rows → O(min(|a|,|b|)) memory.
    if len(a) < len(b):
        a, b = b, a
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, start=1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, start=1):
            cur[j] = prev[j - 1] if ca == cb else 1 + min(prev[j - 1], prev[j], cur[j - 1])
        prev = cur
    return prev[len(b)]

When top-down is still better:

• Many states are unreachable — top-down skips them, tabulation fills the whole grid anyway
• The recurrence is more naturally recursive (e.g. game theory minimax) and the depth fits the stack

Reference: USACO Guide — Introduction to DP

Use A Balanced BST Or Sorted Container For Order-Sensitive Queries

A hash map is faster than a balanced BST for point lookups — but it loses to a BST whenever you need any ordered operation: predecessor, successor, range scan, k-th smallest, or "give me the smallest key larger than x." For those, a balanced BST (std::map, TreeMap, SortedContainers.SortedList) gives O(log n) per operation while a hash map needs O(n) to find ordered neighbours.

The decision rule: use a hash map for "is x here?" and "what value does x map to?" Use an ordered structure when the question involves "next/previous/range/rank."

Incorrect (linear scan for predecessor — O(n) per query):

def closest_below(values: list[int], target: int) -> int | None:
    # Walk the list to find the largest value < target. O(n) per query.
    best = None
    for v in values:
        if v < target and (best is None or v > best):
            best = v
    return best

Correct (sorted container — O(log n) per query):

from sortedcontainers import SortedList

class ClosestBelowIndex:
    def __init__(self, values: list[int]):
        # O(n log n) build, O(log n) per query and per insert.
        self.s = SortedList(values)

    def query(self, target: int) -> int | None:
        i = self.s.bisect_left(target)  # O(log n)
        return self.s[i - 1] if i > 0 else None

When a hash map is enough:

If the only ordered query is "global min/max" and inserts never delete the current extreme, a hash map plus a running min/max variable is simpler and faster.

Language equivalents:

• Python: sortedcontainers.SortedList / SortedDict (third-party; or use bisect + list for static data)
• C++: std::map, std::set (red-black trees), std::multiset
• Java: TreeMap, TreeSet
• Go: stdlib lacks one — use a third-party B-tree or skip list

Reference: CLRS Chapter 13 — Red-Black Trees

Use A Deque For Both-End Operations, Not List Pop-From-Front

list.pop(0) in Python (and array-shift equivalents in other languages) is O(n) because every remaining element shifts down one slot. When this is the queue operation in a BFS or sliding-window algorithm, you've turned an O(n) algorithm into O(n²). A double-ended queue (collections.deque, std::deque, ArrayDeque) gives O(1) at both ends.

Reach for a deque whenever you append on one end and remove from the other (FIFO queue) or when sliding-window algorithms need cheap pops from the head.

Incorrect (BFS using `list.pop(0)` — O(V²) instead of O(V+E)):

def bfs(start, adj):
    # Each `queue.pop(0)` is O(|queue|). With V vertices, that's O(V²) total.
    queue = [start]
    visited = {start}
    while queue:
        node = queue.pop(0)  # ← linear in queue size
        for n in adj[node]:
            if n not in visited:
                visited.add(n)
                queue.append(n)
    return visited

Correct (deque — O(V+E) BFS):

from collections import deque

def bfs(start, adj):
    # deque.popleft() is O(1). BFS is now O(V+E) as it should be.
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        for n in adj[node]:
            if n not in visited:
                visited.add(n)
                queue.append(n)
    return visited

Sliding window minimum / maximum:

A monotonic deque is the canonical O(n) algorithm for "find the min/max in every window of size k." Each index enters and leaves the deque at most once.

Language equivalents:

• Python: collections.deque
• C++: std::deque (or std::queue adapter)
• Java: ArrayDeque (prefer over LinkedList)
• Go: container/list or a circular buffer

Reference: Python docs — collections.deque

Use A Fenwick Or Segment Tree For Mutable Range Queries

When an array supports both updates and range queries (sum, min, max, gcd) freely interleaved, neither a plain array (O(n) per query) nor a prefix-sum array (O(n) per update) is acceptable. A Fenwick tree (BIT) gives O(log n) for point-update + prefix-sum and is ~10 lines of code. A segment tree handles arbitrary associative operations and lazy propagation for range updates.

Pick Fenwick when the operation is sum and updates are point-wise — it's smaller and faster by a constant factor. Pick a segment tree for min/max/gcd or for range updates with lazy propagation.

Incorrect (prefix sum rebuilt on every update — O(n) per update):

def process(arr, ops):
    out = []
    for op in ops:
        if op[0] == "update":
            arr[op[1]] = op[2]
        else:  # query l..r
            out.append(sum(arr[op[1]:op[2] + 1]))  # O(n) per query
    return out

Correct (Fenwick tree — O(log n) for both):

class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.t = [0] * (n + 1)

    def update(self, i: int, delta: int) -> None:
        # Point-add `delta` at position i. O(log n).
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def prefix(self, i: int) -> int:
        # Sum of indices 0..i-1. O(log n).
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s

    def range_sum(self, l: int, r: int) -> int:
        # Sum of indices l..r inclusive.
        return self.prefix(r + 1) - self.prefix(l)

When to skip and use sqrt decomposition:

For exotic operations that don't compose nicely (e.g. "k-th element in range"), an O(√n) bucket structure is easier to write than a balanced BST and only ~30x slower than a segment tree at n = 10⁵.

Reference: cp-algorithms — Fenwick tree

Use A Hash Map For Keyed Lookup, Not Repeated Linear Scans

A hash map (dict in Python, unordered_map in C++, HashMap in Java) gives O(1) average-case lookup, insert, and delete. Any code that repeatedly looks something up "by id" or "by name" by scanning a list is silently O(n·k) where it should be O(n+k). This is the most consequential data-structure switch in everyday code — the speedup is unbounded as the dataset grows.

Build the index once before the lookup loop; the build cost is O(n), and it's reused across every query.

Incorrect (linear scan inside a loop — O(n·m)):

def attach_user_emails(orders, users):
    # For each order, scan all users to find the matching one.
    # n orders × m users = O(n·m).
    for order in orders:
        for u in users:
            if u["id"] == order["user_id"]:
                order["email"] = u["email"]
                break
    return orders

Correct (build index once — O(n + m)):

def attach_user_emails(orders, users):
    # Build a {user_id: email} index in O(m), then O(1) per order lookup.
    email_by_id = {u["id"]: u["email"] for u in users}
    for order in orders:
        order["email"] = email_by_id.get(order["user_id"])
    return orders

When NOT to use a hash map:

• You need ordered iteration by key → use a balanced BST (std::map, TreeMap, SortedDict)
• You need range queries (keys in [lo, hi]) → BST or sorted array + binary search
• Keys are small integers in a known range → an array indexed by the integer is faster and cache-friendly
• Memory is critical and the dataset is small (< ~30 items) — a linear scan over contiguous memory may beat a hash table on cache effects

Reference: CLRS Chapter 11 — Hash Tables

Use A Heap For Top-K And Priority Queues, Not Sort-Then-Slice

A binary heap supports push and pop-min in O(log n). When you only need the top-k items out of n, a size-k heap solves it in O(n log k) — strictly better than the O(n log n) full sort for any k < n. The trick: keep a min-heap of size k; each new element either replaces the smallest in the heap or is discarded. At the end, the heap holds the top-k.

Heaps also implement priority queues for graph algorithms (Dijkstra, Prim), event-driven simulation, and scheduling. The "is this thing the smallest/largest right now?" question is exactly what a heap answers.

Incorrect (full sort to get top 10 from 10⁷ items — O(n log n)):

def top_k(scores: list[int], k: int) -> list[int]:
    # Sort all 10⁷ elements just to take the largest 10 — wastes O(n log n)
    # when we only need O(n log k) work.
    return sorted(scores, reverse=True)[:k]

Correct (size-k min-heap — O(n log k)):

import heapq

def top_k(scores: list[int], k: int) -> list[int]:
    # heapq.nlargest uses a size-k heap internally. O(n log k) time, O(k) space.
    return heapq.nlargest(k, scores)

Explicit heap example (priority queue for scheduling):

import heapq

def process_jobs_by_priority(jobs):
    # Min-heap; jobs with smaller priority numbers come out first.
    pq: list[tuple[int, str]] = []
    for j in jobs:
        heapq.heappush(pq, (j.priority, j.id))
    while pq:
        priority, job_id = heapq.heappop(pq)
        run(job_id)

Use `heapq` (Python) idioms:

• Min-heap by default — negate values to get a max-heap, or use heapq.nlargest.
• For ties on the primary key, push (priority, counter, item) to avoid comparing arbitrary objects.

Reference: CLRS Chapter 6 — Heapsort

Use Prefix Sums For Repeated Range Sums

If you sum a slice of an array more than once, build a prefix-sum array first. After O(n) preprocessing, every "sum from index l to r" query becomes a single subtraction: prefix[r+1] - prefix[l]. For q queries this is O(n + q) instead of O(n·q).

This generalizes to: 2D prefix sums (sub-rectangle queries), prefix XOR (range XOR), prefix counts (number of occurrences up to i), and difference arrays (range updates as a dual of range queries).

Incorrect (recomputing the sum for every query — O(n·q)):

def range_sums(arr: list[int], queries: list[tuple[int, int]]) -> list[int]:
    # Each query scans O(n) elements. q queries → O(n·q).
    return [sum(arr[l:r+1]) for l, r in queries]

Correct (prefix sums — O(n + q)):

from itertools import accumulate

def range_sums(arr: list[int], queries: list[tuple[int, int]]) -> list[int]:
    # prefix[i] = sum of arr[0..i-1]. sum(arr[l..r]) = prefix[r+1] - prefix[l].
    prefix = [0, *accumulate(arr)]  # O(n)
    return [prefix[r + 1] - prefix[l] for l, r in queries]  # O(1) per query

*Difference-array variant (for many range updates followed by point reads):*

def apply_range_increments(n: int, updates):
    # Each update +x on [l, r] becomes diff[l] += x, diff[r+1] -= x. O(1) per update.
    diff = [0] * (n + 1)
    for l, r, x in updates:
        diff[l] += x
        diff[r + 1] -= x
    # Finalize with one prefix-sum pass.
    out = []
    running = 0
    for i in range(n):
        running += diff[i]
        out.append(running)
    return out

When a Fenwick tree or segment tree beats prefix sums:

If the array also changes between queries, prefix sums must be rebuilt O(n) per update. A Fenwick tree gives O(log n) for both update and prefix sum — better whenever updates are frequent.

Reference: USACO Guide — Introduction to Prefix Sums

Use A Set For Uniqueness And Membership, Not A List

A set tracks "have I seen this value?" in O(1) average time. Using a list for the same purpose makes every check O(n) and every dedup pass O(n²). The two operations look identical in code (if x in container) but have wildly different costs — the container type is the only difference, and it matters for every single iteration.

Reach for a set whenever the question is "is this value present?" or "give me the distinct values." Reach for a dict if you also need a payload per key.

Incorrect (dedup via list — O(n²)):

def unique_preserve_order(items: list[int]) -> list[int]:
    # `x in seen` is O(|seen|), called n times → O(n²)
    seen: list[int] = []
    out: list[int] = []
    for x in items:
        if x not in seen:
            seen.append(x)
            out.append(x)
    return out

Correct (dedup via set — O(n)):

def unique_preserve_order(items: list[int]) -> list[int]:
    # `x in seen` is O(1) average. Set tracks membership; list preserves order.
    seen: set[int] = set()
    out: list[int] = []
    for x in items:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out

One-liner when order doesn't matter:

def unique(items: list[int]) -> list[int]:
    return list(set(items))  # O(n), no order guarantee

Watch out:

• Set elements must be hashable. For lists of dicts/lists, use frozenset/tuple keys or a dict[hashable_id, item].
• Python's set iteration order is insertion order in CPython 3.7+ for dict, but not for set — don't rely on it.

Reference: Python docs — set

Use Union-Find For Dynamic Connectivity And Grouping

Whenever the problem asks "are these two things in the same group?" or "merge these two groups," the canonical answer is a disjoint-set union (DSU / Union-Find) with path compression and union-by-rank. Operations cost O(α(n)) amortized — inverse Ackermann, effectively constant for any input that fits in this universe. The naive alternative is a BFS/DFS over the current graph per query, which is O(V+E) each time — fine for one query, catastrophic for many.

Use DSU for: Kruskal's MST, connectivity queries on a growing graph, equivalence-class problems, Hoshen-Kopelman percolation, image segmentation.

Incorrect (BFS per query, quadratic over q queries):

def connected_queries(n, edges, queries):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v); adj[v].append(u)
    out = []
    for u, v in queries:
        # BFS from u to see if it reaches v — O(V+E) per query.
        seen = {u}; stack = [u]; found = False
        while stack:
            x = stack.pop()
            if x == v:
                found = True; break
            for y in adj[x]:
                if y not in seen:
                    seen.add(y); stack.append(y)
        out.append(found)
    return out

Correct (DSU with path compression and union-by-rank):

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        # Path compression: every node on the path points directly at the root.
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        # Union by rank keeps trees shallow.
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def connected_queries(n, edges, queries):
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    return [dsu.find(u) == dsu.find(v) for u, v in queries]

Both optimizations are required: path compression alone gives O(log n) amortized; union-by-rank alone gives O(log n) worst case per op; together they give O(α(n)).

Reference: CLRS Chapter 21 — Data Structures for Disjoint Sets

Use BFS For Unweighted Shortest Paths, Not Dijkstra

For graphs where every edge has the same weight (typically 1 — grids, social networks, unweighted state graphs), BFS finds shortest paths in O(V+E) with a plain FIFO queue. Dijkstra solves the more general weighted case in O((V+E) log V), which is strictly slower because of the heap operations. Reaching for Dijkstra when BFS suffices is a 5-50x slowdown depending on input size.

The diagnostic: are all edges weighted 1 (or any single constant)? Use BFS. Are weights 0 or 1 only? Use 0-1 BFS with a deque (push 0-weight to front, 1-weight to back) — still O(V+E).

Incorrect (Dijkstra on unweighted grid — wastes the heap):

import heapq

def shortest_path_grid(grid, start, end):
    # All edges have weight 1. Heap log-factor is pure overhead here.
    R, C = len(grid), len(grid[0])
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, (r, c) = heapq.heappop(pq)
        if (r, c) == end: return d
        for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
                nd = d + 1
                if nd < dist.get((nr, nc), float("inf")):
                    dist[(nr, nc)] = nd
                    heapq.heappush(pq, (nd, (nr, nc)))
    return -1

Correct (BFS — O(V+E) with a deque, no heap):

from collections import deque

def shortest_path_grid(grid, start, end):
    # Pure BFS: first time we dequeue a cell, its distance is optimal.
    R, C = len(grid), len(grid[0])
    if start == end: return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        (r, c), d = queue.popleft()
        for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#" \
               and (nr, nc) not in visited:
                if (nr, nc) == end:
                    return d + 1
                visited.add((nr, nc))
                queue.append(((nr, nc), d + 1))
    return -1

0-1 BFS (when edges are weight 0 or 1):

from collections import deque

def shortest_01(adj, src, dst):
    INF = float("inf")
    dist = {src: 0}
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            nd = dist[u] + w
            if nd < dist.get(v, INF):
                dist[v] = nd
                # Weight 0 → front; weight 1 → back. Maintains BFS invariant.
                (dq.appendleft if w == 0 else dq.append)(v)
    return dist.get(dst, -1)

Reference: cp-algorithms — Breadth-first search

Detect Cycles With DFS Colours, Not "Visited" Alone

A single visited set is not enough to detect cycles in a directed graph — it conflates "we've fully explored this node" with "this node is in our current DFS stack." A node already visited via a different DFS branch is not a cycle. The three-colour scheme (WHITE = unseen, GRAY = on stack, BLACK = done) is the canonical fix: a back-edge to a GRAY node is a cycle; an edge to a BLACK node is not. For undirected graphs, instead track the parent and ignore the edge back to it.

Conflating these is a frequent source of false positives (BLACK nodes flagged as cycles) and false negatives (forgetting that a GRAY node is a back-edge target).

Incorrect (single visited set on directed graph — false positives):

def has_cycle(adj):
    visited = set()
    def dfs(u):
        if u in visited: return True     # ← wrong: BLACK node is fine, not a cycle
        visited.add(u)
        return any(dfs(v) for v in adj[u])
    return any(dfs(u) for u in range(len(adj)) if u not in visited)

Correct (three-colour DFS for directed cycle detection):

def has_cycle_directed(adj: list[list[int]]) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * len(adj)

    def dfs(u: int) -> bool:
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:         # back-edge to ancestor → cycle
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(color[u] == WHITE and dfs(u) for u in range(len(adj)))

Undirected variant (track parent — don't follow the edge you came in on):

def has_cycle_undirected(adj: list[list[int]]) -> bool:
    visited = [False] * len(adj)
    def dfs(u: int, parent: int) -> bool:
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs(v, u): return True
            elif v != parent:            # visited neighbour that isn't where we came from
                return True
        return False
    return any(not visited[u] and dfs(u, -1) for u in range(len(adj)))

Recursion-depth note: Python's default recursion limit is 1000. For deep graphs (chains of length 10⁵), either iterate with an explicit stack or sys.setrecursionlimit(10**6) AND raise the thread stack size (threading.stack_size).

Reference: CLRS Chapter 22 — Elementary Graph Algorithms

Use Dijkstra With A Heap For Non-Negative Weighted Shortest Paths

For weighted graphs with non-negative edge weights, Dijkstra's algorithm with a binary heap runs in O((V+E) log V). It's strictly faster than Bellman-Ford's O(V·E) and is the right default for road networks, network routing, and any "weighted shortest distance" question. The two failure modes to recognize: (1) negative edge weights break Dijkstra silently (it commits to nodes too early and never revisits) — use Bellman-Ford or SPFA. (2) Bidirectional A\* can be dramatically faster when a good heuristic exists, but plain Dijkstra is the safe default.

The standard implementation uses lazy deletion: push every relaxation onto the heap; skip popped entries whose distance is stale. This is simpler than a decrease-key heap and almost as fast.

Incorrect (Bellman-Ford on a graph with all non-negative weights — O(V·E) wasted):

def bellman_ford(n, edges, src):
    # O(V·E) — runs V-1 relaxation passes. For dense graphs that's ~V³.
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Correct (Dijkstra with lazy deletion):

import heapq

def dijkstra(adj: list[list[tuple[int, int]]], src: int) -> list[float]:
    # adj[u] = [(v, w), ...]. All w >= 0.
    n = len(adj)
    dist = [float("inf")] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue  # lazy-deleted stale entry
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

*When you have a heuristic (e.g. Euclidean distance for road graphs), use A\:**

import heapq

def a_star(adj, h, src, dst):
    g = {src: 0}
    pq = [(h(src), 0, src)]
    while pq:
        _, gu, u = heapq.heappop(pq)
        if u == dst: return gu
        if gu > g.get(u, float("inf")): continue
        for v, w in adj[u]:
            ng = gu + w
            if ng < g.get(v, float("inf")):
                g[v] = ng
                heapq.heappush(pq, (ng + h(v), ng, v))
    return float("inf")

Hard constraints:

• Dijkstra requires non-negative weights. Period. A single -1 edge silently breaks it.
• For all-pairs shortest paths on small dense graphs (V ≤ ~400), Floyd-Warshall O(V³) is simpler and often faster than V × Dijkstra.

Reference: cp-algorithms — Dijkstra Algorithm

Use Kruskal Or Prim For Minimum Spanning Trees

When the problem is "connect all nodes with minimum total edge weight," the answer is a minimum spanning tree. Two greedy algorithms are canonical: Kruskal sorts edges by weight and adds them if they don't form a cycle (uses Union-Find — O(E log E)). Prim grows the tree from a starting node, picking the cheapest crossing edge each step (uses a heap — O((V+E) log V)). Both produce an optimal MST; both run in essentially O(E log V).

Pick Kruskal when the graph is given as an edge list — it's the more natural fit. Pick Prim when the graph is given as adjacency lists and is dense, or when you only need an MST starting from a particular node.

Incorrect (enumerate edge subsets, exponential blowup):

# 2^E subsets of edges; checking each for "spans + cheapest" is O(V α(V)).
# Even for tiny graphs (V = 20, E = 50) this is infeasible.
from itertools import combinations
def mst_brute(n, edges):
    best = float("inf")
    for size in range(n - 1, len(edges) + 1):
        for subset in combinations(edges, size):
            # check connectivity, sum weights ... O(2^E) total
            ...
    return best

Correct (Kruskal with Union-Find):

class DSU:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0]*n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        return True

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> int:
    # edges: (weight, u, v). Returns total MST weight.
    dsu = DSU(n)
    total = 0
    for w, u, v in sorted(edges):       # O(E log E)
        if dsu.union(u, v):             # O(α(V))
            total += w
    return total

Alternative (Prim with a heap):

import heapq

def prim(adj: list[list[tuple[int, int]]]) -> int:
    # adj[u] = [(v, w), ...]
    n = len(adj)
    in_mst = [False] * n
    pq: list[tuple[int, int]] = [(0, 0)]  # (weight, vertex), start at 0
    total = 0
    seen = 0
    while pq and seen < n:
        w, u = heapq.heappop(pq)
        if in_mst[u]:
            continue
        in_mst[u] = True
        total += w
        seen += 1
        for v, ew in adj[u]:
            if not in_mst[v]:
                heapq.heappush(pq, (ew, v))
    return total if seen == n else float("inf")

*Both algorithms are greedy and optimal because MSTs satisfy the cut property:* the cheapest edge crossing any cut belongs to some MST. Greedy never has to backtrack.

Reference: cp-algorithms — Minimum spanning tree

Represent Sparse Graphs As Adjacency Lists, Not Matrices

An adjacency matrix uses V² memory and forces every traversal to scan all V neighbours of every node — O(V²) work regardless of how many edges exist. For sparse graphs (E = O(V) or O(V log V)), that's catastrophic: a road network with 10⁶ nodes and 10⁷ edges fits in ~80 MB as an adjacency list but needs 1 TB as a matrix. Adjacency lists store only the edges that exist, giving O(V+E) iteration.

The rule of thumb: prefer adjacency lists by default. Reach for a matrix only when (1) the graph is dense (E close to V²), or (2) the algorithm needs O(1) edge-existence queries (Floyd-Warshall, transitive closure), or (3) V is small (≤ ~1000).

Incorrect (adjacency matrix on a sparse social graph — O(V²) BFS, O(V²) memory):

def shortest_hops_matrix(adj_matrix, src, dst):
    # Inner loop scans all V neighbours every step → O(V²) total, even if the
    # graph has only 5 edges per node.
    n = len(adj_matrix)
    from collections import deque
    visited = {src}
    queue = deque([(src, 0)])
    while queue:
        u, d = queue.popleft()
        if u == dst: return d
        for v in range(n):
            if adj_matrix[u][v] and v not in visited:
                visited.add(v); queue.append((v, d + 1))
    return -1

Correct (adjacency list — O(V+E)):

def shortest_hops_list(adj: list[list[int]], src: int, dst: int) -> int:
    # Inner loop visits only actual neighbours. O(V+E) total.
    from collections import deque
    if src == dst: return 0
    visited = {src}
    queue = deque([(src, 0)])
    while queue:
        u, d = queue.popleft()
        for v in adj[u]:
            if v in visited: continue
            if v == dst: return d + 1
            visited.add(v); queue.append((v, d + 1))
    return -1

Building an adjacency list from an edge list:

def build_adj(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)  # omit for directed
    return adj

When a matrix wins:

• V ≤ ~500 and edges are dense (E > V²/4)
• The algorithm needs is_edge(u, v) in O(1) (Floyd-Warshall, max-flow with Edmonds-Karp on dense networks)
• A bitset adjacency matrix (each row is a packed int) gives O(V²/64) memory and SIMD-style "AND" for neighbour-of-neighbour queries

Reference: Sedgewick & Wayne — Graphs

Use Topological Sort For Dependency Ordering And DAG DP

Whenever the input is "things with prerequisites" (build targets, task scheduling, course planning, expression evaluation, package install order), the right primitive is topological sort. Kahn's algorithm runs in O(V+E), processes nodes once their in-degree hits zero, and detects cycles as a free side effect (any unprocessed node means a cycle). After sorting, DP on a DAG runs in linear time because subproblem dependencies are guaranteed to be resolved before any node is visited.

Don't write ad-hoc "process the smallest first" loops; they're slower and miss cycles silently.

Incorrect (ad-hoc dependency resolution — O(V²) and cycle bugs):

def build_order(tasks, deps):
    # deps[u] = list of prerequisites of u.
    # O(V²) — every pass scans everything; cycle yields infinite loop.
    done, order = set(), []
    while len(done) < len(tasks):
        progress = False
        for t in tasks:
            if t in done: continue
            if all(d in done for d in deps[t]):
                done.add(t); order.append(t); progress = True
        if not progress:
            raise RuntimeError("cycle? infinite loop")
    return order

Correct (Kahn's algorithm — O(V+E), detects cycles):

from collections import deque

def topological_sort(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    # edges (u, v) mean "u must come before v". Returns None if a cycle exists.
    adj: list[list[int]] = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    queue = deque(i for i, d in enumerate(indeg) if d == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None  # None ⇒ cycle

DP on a DAG (once you have the topological order, every recurrence becomes linear):

def longest_path_in_dag(n, edges, weight):
    order = topological_sort(n, edges)
    if order is None:
        raise ValueError("not a DAG")
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for (u, v), w in zip(edges, weight):
        adj[u].append((v, w))
    dist = [0] * n
    for u in order:                      # nodes appear after their dependencies
        for v, w in adj[u]:
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
    return max(dist)

DFS-based topo sort is also O(V+E) and uses post-order; Kahn's version is preferred when you also need cycle detection or want to process in BFS-like waves (e.g. layer-by-layer parallelism).

Reference: cp-algorithms — Topological sorting

Use A Priority Queue For "Always Pick The Smallest" Greedies

A common greedy pattern is "repeatedly pick the smallest (or largest) element from a changing collection." Naively re-scanning for the minimum is O(n) per step and O(n²) overall; a binary heap makes each pick O(log n) and the whole algorithm O(n log n). Canonical examples: Huffman coding (repeatedly merge the two smallest frequencies), merge-k-sorted-lists (smallest head from k lists at each step), task scheduling with cooldowns, rope-merging (minimize total merge cost).

The heap variant has identical correctness to the naive version — only the data structure changes — but the time complexity changes dramatically once n > ~10³.

Incorrect (Huffman with linear min-scan — O(n²)):

def huffman_cost_slow(freqs: list[int]) -> int:
    freqs = list(freqs)
    cost = 0
    while len(freqs) > 1:
        # Find two smallest by scanning — O(n) per iteration, n iterations → O(n²).
        freqs.sort()
        a, b = freqs.pop(0), freqs.pop(0)
        cost += a + b
        freqs.append(a + b)
    return cost

Correct (Huffman with a min-heap — O(n log n)):

import heapq

def huffman_cost(freqs: list[int]) -> int:
    # Each heap pop/push is O(log n). 2n-1 ops total.
    heap = list(freqs)
    heapq.heapify(heap)
    cost = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        cost += a + b
        heapq.heappush(heap, a + b)
    return cost

Merge k sorted lists (priority queue keyed on list heads):

import heapq

def merge_k_sorted(lists: list[list[int]]) -> list[int]:
    # O(N log k) where N is the total element count and k is the number of lists.
    pq = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(pq, (lst[0], i, 0))
    out = []
    while pq:
        val, i, j = heapq.heappop(pq)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(pq, (lists[i][j + 1], i, j + 1))
    return out

The "decrease-key" gotcha: standard binary heaps don't support efficient decrease-key. Common pattern is lazy deletion — push the new (smaller) entry and skip stale entries on pop. This is the same trick used in Dijkstra's algorithm.

Reference: CLRS Chapter 16 — Greedy Algorithms (Huffman)

Use Sweep-Line For Interval Overlap And Maximum-Concurrency Problems

For any problem of the form "given a set of intervals, find X" — merge overlapping intervals, find the maximum number of overlapping intervals at any point, find the smallest set of points hitting every interval, allocate the minimum number of rooms — the canonical technique is sweep-line: convert each interval into two events (start, end), sort the events, sweep left-to-right while maintaining a counter or priority queue. Total work is O(n log n) for the sort plus O(n) for the sweep.

The naive O(n²) check-every-pair approach works only up to n ≈ 10⁴. Sweep-line scales to 10⁷.

Incorrect (pairwise overlap check — O(n²)):

def max_overlap(intervals: list[tuple[int, int]]) -> int:
    # For every point that matters, count how many intervals cover it. O(n²).
    points = sorted({p for s, e in intervals for p in (s, e)})
    return max(sum(1 for s, e in intervals if s <= p < e) for p in points)

Correct (sweep-line — O(n log n)):

def max_overlap(intervals: list[tuple[int, int]]) -> int:
    # Each interval contributes two events: +1 at start, -1 at end.
    # Sort by time; ties: end before start so [1,3) and [3,5) don't overlap at 3.
    events = []
    for s, e in intervals:
        events.append((s, +1))
        events.append((e, -1))
    events.sort()
    current = peak = 0
    for _, delta in events:
        current += delta
        peak = max(peak, current)
    return peak

Merge overlapping intervals (sort by start, merge greedily):

def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    if not intervals: return []
    intervals = sorted(intervals)
    merged = [intervals[0]]
    for s, e in intervals[1:]:
        last_s, last_e = merged[-1]
        if s <= last_e:                    # overlap (or touch)
            merged[-1] = (last_s, max(last_e, e))
        else:
            merged.append((s, e))
    return merged

Minimum rooms / meeting scheduler (heap of end times):

import heapq

def min_rooms(intervals: list[tuple[int, int]]) -> int:
    intervals = sorted(intervals)
    end_heap: list[int] = []
    for s, e in intervals:
        if end_heap and end_heap[0] <= s:
            heapq.heapreplace(end_heap, e)  # reuse a room
        else:
            heapq.heappush(end_heap, e)
    return len(end_heap)

The sweep-line skeleton generalizes to 2D: rectangle area union (sweep + segment tree), line-segment intersection (Bentley-Ottmann), and closest pair of points.

Reference: cp-algorithms — Sweep line algorithms

Prove A Greedy Choice With An Exchange Argument Before Coding It

Greedy algorithms are fast and short — when they work. The trouble: many problems look greedy-shaped but require DP for correctness (0/1 knapsack, longest path), and silently-wrong greedy solutions pass most test cases. The defense: before writing a greedy algorithm, prove its correctness via an exchange argument — show that if any optimal solution disagrees with the greedy choice at step k, you can swap in the greedy choice without losing optimality. If you can't construct that argument, don't ship the greedy; use DP.

Three problems greedy does solve optimally: activity selection (sort by finish time), Huffman coding (always merge two smallest), and minimum-spanning-tree (cut property). Each has a clean exchange-argument proof. Coin change with arbitrary denominations is a famous example where greedy fails.

Incorrect (greedy coin change with non-canonical denominations — wrong answer):

def greedy_coin_change(coins: list[int], amount: int) -> int:
    # For coins = [1, 3, 4] and amount = 6, greedy picks 4 + 1 + 1 = 3 coins.
    # Optimal is 3 + 3 = 2 coins. Greedy is silently wrong.
    coins = sorted(coins, reverse=True)
    used = 0
    for c in coins:
        used += amount // c
        amount %= c
    return used if amount == 0 else -1

Correct (DP coin change — always optimal):

def coin_change(coins: list[int], amount: int) -> int:
    # dp[w] = min coins to make w. O(amount · |coins|).
    INF = float("inf")
    dp = [0] + [INF] * amount
    for w in range(1, amount + 1):
        for c in coins:
            if c <= w and dp[w - c] + 1 < dp[w]:
                dp[w] = dp[w - c] + 1
    return -1 if dp[amount] == INF else dp[amount]

*A correct greedy with an exchange argument — activity selection:*

def max_non_overlapping(intervals: list[tuple[int, int]]) -> int:
    # Sort by finish time; pick the earliest-finishing compatible interval each step.
    # Exchange argument: any optimal solution can be modified to match this greedy choice
    # at step 1 without losing optimality — swap its first interval for ours, the rest
    # still fit. Induction completes the proof.
    intervals = sorted(intervals, key=lambda x: x[1])
    count, last_end = 0, -float("inf")
    for s, e in intervals:
        if s >= last_end:
            count += 1
            last_end = e
    return count

When greedy is tempting but wrong: 0/1 knapsack ("pick highest value-per-weight"), graph colouring ("pick the highest-degree node"), longest path in general graphs. All NP-hard or counter-example-prone.

Reference: CLRS Chapter 15 — Greedy Algorithms

Sort By The Right Key — Earliest Deadline, Smallest Ratio, Largest Density

A surprisingly large family of scheduling and selection problems is solved by sorting on one specific key, then sweeping. The art is identifying the right key. Sorting by start time, by finish time, by duration, by deadline, or by value/weight ratio all give optimal answers for different problems — and using the wrong key gives a fast wrong answer. The exchange argument from the previous rule tells you which key is correct.

Cheat sheet of canonical pairings:

Incorrect (activity selection sorted by start time — wrong answer):

def max_activities(intervals: list[tuple[int, int]]) -> int:
    # Sorting by start time is intuitive but wrong: an early-starting,
    # late-finishing interval blocks many shorter ones.
    intervals = sorted(intervals, key=lambda x: x[0])
    count, last_end = 0, -float("inf")
    for s, e in intervals:
        if s >= last_end:
            count += 1; last_end = e
    return count

Correct (sort by finish time):

def max_activities(intervals: list[tuple[int, int]]) -> int:
    # Earliest finishing time leaves maximum room for the rest.
    intervals = sorted(intervals, key=lambda x: x[1])
    count, last_end = 0, -float("inf")
    for s, e in intervals:
        if s >= last_end:
            count += 1; last_end = e
    return count

Fractional knapsack (notably only the fractional version is greedy — 0/1 needs DP):

def fractional_knapsack(items: list[tuple[int, int]], capacity: int) -> float:
    # items = [(value, weight), ...]
    items = sorted(items, key=lambda x: -x[0] / x[1])  # value-per-weight descending
    total = 0.0
    for v, w in items:
        if capacity >= w:
            total += v; capacity -= w
        else:
            total += v * (capacity / w); break
    return total

Validation step: after coding, hand-trace a small example. If the greedy produces a worse answer than an obvious alternative, the key (or the algorithm) is wrong.

Reference: Algorithm Design Manual — Greedy Algorithms (Skiena)

Use Aho-Corasick For Searching Many Patterns Against The Same Text

When you need to find all occurrences of many patterns in a text, calling KMP or str.find once per pattern is O(P × |T|) — for P = 10⁵ patterns and a 10⁹-byte text, that's 10¹⁴ operations. Aho-Corasick (1975) builds a trie of all patterns, adds failure links (Knuth-Morris-Pratt style suffix transitions), and walks the text once in O(|T| + total pattern length + number of matches). The same per-character cost regardless of how many patterns you're matching.

This is the foundation of: virus scanners (ClamAV scans for 10⁶+ signatures simultaneously), DNA motif search, content filters / profanity blocklists, malware string matching, dictionary-based tokenization, fast spam-keyword detection at email scale.

Incorrect (per-pattern search — quadratic in pattern count):

def find_all_per_pattern(text: str, patterns: list[str]) -> list[tuple[int, str]]:
    # Each `text.find` is sub-linear average but O(|text| · |pattern|) worst.
    # Total: O(P · |text|). At P = 10⁵ this dominates every benchmark.
    matches = []
    for pat in patterns:
        start = 0
        while True:
            i = text.find(pat, start)
            if i == -1:
                break
            matches.append((i, pat))
            start = i + 1
    return matches

Correct (Aho-Corasick — one pass, O(|text| + total |patterns| + |matches|)):

from collections import deque

class AhoCorasick:
    def __init__(self, patterns: list[str]):
        # Build the goto trie, then BFS to add failure and output links.
        self.children: list[dict[str, int]] = [{}]
        self.fail: list[int] = [0]
        self.output: list[list[str]] = [[]]
        for pat in patterns:
            node = 0
            for c in pat:
                if c not in self.children[node]:
                    self.children.append({})
                    self.fail.append(0)
                    self.output.append([])
                    self.children[node][c] = len(self.children) - 1
                node = self.children[node][c]
            self.output[node].append(pat)
        # BFS to set fail and accumulate outputs along fail chain.
        q = deque()
        for c, n in self.children[0].items():
            self.fail[n] = 0
            q.append(n)
        while q:
            node = q.popleft()
            for c, n in self.children[node].items():
                # Follow fail until a node has a child on `c`, or back to root.
                f = self.fail[node]
                while f and c not in self.children[f]:
                    f = self.fail[f]
                self.fail[n] = self.children[f].get(c, 0) if f or c in self.children[0] else 0
                # If the fail-target matches its own pattern, inherit its output.
                self.output[n].extend(self.output[self.fail[n]])
                q.append(n)

    def find_all(self, text: str):
        # Single pass over `text`. Each character does amortized O(1) work
        # (failure links amortize like KMP). Yields (end_index, pattern).
        node = 0
        for i, c in enumerate(text):
            while node and c not in self.children[node]:
                node = self.fail[node]
            node = self.children[node].get(c, 0)
            for pat in self.output[node]:
                yield (i - len(pat) + 1, pat)

# Usage
ac = AhoCorasick(["he", "she", "his", "hers"])
print(list(ac.find_all("ushers")))
# → [(1, 'she'), (2, 'he'), (2, 'hers')]

Performance reality check: a hand-rolled Python version is OK for thousands of patterns; for 10⁶+ patterns at production speed, use pyahocorasick (C extension, ~50x faster) or a SIMD-accelerated implementation (Hyperscan from Intel handles literal+regex multi-pattern at multi-GB/s).

Alternatives:

• Commentz-Walter combines Aho-Corasick with Boyer-Moore shifting — faster in practice for many long patterns, but harder to implement
• Bit-parallel multi-pattern (Wu-Manber, MultiBM) — best for small alphabets and large patterns
• Suffix automaton of the text — invert the problem: build automaton once on the text, query each pattern in O(|pattern|). Use when text is fixed and patterns change.

When NOT to use:

• Only one pattern — use str.find or KMP
• Patterns are regexes — use Hyperscan or RE2's set-of-regex API; Aho-Corasick is literal-string only
• Very few patterns (≤ ~5) — startup cost of building the automaton outweighs the win

Production: ClamAV virus signatures, Snort/Suricata IDS, fgrep (grep -F -f patterns.txt), Lucene's keyword tokenizer, spam keyword scanning at every major email provider.

Reference: Aho-Corasick algorithm — Wikipedia

Use A Bloom Filter For Cheap Probabilistic Membership At Scale

A hash set storing 10⁹ entries needs ~64 GB of RAM (8-byte pointers + load factor). A Bloom filter holding the same set with a 1% false-positive rate needs ~1.2 GB — a 50x reduction — and answers "is x possibly in the set?" in O(k) where k is the number of hash functions (typically 7-10). The cost: no false negatives, but ~1% false positives (configurable, smaller filter = more FPs). It also cannot enumerate members or delete entries (use counting Bloom filter or cuckoo filter for deletion).

The killer use case: filter cheap-to-check elements before an expensive check. URL crawler "have we seen this URL?", database "could this row exist?" (avoid disk seek), CDN "have we cached this object?", spam filter, password-breach checks (HIBP). Every false positive triggers the expensive path; every true negative skips it.

Incorrect (hash set on a billion-URL crawler — 64 GB heap, GC pressure):

def crawl(urls):
    seen: set[str] = set()
    for url in urls:
        if url in seen:        # exact, but at n = 10⁹ this is ~80-100 GB of memory
            continue
        seen.add(url)
        fetch(url)

Correct (Bloom filter — ~1.2 GB for 10⁹ URLs at 1% FP rate):

import math
from bitarray import bitarray
import mmh3  # MurmurHash3 — non-cryptographic, fast

class BloomFilter:
    def __init__(self, n: int, fp_rate: float = 0.01):
        # m = -(n * ln p) / (ln 2)^2 bits; k = (m/n) * ln 2 hashes.
        self.m = max(8, int(-(n * math.log(fp_rate)) / (math.log(2) ** 2)))
        self.k = max(1, int((self.m / n) * math.log(2)))
        self.bits = bitarray(self.m)
        self.bits.setall(False)

    def add(self, key: str) -> None:
        for i in range(self.k):
            self.bits[mmh3.hash(key, seed=i, signed=False) % self.m] = True

    def __contains__(self, key: str) -> bool:
        # False ⇒ definitely not in set. True ⇒ likely in set (with fp_rate false-positive risk).
        return all(
            self.bits[mmh3.hash(key, seed=i, signed=False) % self.m]
            for i in range(self.k)
        )

def crawl(urls):
    seen = BloomFilter(n=10**9, fp_rate=0.01)
    for url in urls:
        if url in seen:        # ~1% of new URLs incorrectly skipped — acceptable for a crawler
            continue
        seen.add(url)
        fetch(url)

When NOT to use:

• The application cannot tolerate even one false positive (membership must be exact)
• You need to delete elements (use counting Bloom or cuckoo filter)
• You need to enumerate members (Bloom filter cannot reveal what's stored)
• The set is small enough that a hash set fits comfortably (n < ~10⁶)

Production deployments: Cassandra and HBase use Bloom filters to skip disk reads. Chrome's "Safe Browsing" used a Bloom filter for the local URL blocklist. Bitcoin SPV clients use Bloom filters to request relevant transactions without revealing which addresses they own.

Reference: Bloom filter — Wikipedia

Use Consistent Hashing For Sharding That Survives Node Changes

Plain shard_id = hash(key) % N is fine until N changes — and then almost every key remaps to a different shard, forcing a cache stampede or full data reshuffle. Consistent hashing (Karger et al., 1997) places nodes and keys on a circular hash space; each key goes to the next node clockwise. Adding or removing a node only moves the keys "between" that node and its predecessor — on average k/n keys instead of n-1/n. Virtual nodes (vnodes) smooth out load imbalance.

This is the foundation of distributed caches (Memcached, Redis Cluster sharding policies), DHTs (Chord, Cassandra, DynamoDB), CDN edge selection, and request routing in microservices.

Incorrect (modulo sharding — resize remaps ~all keys):

def shard_id(key: str, n_shards: int) -> int:
    # Adding a single shard (n=4 → 5) remaps ~80% of keys to a different shard.
    # Every cache miss, every range rebalance.
    return hash(key) % n_shards

Correct (consistent hashing with vnodes — adding a shard remaps ~1/N of keys):

from bisect import bisect_right, insort
import hashlib

class ConsistentHashRing:
    def __init__(self, vnodes_per_node: int = 200):
        # vnodes smooth load: more vnodes → tighter distribution, more memory.
        # 100-500 vnodes/node is the production-tested sweet spot.
        self.vnodes_per_node = vnodes_per_node
        self.ring: list[int] = []                  # sorted vnode positions
        self.node_for_position: dict[int, str] = {}

    @staticmethod
    def _hash(s: str) -> int:
        # MurmurHash or xxHash are faster; SHA-1 shown for stdlib only.
        return int(hashlib.sha1(s.encode()).hexdigest()[:16], 16)

    def add_node(self, node: str) -> None:
        for i in range(self.vnodes_per_node):
            pos = self._hash(f"{node}#{i}")
            insort(self.ring, pos)
            self.node_for_position[pos] = node

    def remove_node(self, node: str) -> None:
        for i in range(self.vnodes_per_node):
            pos = self._hash(f"{node}#{i}")
            self.ring.remove(pos)
            del self.node_for_position[pos]

    def shard_for(self, key: str) -> str:
        # Walk clockwise to the first vnode ≥ hash(key); wrap if needed.
        h = self._hash(key)
        idx = bisect_right(self.ring, h)
        if idx == len(self.ring):
            idx = 0
        return self.node_for_position[self.ring[idx]]

# Usage
ring = ConsistentHashRing()
for n in ("cache-1", "cache-2", "cache-3", "cache-4"):
    ring.add_node(n)
target = ring.shard_for("user:42:profile")

Vnode count tradeoff:

Alternatives:

• Rendezvous hashing (HRW) — assign key to node with max hash(key, node). O(N) per lookup but no ring to maintain; trivially handles node weight changes. Catalyst at Spotify, used by Foursquare.
• Jump consistent hash (Lamping & Veach, 2014) — O(log N) lookup, zero memory, but only works when shards are numbered 0..N-1 (can't easily remove an arbitrary shard).
• Maglev hashing (Google) — fast lookup, minimal disruption, but rebuild cost is high; designed for load balancers where lookups vastly outnumber topology changes.

When NOT to use:

• Fixed shard count that never changes (modulo is simpler and faster)
• Stateless sharding where misses are free (no cache, no replication state to move)
• Strong-consistency systems where deterministic placement matters more than minimal reshuffling

Production: Amazon DynamoDB (originally Dynamo, the paper), Cassandra, Riak, Memcached client libraries (ketama), Akamai CDN edge selection, Discord guild sharding.

Reference: Consistent hashing — Wikipedia