a field guide to algorithms and data structures, stacked one stone at a time
An eleventh Searching entry, and the first over a matrix instead of a one-dimensional array: a grid sorted ascending along both rows and columns, searched by eliminating a whole row or column per comparison from the top-right corner. Verified 0 mismatches against a brute-force oracle across 2,000 random matrices. Two checked pitfalls: starting the walk at the top-left corner instead of top-right, keeping the same branch logic, silently misses values that are really there (59.0% wrong across 3,000 trials — on this page's own 5×6 grid it walks straight down column 0 and never finds 16, sitting at row 2, column 3); and a matrix that's row-sorted but not also column-sorted breaks the same way 40.0% of the time.
A tenth Searching entry that doesn't search an array at all: given a monotonic yes/no
feasibility check over a numeric range, binary-search the range of candidate answers
themselves for the boundary between "no" and "yes," the same halving trick as the array-based
entries aimed at a different kind of range. Worked example: the minimum ship capacity that
loads every package within a fixed number of days. Two checked pitfalls: using an
"exactly D days" predicate instead of "D days or fewer" isn't monotonic in the direction the
search needs — it silently converges on capacity 55 (1 day) instead of the real answer, 15,
on the demo's own 10-package example; and rounding the midpoint up while narrowing with
hi = mid is a genuine infinite loop, confirmed stuck at the same two-value range
for 96 straight iterations past a safety cap.
A ninth Searching entry: binary search's own halving trick, adapted for an array that's sorted and then rotated at an unknown pivot instead of sorted straight through. One comparison per step reveals which of the two halves around the midpoint is still genuinely sorted — there's only ever one rotation break, so it can't be in both — then falls back to plain binary-search logic on whichever half could hold the target. Verified 0 mismatches across 20,770 distinct-value cases and 50,000 duplicate-value cases against a brute-force oracle. Two checked pitfalls: a too-casual sortedness check gives a real wrong "not found" on present data (22/50,000 duplicate trials, 0.044%), and the fix that closes that gap degrades the worst case to O(n) — measured exactly 1,000 iterations on an all-duplicate 1,000-element array versus 10 for a distinct one.
Finds the k-th smallest element without sorting anything, by reusing quicksort's own partition step but recursing into only the one side that can hold the answer — the geometric series n + n/2 + n/4 + ... is what turns quicksort's O(n log n) into expected O(n) here. Demo fades the discarded side of every partition and live-compares pivot strategies. Verified from scratch (86,000+ checks against a sort-and-index oracle, 0 mismatches) and measured exactly: a fixed last-element pivot on an already-sorted array costs precisely n(n-1)/2 comparisons finding the minimum, while median-of-medians holds flat around 5-6x n on that same adversarial input — genuinely linear where the fixed pivot is quadratic.
The only Searching entry that makes no assumption about sortedness — checks every element in turn, correct on shuffled data exactly as on sorted data, in exchange for giving up every other entry's sub-O(n) guarantee. Demo counts real comparisons for the sentinel optimization (append the target as a temporary sentinel to drop the per-iteration bounds check), verified to exactly halve the naive count whenever the target is present, plus a live toggle reproducing the classic bug of porting a sorted-array early-break onto unsorted data — it stops at the very first larger element and silently reports "not found" even when the target is really there.
Finds a value in a sorted array without ever dividing or multiplying — only addition and subtraction, using Fibonacci numbers to split each remaining range at the golden-ratio point (≈38%/62%) instead of binary search's exact half. Demo has three presets on the same 20-element array: an early target where the uneven split wins (2 probes vs. binary search's 4), a late target where it costs extra (6 vs. 5), and an absent target that triggers a one-off check after the main loop — verified by deliberately stripping that check's two guards and finding 128 real out-of-bounds reads across 1,845 test cases, silently harmless in JavaScript but not in a bounds-checked language.
Trades binary search's random access for strictly-forward-only movement: jump ahead in fixed-size blocks, checking only the last element of each, then walk one element at a time through the block that must contain the target — the standard technique for a sorted linked list, which can't jump to an arbitrary index at all. Demo includes a live table sweeping every block size against the loaded target, plus a checked proof that the textbook √n block size sits in a flat worst-case-optimal plateau (comparisons 11 for block sizes 5–8 on the page's 36-element array) rather than a single sharp minimum — and a real counterexample where √n isn't even the best choice for one specific target.
Solves a different problem than the site's other Searching entries: not "find this value" but "find the peak" of a unimodal sequence, using two interior points instead of one midpoint to narrow the range by a third each step. Demo includes a checked example of it converging to a real but wrong local peak on a non-unimodal (two-hump) input, plus a checked head-to-head showing it costs strictly more comparisons than binary search when misapplied to plain sorted-array lookup — 400 vs. 328 total comparisons searching all 64 values of exponential search's own array.
Finds a range for binary search by doubling outward — 1, 2, 4, 8… — instead of needing the array's length up front, which is what makes it the standard technique for unbounded or streaming sorted data. Demo includes a checked head-to-head against binary search on the same 64-element array: 4 probes to binary search's 6 for a target near the front, but 12 to binary search's 7 for a target near the back — a real, counted case where the doubling phase costs more than it saves.
Guesses where the target should be from its value instead of always checking the middle — a phone-book lookup instead of a halving search. Demo includes a real skewed-data example where it degrades to a near-linear scan while binary search on the same array barely notices.
Halving a sorted array's worth of doubt with every comparison. Includes a step-through visualizer you can drive with your own array and target.
An eleventh entry, and the first asking a different question from every other DP-table entry here: find the best-matching region inside two sequences, ignoring dissimilar flanks entirely, instead of comparing two whole strings end-to-end. The mechanism behind BLAST and DNA/protein local alignment — one extra "reset to zero" option turns Edit Distance's own recurrence into a local one. Includes a checked pitfall where reading the answer out of the table's bottom-right corner, the habit every other DP page here builds, gives a real wrong number: 7 instead of the true 9.
A tenth entry, and a third mechanism answering "many candidates at once" — needing no trie and no inverted index, just a distance function obeying the triangle inequality. Arranges a fixed dictionary into a tree keyed by real edit-distance values, then proves whole subtrees can't possibly match and skips them without computing a single distance inside. Includes a checked pitfall, built from this site's own Damerau-Levenshtein page, where a non-metric distance silently breaks the pruning and drops a real match.
A ninth entry, and the second to answer the Levenshtein Automaton's "many candidates at once"
question with a completely different mechanism: slice every string into overlapping 3-character
windows, score overlap with the Dice coefficient, and only ever examine a candidate an inverted
index says shares at least one window with the query. A heuristic, not an exact distance — the
real mechanism behind PostgreSQL's pg_trgm extension. Includes a live fuzzy-search
demo over the same 18-word dictionary the automaton uses, and a checked pitfall where a genuine
one-edit match ("cat" → "cot") scores a flat 0.000, tied with words sharing nothing at all.
An eighth entry, and the first that isn't about one pair: given a query word and a whole dictionary trie, which candidates are within k edits — computed by walking the trie in lockstep with one edit-distance row per node, sharing every prefix's work exactly once and pruning a whole branch the instant its own row proves nothing below it can recover. The real mechanism behind Lucene's and Elasticsearch's fuzzy-match queries. Includes a step-through visualizer over an 18-word dictionary (25 of 35 nodes visited at k=1, 10 pruned, 8 matches) and a live toggle to a broken prune bound that visits exactly the root and returns zero matches, silently, for any k below the query's own length.
A seventh entry, and the first that isn't measuring anything: instead of an edit count or a
similarity score, it maps every string to a fixed-width 4-character phonetic code — two strings
either land on the identical code or they don't. Patented 1918 for the U.S. Census Bureau, still
shipped as SQL's built-in SOUNDEX(). Includes a step-through visualizer encoding two
names side by side, a live toggle reproducing a real bug in the H/W merge-preservation rule
(Ashcraft: correct A261 vs. broken A226), and two checked pitfalls —
Bard/Board/Beard/Bird/Byrd all collide on B630, while true homophones Knight/Night
(K523/N230) don't match at all.
A sixth entry, and the first that isn't a dynamic-programming table or a bit-parallel matcher: a similarity score (0 to 1, not an edit count) built from a position-bounded matching window, a transposition count among the matches, and a bonus for a shared prefix. Includes a live mode toggle comparing Jaro-Winkler against plain Jaro on the classic MARTHA/MARHTA pair (0.961 vs. 0.944), plus three checked pitfalls: a window too narrow to see a swap across a whole 5-letter string, a concrete triangle-inequality violation, and a paired example proving the prefix bonus rewards only a shared beginning — an identical shared suffix gets nothing.
A fifth entry, and a direct extension of Edit Distance: adds a fourth edit operation — swapping two adjacent characters counts as one edit instead of two substitutions, catching typo shapes like "recieve" → "receive" in a single move. Includes a live mode toggle comparing Damerau–Levenshtein against plain Levenshtein on the identical pair (distance 1 vs. 2), plus a checked example ("CA" → "ABC") where the cheap, practical restricted version (OSA) disagrees with the true unrestricted distance and — as a direct consequence — fails the triangle inequality.
A fourth entry, and the actual algorithm behind diff and git diff: instead
of filling a table sized by the input like Edit Distance, or restricting a fixed band like Banded Edit
Distance, this one searches outward by number of edits D = 0, 1, 2, … across the diagonals of the edit
graph, sliding for free through every run of matching characters ("snakes"), and stops the instant a
path reaches the far corner — so cost scales with how different the inputs actually are, not with
their size. Includes a step-through demo over the classic ABCABBA/CBABAC example from Myers' own 1986
paper, and a live toggle to a broken variant that skips the snake: it doesn't report a wrong answer,
just the needlessly worst one (13 edits instead of the true 5).
A third entry, and a different way to exploit the same "only a bounded budget matters" idea Bitap
with Edit Distance uses: instead of packing the error budget into a bit-parallel word, restrict Edit
Distance's own dynamic-programming table to a diagonal band of width k, since any cell farther than k
off the main diagonal provably costs more than k edits to reach. Includes a step-through demo with a
live toggle between the correct version (out-of-band cells treated as infinitely far) and a broken one
that defaults them to 0 instead — the broken version doesn't crash, it silently reports
min(k, true distance), a number that looks like a legitimate answer at every k below the
true one.
Closes the gap Bitap's own Pitfalls section named: substitution-only matching can't tolerate a dropped or inserted character, because every window it checks is locked to the pattern's exact length. This page keeps Bitap's bit-parallel recurrence but adds the other two edit types — the same three-edit set Edit Distance's dynamic-programming table already uses, just packed into bits. Includes a step-through visualizer and a live demonstration of a real, checked quirk: a true match "floods" its own neighborhood with near-miss end-positions, and the flood grows with k.
A fourth mechanism for the same problem: pack "which prefixes could be mid-match" into the bits of a machine word and advance the whole word with one shift, one AND, one OR per text character. Unlike KMP, Aho-Corasick, or Rabin-Karp, this reframing extends directly to typo-tolerant approximate matching — keep one bitmask per number of allowed substitutions. Includes a step-through visualizer over a real spread of exact and fuzzy matches — a default demo checked to find "cat" exactly, "cot" and "bat" with one substitution, and "mad" only once two are allowed.
A twelfth exact-match entry, closing a forward reference Burrows-Wheeler Transform's own intro named
but never linked: the compressed self-index real genome aligners like BWA and Bowtie build
directly on top of the transform. Needs no suffix array and no copy of the original text — just
the transform itself plus two small derived tables, C[] and a rank function
Occ — to narrow a range of matching rows by walking the pattern backward,
last character to first, in time independent of the text's own length. Locates each match with no
stored suffix array at all, by walking the same LF-mapping mechanism the Burrows-Wheeler
Transform page names but never builds, back to the sentinel — checked directly against every
row's independently known position, 0 mismatches across 67,503 row-locates. A fourth mechanism
folded into the site's largest guide comparison, alongside Suffix Array, Suffix Tree, and Suffix
Automaton. Two verified pitfalls: matching the pattern forward instead of backward looks like the
natural loop direction and is wrong 11.1% of 100,000 trials; building the C[] table
from "count ≤ c" instead of "count < c" is a one-symbol change wrong 34.0% of the time.
An eleventh exact-match entry, and a second that answers a different question from the nine-way matcher comparison: not a search at all, but a reversible rearrangement of a text's own characters — sort every rotation, read off the last column — that clumps repeated substrings together for a downstream compressor, the technique behind bzip2 and the FM-index genome aligners like BWA and Bowtie use. Built directly from sorted rotations (same order this site's own Suffix Array reaches by sorting suffixes instead — checked equivalent, 2,000 random trials, 0 mismatches), then reconstructed with no other memory of the original by repeatedly prepending the transform as a column and re-sorting. Round-tripped through an exhaustive 134-string sweep and 5,000 randomized trials with 0 mismatches. Two live-checkable claims via the demo's own run-count stat: a genuinely repetitive text's run count drops 27→11 after the transform, while a no-repeats text goes 12→13 (no help at all) — the transform can't clump context that was never there. A separately measured pitfall: the naive column-by-column decoder is 3.5×-14× more expensive on repeated-character input than random input of the same length at n=51..401, a growing gap real implementations avoid with an O(n) LF-mapping walk.
A tenth exact-match entry, and the first that answers a genuinely different question from the
other nine: given one string with no pattern at all, what is its longest palindromic substring?
Transforms the text (inserting # between every character, plus ^/$
sentinels) so odd- and even-length palindromes become one case, then reuses mirror symmetry around
a running center to get O(n), the same amortized idea behind this site's own
Z-Algorithm applied to palindromic structure instead of a repeated prefix. Verified against
brute-force enumeration across 269,813 strings exhaustively tested before shipping. A live
checkbox skips the mirror-copy's boundary cap, a real, checked bug: on the page's own default
("babaaa"), the correct answer is "bab" but the buggy version reports
"abaaa" — which isn't even a palindrome — and the two versions disagree on 16.6% of
805,350 strings tested. Sits outside the exact-match comparison guide's nine-way table (see its
own "different question" note); the Guides page there has been updated to say so.
A ninth exact-match entry, and a third mechanism for the same "index the text once" inversion
Suffix Array and Suffix Tree already use — this time as the smallest DFA
that accepts every substring of the text (not just its suffixes), with states standing for whole
endpos-equivalence classes instead of one node per suffix or branch point. Verified against
brute-force enumeration across 3,000 random trials with every possible query string exhaustively
checked (1.1M+ membership checks, zero mismatches). A live checkbox skips one line
(states[q].link = clone) during a clone event, reproducing a real bug: on the page's
own default ("banana"), the distinct-substring count breaks (15 → 20, wrong on
63.9% of random trials) while substring membership queries stay completely correct, since
membership only ever follows transitions, never suffix links — a checked, not asserted,
demonstration that the two computations depend on different parts of the same structure.
An eighth exact-match entry, and the second (with Suffix Array) that indexes the text once
instead of paying a fresh cost per search — but by a different mechanism: every suffix goes
into one shared, edge-compressed trie instead of a sorted array, so a query walks straight down
matching pattern characters against edge labels, O(m) with no binary-search log factor. Reference
implementation (naive trie-then-compress, since a real Ukkonen's-algorithm build wasn't
implemented) verified against brute-force search across ~15,400 random (text, pattern) pairs,
zero mismatches. Live checkbox toggles the $ terminator off: on the page's own default
("mississippi" searched for "i"), skipping it makes the suffix "i"
share a node with the longer suffix "ississippi" instead of getting its own leaf, silently
dropping one of the four real occurrences — measured at a 5.1% mismatch rate across the same
random pairs. Complexity section proves, not just measures, that the naive build is
unconditionally O(n²) — exactly n(n+1)/2 steps regardless of content, unlike
Suffix Array's naive sort which is only quadratic on repetitive text — while the final compressed
tree stays within a proven O(n) bound (at most 2n−1 nodes, checked across 5,000 random
builds). Suffix Array and the shared exact-match guide both updated to reflect the new sibling.
No new CSS: reuses .bst-wrap/.bst-node/.hc-edge-label/
.hc-internal verbatim.
A seventh exact-match entry, and the first that preprocesses the text instead of paying
a fresh cost per search: sort all of a text's suffixes once, then answer any later pattern —
nobody needs to know it in advance — with a binary search that proves a match exists, then expands
outward through the sorted table's contiguous run of matching neighbors to find every occurrence.
Verified against brute-force search across 20,000 random (text, pattern) pairs, zero mismatches.
Live checkbox toggles the expansion step off: on the page's own default
("mississippi" searched for "is"), skipping it silently reports only one
of the two real occurrences. Complexity section measures, not just asserts, the naive sort's real
O(n²) blowup on repetitive text by counting actual character comparisons — the ratio to
n doubles every time n doubles. New CSS: .stat-table
tr.sa-current/tr.sa-match, a row-level sibling to .dp-table's
existing per-cell .current/.match.
A sixth exact-match entry and a direct simplification of the site's own Boyer-Moore page: keep the right-to-left comparison, but drop the good-suffix rule entirely and replace the bad-character rule's per-mismatch lookup with a single table keyed to one fixed text position — the window's last character — regardless of where a mismatch actually happened. Same default text as the Boyer-Moore page's own example lets the two demos be compared directly: 5 alignments here against Boyer-Moore's 3. Three checked pitfalls, not just claimed: a table-construction off-by-one that corrupts the shift for the pattern's own last character to zero and stalls the search in place; looking up the character that actually mismatched instead of always the fixed window-end position, which silently skips real matches rather than merely shifting a different amount; and the same periodic-input worst case that defeats Boyer-Moore, where this algorithm degrades to naive search's exact comparison count, not just a similar one.
A structurally different approach from its three siblings: glue pattern and text into one string, build a single Z-array over the whole thing, and read every match straight off it — no separate search phase, no fallback table consulted mid-scan. Reuses the same "reuse what's already proven" idea behind KMP's failure function, applied to a sliding window over the concatenation instead of pattern-only links. Includes a step-through visualizer over the Z-array build with a live naive-search comparison count, plus a checked demonstration of the literally-impossible value the window's missing min-cap produces if skipped.
A genuinely different mechanism than KMP, Aho-Corasick, or Rabin-Karp: compare the pattern against the text right to left instead of left to right, so a single mismatch on the pattern's last character can rule out large stretches of text at once. Combines two independent shift rules — bad-character and good-suffix — always taking whichever proposes the bigger jump. Includes a step-through visualizer over both shift tables and a live comparison count against naive search, plus a checked demonstration of exactly the redundant work Galil's rule (not implemented here) exists to remove.
A fresh angle on the same problem KMP and Aho-Corasick solve by comparing characters: compare cheap rolling-hash fingerprints of the pattern and each text window instead, ruling out most windows with a single O(1) integer check. The catch is that different strings can share a fingerprint — the demo's own default input ships a real hash collision under a deliberately small modulus, caught live by character verification, not just described in prose.
Closes the forward reference KMP's own Pitfalls section left open: search for many patterns at once by building them all into one trie, then generalizing KMP's failure-link idea from "one pattern compared against itself" to "every trie node compared against every other node." Includes a step-through visualizer over the failure-link build and the single-pass scan, and a checked, not just claimed, demonstration of a match — "he" inside "ushers" — that only shows up through the failure-link output chain.
The site's first string-matching entry: naive substring search re-walks the pattern from scratch after every mismatch, which is quadratic on repetitive inputs. KMP precomputes a failure-function table so it never re-examines a text character more than a bounded number of times. Includes a step-through visualizer over the LPS table build and the sliding search, with a live comparison count against naive search and a worked example — checked, not just claimed — of the exact overlapping-match bug a plausible-looking shortcut introduces.
A tenth non-comparison sort, and the first whose keys don't all have the same width. Radix sort and American flag sort both assume a fixed digit count; string keys don't have one, so every recursion level gets an extra sentinel bucket for words that have already run out of characters. Recurses most-significant-character first like American flag sort, but writes into a fresh auxiliary array each level rather than permuting in place. Measured directly: 2,000 random 10-character words examine only 61.3% of the characters a naive full-length scan would touch (they diverge fast), while 2,000 words forced to share an 8-character prefix examine 218.9% of that count instead (every shared level costs a full count-then-place pass). Two checked pitfalls: treating an exhausted word as "nothing to bucket" instead of routing it to the sentinel silently drops data — wrong on 90.9% of 20,000 trials, with a vanished word replaced by a duplicate of its neighbor; forgetting to advance the character position on the recursive call isn't a wrong answer but a stack overflow, crashing 41.6% of 500 random trials and this page's own demo array every time.
A ninth non-comparison sort, and a genuine combination of two already on the site rather than a new idea: takes Bucket Sort's arithmetic mapping over continuous keys and feeds it through Counting Sort's own trick — count hits per bucket, prefix-sum those into fixed start offsets, and every bucket's territory is claimed before a single value is placed. What's left is a small insertion confined to each bucket's own window in one shared output array, no separate per-bucket lists needed. Three checked pitfalls: skipping the in-window insertion produces a wrong order in 18,711 of 20,000 random trials (93.6%) — buckets end up grouped but not sorted; the same clustering weakness bucket sort/Flash Sort/Spreadsort all share costs 57× more comparisons on a narrow-range input at n=200; and an inclusive-instead-of-exclusive prefix sum doesn't just misorder — on this page's own demo array it silently drops two values entirely and leaves two output slots permanently null, wrong on all 20,000 trials tested.
An eighth non-comparison sort, and the first that recurses: classifies values into buckets by
the same arithmetic formula Flash Sort and
bucket sort use, but any bucket still too big becomes
its own region — local min/max rescanned from scratch, classified and permuted again — instead of
finishing with one flat pass. Measured on a clustered input (95% of the array packed into a
20-wide band) that both siblings' own pitfalls sections choke on: up to 10,290× fewer
comparisons than a single-level classifier at n=2,000, the gap widening with
n. Two checked pitfalls: reusing the original array's global min/max instead of
recomputing it per region never finishes (5,000+ region-splits without completing); skipping the
min === max base case hangs outright on duplicate-heavy input. A genuinely
adversarial range (values doubling every step) still collapses toward O(n²) —
recursion narrows a clustered range, but doesn't defeat every skew.
A seventh non-comparison sort, sitting at a real intersection of two entries already on the site: classifies values by an arithmetic formula the way bucket sort does, but permutes them in place via the exact swap-chain-with-cursors technique American flag sort uses for its own digit buckets, then finishes with one flat insertion-sort pass since a computed class (unlike a digit) only promises relative order, not exact equality. Verified against 20,000 random trials and an exhaustive permutation sweep, 0 mismatches. Two checked pitfalls: skipping the finishing pass leaves classes grouped but unsorted (98.8% wrong across 5,000 trials); reusing bucket sort's own unscaled formula never produces a wrong answer — the finishing pass masks it — but silently throws away the whole benefit, measured at up to 84× more finishing work as the array grows.
A sixth non-comparison sort, and the most literal one on the site: no counting, no prefix sums, no computed index — just one hole per possible key value, elements dropped straight in and drained back out in hole order. Sortedness falls out for free from walking the holes in order; the only real work is picking a drain direction, and getting that wrong (draining last-in-first-out instead of first-in-first-out) silently reverses the relative order of equal elements, visualized directly with per-element subscripts showing original input position.
A fifth non-comparison sort, and the first that isn't arithmetic on the values at all: each
number becomes a row of beads on a vertical abacus, and gravity — settled one column at a time,
each column only ever counting beads, never tracking which row they came from — does the actual
sorting. Verified order-independence (two inputs with the same multiset in different row order
settle to the identical output) across 3,000 random trials, plus a live off-by-one toggle: drop
the grid's last column and the true maximum silently collapses into the second-highest value
(1, 1, 3, 4, 5 becomes 1, 1, 3, 4, 4 on the default array) instead of
crashing.
A fourth non-comparison sort, and the first to work most-significant-digit first: count how many values belong in each digit bucket, fix every bucket's index range in advance, then permute the array in place by following swap chains — no auxiliary output array the way radix sort needs one every pass. Trades that stability away, recursing into any multi-element bucket to finish the job. Includes a step-through visualizer, and two real broken variants run for real: a fixed-loop permutation (wrong ~41% of the time over 5,000 seeded trials) and skipping the recursion entirely (wrong ~48% of the time).
A third non-comparison sort, but a genuinely different assumption than its two neighbors
here: not small integer keys, but real-valued keys spread roughly uniformly over a known
range. Scale each value into one of k buckets by arithmetic, then finish each
bucket — usually small — with a plain insertion sort. Includes a step-through visualizer using
the same chained-bucket layout as this site's hash table demo, and a real, checked comparison
of 90 vs. 5,235 insertion-sort comparisons on the same 200 values, uniform versus clustered.
Counting sort's fix for wide numeric ranges: instead of one pass keyed by the whole value, run several passes keyed by one digit at a time, least significant first, each needing only 10 buckets no matter how large the numbers get. Includes a step-through visualizer over the classic three-digit textbook example, and a worked example of what goes wrong when a single pass isn't stable.
The site's first non-comparison sort: tally how many times each value occurs, turn those
counts into a running total, then place every element directly into its final slot — no
comparisons at all, sidestepping the Ω(n log n) bound every other sort here
is bound by. Includes a step-through visualizer showing the count buckets and output array fill
live.
The eleventh Comparison Sorts entry: the only one that guarantees every element is written
to its final array slot at most once — the provable minimum for any in-place comparison sort,
not just an average-case improvement. Finds each element's correct position by counting how
many unfinalized elements are smaller than it, then follows the resulting chain of
displacements (a "cycle") until it loops back to where it started; duplicates are handled by
walking past equal values before writing, which is also what keeps a cycle from spinning
forever. Verified across 2,000 duplicate-heavy trials (100% correct) and confirmed the write
count exactly equals the number of out-of-place elements, the theoretical minimum, in a
separate 2,000-trial check. Two checked pitfalls, both against selection sort on the same
3,000-trial setup: skipping the duplicate-skip step hangs or corrupts 67.7% of the time;
counting with <= instead of < does the same 81.8% of the time.
Measured against selection sort directly: never more writes across 3,000 trials, ~71% fewer on
average. Updated Choosing a Comparison
Sort (ten → eleven entries, new section, added to the live race, fixed a pre-existing
overstatement in Bitonic Sort's own section) and fixed six sibling pages' own "the other N"
count plus one stale "only sort that minimizes writes" claim on selection-sort.html.
The tenth Comparison Sorts entry, and the first whose entire sequence of compare-exchange
operations is fixed by the array's length alone rather than decided by the data — a sorting
network, built for hardware where every lane must run the identical schedule. Recursively
builds a bitonic (rise-then-fall) sequence by sorting one half ascending and the other
descending, then merges it with a halving compare-exchange pattern; non-power-of-two lengths
are padded with +∞ sentinels first, trimmed back off at the end. Verified
with an 8,200-trial stress test (0 mismatches, including negative values and non-power-of-two
lengths) and confirmed the comparator count is exactly identical — not just close — across
sorted, reverse-sorted, and random input of the same size, matching the closed-form
(n/4)·log2(n)·(log2(n)+1) exactly. Three checked pitfalls: skipping padding on a
non-power-of-two length is wrong 99.5% of the time with zero crashes; padding with
0 instead of +∞ lets real negative values get displaced by the
pad, wrong 79.5% of the time; forgetting to flip the second half's sort direction breaks the
bitonic property itself, wrong 91.0% of the time. Updated Choosing a Comparison Sort (nine → ten
entries, new section, added to the live race) and fixed nine sibling pages' own "the other
N" count.
The ninth Comparison Sorts entry, closing a forward reference four other pages had already
named but never linked: the real hybrid behind C++'s std::sort. Runs quicksort by
default, but caps recursion depth at 2·floor(log2(n)) and falls back to heap sort
on whichever range breaches it, plus insertion sort below a small-range threshold — three
algorithms already covered standalone on this site, stitched together. Verified the safety net
fires exactly where the math predicts (sizes 50–1,600, always at n − depthLimit)
and stays silent on random data (0 of 1,000 seeded shuffles) while catching every adversarial
one tried. Also caught and fixed a wrong claim before shipping: a heap-index-offset bug that's
invisible on the ascending demo array (its one fallback happens to land at lo=0)
but corrupts the descending version's output silently. Updated Choosing a Comparison Sort (eight → nine
entries, new section, new table row, added to the live race) and fixed the three other
pages' own dangling mentions.
The eighth Comparison Sorts entry, closing a forward reference three other pages had already
named but never linked: the real hybrid behind Python's sorted() and Java's
Arrays.sort() for objects. Detects existing ascending/descending runs, extends
short ones with binary insertion sort, and merges them back with the same balance-preserving
stack discipline that gives merge sort its guarantee — measured at 1,000 comparisons on an
already-sorted 1,000-element array against plain merge sort's 4,932. Includes a step-through
visualizer with a run stack panel, plus a live counted comparison against merge sort across
five data shapes.
The seventh Comparison Sorts entry, closing selection sort's own forward reference: repeatedly
compares and swaps adjacent pairs so the largest unsorted value bubbles to the end each pass.
Stable, unlike selection sort's naive swap, and only gets an adaptive O(n) best
case with an explicit early-exit flag. Includes a step-through bar-chart visualizer with a
toggle for that optimization.
The sixth Comparison Sorts entry: scans the unsorted remainder for its minimum and swaps
it straight into place — always exactly n(n-1)/2 comparisons no matter the
input, but at most n - 1 writes total, and not stable in its naive swap-based
form. Includes a step-through bar-chart visualizer.
The fifth Comparison Sorts entry: generalizes insertion sort by first shifting elements at wide gaps, shrinking to a final gap-1 pass that is plain insertion sort — but on a mostly- sorted array by then. Includes a step-through bar-chart visualizer.
Turn the array into a max-heap in place, then repeatedly extract the maximum into the last
unsorted slot. Guaranteed O(n log n) with no bad-pivot risk and no merge buffer —
the tradeoff real standard-library sorts make when they fall back from quicksort. Includes a
step-through bar-chart visualizer.
Same divide-and-conquer bet as merge sort, paid off differently: partition around a pivot so everything smaller ends up left and everything larger ends up right, in place, no merge buffer required. Includes a step-through bar-chart visualizer — paste in a sorted array to watch the O(n²) worst case happen.
Split, sort each half, merge the sorted halves back together. Includes a step-through
bar-chart visualizer showing the active merge window and its comparison pointers, and
contrasts with insertion sort: guaranteed O(n log n) in every case, at the cost
of O(n) extra space instead of sorting in place.
Sorting cards in your hand, one at a time. Includes a step-through bar-chart visualizer showing the sorted prefix grow and the "hole" carry an element into place.
The tenth Minimum Spanning Trees entry, and the first that relaxes which vertices even have
to show up — connect only a required subset of terminals, routing through the rest as unpriced
Steiner points if that's cheaper. The general problem is NP-hard, but treating the terminals as a
small complete graph weighted by shortest-path distance and reusing kruskal.html's
own MST builder on that gives a classic, provable 2-approximation. On a five-site network (three
towns needing service, two optional junctions), the approximation lands at weight 8 against a
brute-force-verified true optimum of 7 (ratio 1.14, comfortably inside the guarantee) — it misses
the true optimum because the pairwise-shortest-path view never notices a cheap connector between
the two junctions that's only useful once all three towns are considered together, not any single
pair. Two verified pitfalls: skipping the Steiner points entirely doesn't just cost more, it
leaves one required town completely unconnected (not a worse tree — not a tree over the required
terminals at all); and materializing each terminal pair's shortest path independently, the way the
approximation does, can miss a shared connector a combined route would reuse. Both checked against
the real shipped script via a fake-DOM harness, not just reasoned about. Updated
choosing-a-minimum-spanning-tree-algorithm.html (nine entries → ten, new section +
table row) and bumped "all nine of this site's Minimum Spanning Trees entries" to "all ten" on all
nine pre-existing MST pages' footer cross-links, plus randomized-mst.html's own meta description
("other eight" → "other nine"). Zero new CSS — reuses .kruskal-node.hull/.interior and
.kruskal-edge.accepted/.rejected verbatim from Graham Scan and Kruskal's.
The site's ninth Minimum Spanning Trees entry, and the first that reaches for randomness at
all — picked via the staleness tiebreak among the eight categories tied at 8 entries (this
category's own newest, Euclidean MST, shipped session 282, older than any other tied category's
own newest entry). Flip a coin on every trail, build the minimum spanning forest
F of just the surviving half, then reuse mst-verification.html's own
cycle-property path-max check against F instead of a finished candidate tree — any
trail heavier than the priciest trail on its own F-path is provably safe to discard from
the whole graph's MST, not just the sample's. Verified against a brute-force MST oracle across
20,000 random coin-flip trials via a fake-DOM harness driving the real shipped script: the
filtered result matched the true minimum's weight in all 20,000 (500/500 in the harness's own
smaller live run), while a checkbox exposing the tempting shortcut — trusting the sample's own
forest F directly, no filter — matched only 293 of 20,000 (6/500 in the harness run).
Second checked pitfall: the same-component guard before the path-max query isn't optional
tidiness — removing it crashes treePath outright, since F is a forest, not
one tree, and an unreachable target leaves parent[v] null; measured 9,818 of 30,000
individual edge checks throwing that exact error across 3,000 trials with the guard removed.
Honest about scope: this demo runs the filtering step once, on the full graph, to isolate that
one new idea — the real algorithm's expected linear time comes from interleaving two rounds of
Borůvka contraction before each sample, which this page doesn't build. Updated
choosing-a-minimum-spanning-tree-algorithm.html (eight entries → nine, new section
+ table row) and bumped "all eight of this site's Minimum Spanning Trees entries" to "all nine"
on all eight pre-existing MST pages' footer cross-links, plus this homepage's own guide blurb.
Zero new CSS — reuses .kruskal-edge.current/.accepted/.rejected/.danger/.path and
.kruskal-edge-chip verbatim from Kruskal's and Minimum Spanning Tree
Verification.
The eighth Minimum Spanning Trees entry (230th page), freely picked from nine categories tied
at seven entries by scanning Minimum Spanning Trees' own siblings for a genuinely different
mechanism: a fifth way to build the identical tree, but only when the input is narrower than an
arbitrary graph — vertices that are points in the plane, weight is Euclidean distance. The true
MST is always a subgraph of the point set's own Delaunay triangulation (at most 3n-6
edges), so Kruskal only needs to sort those instead of all n(n-1)/2 pairs. Proved via
an intermediate Gabriel-graph exchange argument (MST edges ⊆ Gabriel edges ⊆ Delaunay edges),
independently confirmed by a 5,000-trial stress harness with 0 mismatches against a complete-graph
Kruskal baseline, plus a separate 5,000-trial check that every MST edge really does satisfy the
Gabriel diametral-circle condition. Re-verified the real shipped script via a fake-DOM harness
driving the actual Load/Step controls across all three of its candidate-edge-set options,
reproducing the exact numbers written on the page. Pitfall demonstrated live: a 3-nearest-neighbor
"shortcut" looks like the same kind of geometric pruning but isn't guaranteed to contain the true
MST — it silently returns a heavier spanning tree on this page's own 8 points, and fails on about
21% of a 3,000-trial random stress check. Zero new CSS — reuses
.kruskal-wrap/.kruskal-edge/.kruskal-node/
.kruskal-edgelist/.kruskal-stats verbatim from Kruskal's, and its own
Bowyer-Watson construction is the identical function from Delaunay Triangulation. Updated the MST
guide (four ways → five, new section and table row) and all seven sibling pages' "all seven" guide
backlinks → "all eight"; added a forward cross-link from Delaunay Triangulation's own page.
The seventh Minimum Spanning Trees entry, freely picked as the site's smallest category (six
entries, every other category at seven or more): given a candidate spanning tree, verify it's
actually minimum without rebuilding it via Kruskal's or Prim's. The cycle property does it in one
pass — a tree is minimum exactly when no leftover edge is cheaper than the priciest tree edge on
the path it would replace. Verified from scratch against an independent brute-force MST oracle
(4,000 random graphs, 20,000 checks, 0 mismatches); self-tested against two deliberately broken
variants first — skipping the structural spanning-tree check lets a cyclic-plus-disconnected edge
set report "valid" instead of erroring, and a strict "less than" comparison instead of allowing
ties wrongly rejects a genuine minimum spanning tree on a three-node all-equal-weight triangle.
Reuses the trail network's exact tree-path routine from Second-Best Spanning Tree, and cross-links
Kruskal's Reconstruction Tree as the same underlying query (priciest edge on a tree path) phrased
as a lookup instead of a pass/fail check. Zero new CSS — .kruskal-wrap/
.kruskal-edge and .dp-wrap/.stat-table reused verbatim.
The sixth Minimum Spanning Trees entry, picked via the staleness tiebreak (four-way tie at 5
entries, Minimum Spanning Trees' newest entry — Second-Best Spanning Tree, 2026-08-10 — the oldest
"newest" of the four): minimizes the tree's single most expensive edge instead of its total weight.
Every MST is automatically an MBST (Kruskal's cycle-rejection rule already drops the priciest edge
on every cycle), but not every MBST is an MST — on the same trail network's one triangle, leaving
out either non-priciest cycle edge instead of Kruskal's own choice still holds the network's
bottleneck at 7 while costing 24 or 26 instead of the true minimum, 22 (all three verified against
a shipped reference implementation via a fake-DOM harness). Pitfall: the bottleneck edge itself
(Overlook–Summit) is a bridge, not part of any cycle, so unlike a cycle's max edge it can't be
dropped — removing it splits Meadow and Summit off from the rest of the network entirely. No new
CSS — reuses .kruskal-wrap/.kruskal-edge
(.accepted/.rejected/.danger) and
.dp-wrap/.stat-table verbatim from Kruskal's and Second-Best Spanning
Tree.
The fifth Minimum Spanning Trees entry, and the first that isn't about building the minimum tree itself: given the MST Kruskal's, Prim's, and Borůvka's pages all reach, what's the next cheapest spanning tree? Adding any leftover edge back in closes exactly one cycle, so the best replacement tree containing it removes the single priciest edge on that cycle — checking all four leftover edges this way is exhaustive, not a heuristic, since the true second-best is always exactly one swap away from the minimum tree (confirmed by brute-force enumeration of every spanning tree in the ten-edge network). Reuses Kruskal's exact trail network and total (22) for direct comparison, landing on 24 via swapping Basecamp–Saddle in for Spring–Saddle.
The fourth Minimum Spanning Trees entry, and the first to tear down instead of build up: start with every edge already in the graph, sort priciest-first, and delete each one unless removing it would disconnect the network. Leans on the cycle property (the max-weight edge on any cycle is never needed) instead of the cut property the other three entries share, and still lands on the identical tree and total weight (22) on the same trail network. Pitfalls ran two broken variants for real: processing cheapest-first instead of priciest-first still produces a valid spanning tree but one costing 45 instead of 22; forgetting to exclude the edge under test before checking connectivity ends with the right edge count (six) but an actually disconnected network, a bug a count-only check can't catch.
The site's third Minimum Spanning Trees entry, and the oldest of the three (1926) despite being taught last: instead of one global sort or one growing frontier, every component picks its own cheapest outgoing edge at once, every round, until one component remains. Uses the same trail network as Kruskal's and Prim's algorithms — same nodes, same costs — and lands on the identical tree and total weight (22) in just two rounds, confirmed against an independent brute-force search and against Kruskal's own reference implementation run on the same data.
The other standard way to build a minimum spanning tree: instead of sorting every edge up front, grow a single tree outward from one node, always reaching for whichever frontier edge is cheapest right now. Uses the same trail network as Kruskal's algorithm — same nodes, same costs — so the two demos are directly comparable, and (ties aside) always land on the identical tree by a different path.
Sort every edge cheapest-first, add each one unless it would close a cycle. Built directly on Union-Find for the cycle check — the site's first algorithm to lean on a data structure from a separate entry rather than reimplementing its own. Includes a step-through demo over a weighted trail network showing accepted edges, rejected edges, and the live partition into connected sets.
The eleventh Shortest Paths entry: an admissible A* heuristic built with no coordinates at all — one Dijkstra pass from a landmark, in both directions, and the triangle inequality alone gives a valid lower bound to any goal. Verified on a seven-node directed graph: the correct heuristic matches optimal on all 30 reachable pairs, visiting as few as 3 of 7 nodes where plain Dijkstra visits all 7. A checked shortcut — treating the directed graph as symmetric and skipping the second Dijkstra run — gets 27 of 30 pairs right by accident and returns a path 229% more expensive than optimal on the other 3.
The tenth Shortest Paths entry: A*'s heuristic-guided f = g + h bound wrapped around Iterative Deepening DFS's repeated bounded depth-first search instead of a priority queue, trading A*'s O(V) open set for O(d) memory. An editable wall maze with A*'s own heuristic-mode toggle shows an inflated heuristic converging on a real wrong answer (cost 21 instead of the true 15), and losing the current-path-only cycle check produces a second, more insidious wrong answer that does less total work than the correct version, not more. A measured 15.8x node-visit overhead over A* on the same maze grounds the actual memory-for-time trade.
The ninth Shortest Paths entry, and the second (after Yen's) to answer something other than "what's the single cheapest path": two paths, source to target, that share no edge at all — a genuine backup route, not just the next-ranked one. One Dijkstra pass, a Johnson-style reweighting that reuses the exact reduced-cost trick Johnson's Algorithm already uses, then a second Dijkstra on a graph where the first path's own edges are reversed at cost zero. Verified against brute-force enumeration across 6,000 random graphs; a checked example shows the reversal trick is sometimes the only way to find a second disjoint path at all, not just a cheaper one.
The eighth Shortest Paths entry, and the first to answer a different question: not the single cheapest path, but the K cheapest loopless paths, ranked. Built on repeated restricted Dijkstra searches via the root-path/spur-node trick, verified against brute-force enumeration on a six-node graph — all 7 simple paths found in the right order, with real ties at cost 8 and 11. A variant that skipped excluding root-path nodes (not just the matching edge) from each spur search was stress-tested separately and found to produce paths that revisit a node within the first few thousand random trials, confirming why that exclusion matters.
The middle case between plain BFS and Dijkstra: edges cost only 0 or 1, so a deque — push a
free neighbor onto the front, a normal one onto the back — keeps BFS's exact
O(V + E) bound instead of paying for a priority queue. Closes a forward reference
from the deque entry's own "where deques show up" list. On the demo's default board, cutting
across a free ice patch costs 7 against 16 the long way around, and a from-scratch reference
implementation matched an independent Dijkstra check across 3,000 random grids.
Bellman-Ford with a FIFO queue instead of fixed passes: only a node whose distance just improved gets re-examined, so most edges never get rechecked at all. Same worst-case bound as Bellman-Ford, but the demo converges in 7 dequeues and 9 relaxation checks against Bellman-Ford's fixed 54 on the identical shipping network. A safeguard checkbox shows what a per-node enqueue-count cap buys: with it on, a rebate loop is caught the instant one node's count passes the node total; with it off, the same graph's queue never empties on its own — capped at 20 dequeues for the demo, not because the algorithm would have stopped there.
All-pairs shortest paths that handle negative edges without Floyd-Warshall's flat
O(V³): one Bellman-Ford pass computes a per-node potential that reweights every edge
non-negative without changing which path is shortest, then plain Dijkstra runs once per node.
Reuses the exact shipping network and rebate-loop toggle from Bellman-Ford and Floyd-Warshall — the
demo's own live potentials strip shows the reweighting phase itself catching a negative cycle and
aborting before Dijkstra ever runs, and the final table matches Floyd-Warshall's exactly.
Dijkstra generalized with a goal in mind: reorder the same priority queue by
f(n) = g(n) + h(n), cost so far plus a heuristic estimate of what's left, and the
search leans toward the target instead of flooding outward evenly. Reuses Dijkstra's exact
weighted-terrain grid so the two are directly comparable, with a heuristic-mode toggle showing
a worked, verified example of an inflated (non-admissible) heuristic actually returning the
wrong path.
Every pair at once instead of one source at a time: for each candidate "through" node in turn, ask whether routing through it beats what's already known, for every pair of nodes simultaneously. Reuses Bellman-Ford's exact shipping network so the two demos are directly comparable — same graph, same rebate loop toggle, but a live 6×6 distance matrix instead of a single-source distance strip, and negative-cycle detection via the matrix's own diagonal going negative instead of a flood-fill.
Dijkstra generalized further: give up the "finalize once popped" shortcut entirely and just
relax every edge, V - 1 times over. Slower, but correct even with negative edges,
and able to detect the one case where "shortest path" stops meaning anything — a negative-weight
cycle. Includes an interactive shipping-network demo with a rebate (negative-weight) route, and a
toggle that closes a rebate loop and shows the algorithm correctly refusing to report a finite
distance instead of returning a wrong one.
BFS generalized: swap the plain queue for a priority queue ordered by accumulated cost, and shortest-by-hop-count becomes cheapest-by-total-weight. Includes an editable weighted-terrain grid — click cells to set their cost, then step through and watch the priority queue route around the expensive ground.
The site's eleventh dynamic-programming entry, and the first indexed by a position in the decimal digits of a single number rather than an array position, a range, a bitmask, or a tree node — plus a boolean flag for whether the digits chosen so far still match the number exactly ("tight") or have already fallen below it ("free"). Counts how many integers up to N share a digit-level property, here digits summing to a target, in O(digits · target) instead of scanning every integer. A 3,000-trial sweep found two tempting shortcuts wrong on 2,387 (79.6%) and 2,440 (81.3%) of random trials: computing the bounded table the same unbounded way as the free one, and dropping the one term that keeps the search following the number's own digits to the end — which silently loses the number itself.
The site's tenth dynamic-programming entry, and the first indexed by a node in a tree rather than an array position, a range, or a bitmask. Every node gets two numbers — its best score included, and its best score excluded — combined child-before-parent in a single O(n) pass, the fastest entry in the category by time. A 3,000-trial sweep found a tempting shortcut in the exclude formula (forgetting that a child might be worth more skipped than taken) wrong on 46% of random trees, and a tempting reconstruction bug (letting "forced excluded" cascade past a node's direct children) wrong on 68%.
The site's ninth dynamic-programming entry, and the first indexed by an exponential state — a subset of visited waypoints, not a range, count, or position. Solves the Traveling Salesman Problem's optimization question (cheapest Hamiltonian cycle, not just whether one exists) by bitmask DP, cutting brute force's O(n!) down to O(n² · 2ⁿ) — measured directly at n = 12: brute force took ~3.1s against Held–Karp's ~5.8ms, roughly 500× faster already at a size this small. Caught a real bug in its own shipped route-reconstruction code before shipping (a duplicated start city) via a fake-DOM harness driving the real demo, not just a reference-model stress test.
The site's eighth dynamic-programming entry, and the deliberate version of the accident 0/1 Knapsack's own Pitfalls section warns against: flip the compressed table's capacity loop from descending to ascending, and item reuse goes from a bug to the whole problem — items become unlimited-supply instead of one-per-item. A live single-row demo backtracks to an actual optimal combination, and the Pitfalls section catches a real, checked surprise: the identical optimal value of 14 backtracks to a different combination (two Pouches vs. Bar + Coil) depending on which loop runs outermost.
The site's seventh dynamic-programming entry, and the first indexed by a whole contiguous range of one sequence rather than a position in one or two. Given a chain of matrices, find the grouping that minimizes scalar-multiplication cost — associativity guarantees every grouping gives the same result matrix, but the demo's own five possible groupings span a 6.6x cost range (5,000 to 33,000). A live triangular DP-table demo fills by increasing chain length, then reconstructs the optimal parenthesization as a tree, not a straight-line backtrack.
The site's sixth dynamic-programming entry, and its first with a genuinely different shape from the other five: no table, just one running value carried forward. Solves the maximum subarray problem — largest-sum contiguous run in an array of positive and negative numbers — with one left-to-right pass deciding, per element, whether to extend the running subarray or start fresh. A zero-init toggle demonstrates a classic bug: on an all-negative array it silently reports the empty subarray (0) instead of the true answer (-1), verified against the real shipped script and an independent brute-force check.
The site's fifth dynamic-programming entry, closing the forward reference Activity Selection's own Pitfalls left open: give every activity a weight, and the finish-time greedy that provably maximizes count stops maximizing value. Reuses Activity Selection's own eleven-activity dataset with one weight added, and a DP recurrence over the same sorted order — each activity's predecessor found by binary search — fixes it. The demo's comparison line shows greedy losing 5× on that data (weight 4 vs. the DP's optimal 20), confirmed against an independent brute-force search over all subsets.
The site's fourth dynamic-programming entry, and the first whose fastest known approach isn't really a DP recurrence — it's binary search wearing a different hat. Includes a step-through demo of the O(n log n) patience-sorting approach, reusing Binary Search's own lo/hi/mid narrowing as a subroutine, plus a Pitfalls section that catches a genuine misreading: the algorithm's own working array is not itself a valid answer.
The site's first dynamic-programming entry that isn't about aligning two strings: given items with a weight and a value each, and a knapsack with a fixed capacity, which items maximize total value? Includes a step-through demo over a fixed hiking-pack item set, with a Pitfalls section that shows — not just claims — that greedy-by-value-density picks a genuinely worse pack than the DP table finds.
Longest Common Subsequence generalized: instead of just skipping characters, three edits are allowed — insert, delete, substitute — and the table finds the fewest of them needed to turn one string into another. Includes a step-through demo that fills the same kind of DP table, then backtracks to reconstruct the actual edit script and renders it as a character-by-character alignment strip.
The site's first dynamic-programming entry — a new family alongside the greedy and traversal algorithms above: solve small subproblems once, save the answers, reuse them instead of recomputing. Includes a step-through demo that fills the DP table cell by cell, then backtracks through it to reconstruct the actual matched characters, not just the length.
The site's tenth Greedy entry, and the first that pairs up two equal-size groups instead of
scheduling, covering, or filling anything: free men propose down their own preference list one
at a time, a free woman accepts, an already-engaged woman trades up only for someone she
prefers more. Verified on a hand-built 3-man/3-woman instance (brute-forced against all 6
possible pairings to confirm exactly 2 are stable) via a fake-DOM harness driving the real
shipped script through all four (who-proposes × engagement-rule) combinations: men
proposing gives M1-W2/M2-W1/M3-W3 with a real mid-run dump (W1 drops M1 for M2), women
proposing gives the genuinely different M1-W3/M2-W1/M3-W2 — same preferences, opposite outcome
for M1 (his 2nd choice vs. his last), matching the man-optimal/woman-pessimal theorem exactly.
Checked pitfall: locking an engagement irrevocably (first acceptance final, no trading up)
produces a real blocking pair on this exact instance and goes unstable on 68.8% of 20,000
random 4-person trials, against 100% stability for the correct deferred-acceptance rule. Added
a new Tier 1 proof shape (no wasted proposal survives) to
choosing-a-greedy-strategy.html (nine entries → ten) — the guide's first entry
where "exact" doesn't mean one right answer, since who proposes decides which of possibly
several stable matchings you get. Zero new CSS — reuses
.kruskal-node/.kruskal-edge(.current/.accepted/.rejected)
verbatim from the site's existing bipartite-graph demos.
The site's ninth Greedy entry, and the first over a graph rather than an interval set,
frequency table, or capacity: walk vertices in a fixed order, assign each the smallest color
number none of its already-colored neighbors hold. The fast, always-linear counterpart to
Graph Coloring's exact backtracking search — same
question, no optimality guarantee at all beyond the trivial Δ+1 bound (max degree plus
one) on colors used. Verified with a hand-built 8-vertex crown graph (true chromatic number 2,
confirmed by an independent BFS two-coloring check): the identical algorithm and correct
neighbor-checking rule finds that exact 2-coloring under a "grouped" vertex order but is forced
to all 4 colors the Δ+1 bound allows under an "interleaved" order on the same graph — a
pure order effect, re-verified through the real shipped script via a fake-DOM harness. A
5,000-random-order sweep confirmed the Δ+1 bound holds for every order (never a fifth
color) and showed the gap between greedy's output and the true minimum has no fixed ceiling —
unlike Set Cover's provable O(ln n) approximation ratio, stretching this same construction to
n vertices per group forces exactly n colors under a bad order while the true chromatic number
stays 2 forever (checked directly at n = 2, 3, 4, 5, 8, 10, 20). Second checked pitfall:
checking only the most recently colored neighbor instead of every colored neighbor produces a
genuinely invalid coloring — real same-color edges, not just extra colors — in 1,264 of 5,000
random-order trials (25.3%), caught by an independent full-edge conflict scan. Added a new
Tier 4 ("never exact, and not bounded") to choosing-a-greedy-strategy.html (eight
entries → nine), bumped "other seven Greedy entries" to "other eight" on all eight pre-existing
Greedy pages, fixed a pre-existing overstatement on interval-partitioning.html
(claimed all seven other entries prove optimality by exchange argument — Coin Change and Set
Cover never did), and cross-linked graph-coloring.html. Zero new CSS — reuses
.topo-wrap/.topo-canvas/.gc-node.c0-.c3/.gc-edge
verbatim from Graph Coloring.
The site's eighth Greedy entry, and the first whose proof isn't an exchange argument at
all: a third distinct question over the same interval input as
Activity Selection and
Interval Point Cover — schedule
every talk, using the fewest parallel rooms. Optimality falls out of matching a
lower bound (max simultaneous overlap needs that many rooms, by pigeonhole) to an upper bound
(greedy, processing by start time, never opens more rooms than that same overlap depth) — no
swap-in-the-optimal-solution argument needed. Verified against an independent
maximum-overlap sweep over 20,000 randomized trials (0 mismatches) and re-verified through the
real shipped script via a fake-DOM harness (300 more trials plus edge cases, 0 mismatches).
Two live-switchable near-misses, both measured rather than asserted: checking only the most
recently used room instead of scanning every open one stays valid but opens more rooms than
necessary 70% of the time (worst case on the default 8-talk set: 6 rooms where 3 suffice);
comparing a candidate room's free time against the new talk's end instead of its
start produces an actively double-booked schedule 85% of the time, caught by an
independent same-room-overlap check, not the assignment loop's own bookkeeping. Updated the
Greedy guide (seven entries → eight, new proof-shape paragraph + table row) and bumped "other
six Greedy entries" to "other seven" on all seven pre-existing Greedy pages. Zero new CSS —
reuses Activity Selection's .as-timeline family verbatim, including Interval
Point Cover's .as-bar.covered/.as-bar.uncovered additions.
The site's seventh Greedy entry, freely picked (staleness tiebreak among four categories tied
at six entries — Greedy's newest, 2026-08-13, was the oldest "newest" of the four). A genuinely
different question from Activity Selection
despite sharing the same sort-and-sweep shape and the same exchange-argument proof pattern: find
the fewest points that touch every interval, rather than the largest non-overlapping subset.
Verified exhaustively (1,365 four-interval subsets drawn from all 15 possible intervals on a
0–5 grid) and via 20,000 randomized trials against a brute-force minimum, 0 mismatches either
way, before writing content. Two live-switchable near-misses, both checked against 10,000
seeded random trials rather than asserted: placing the point at each interval's start instead of
its end stays valid but is suboptimal 67.5% of the time (worst case found: 8 points where 3
suffice); sorting by start instead of end produces a point set that doesn't even cover every
interval 71.5% of the time, including on the demo's own default eight-interval set. Re-verified
the real shipped script via a fake-DOM harness (all three rules on the default data, plus
malformed-input handling), which also confirmed the demo's own end-of-run validity check — not
the algorithm's own step-by-step bookkeeping — is what actually catches the second bug's
silently-wrong "covered" markings. Updated the Greedy guide (six entries → seven, new Tier 1
paragraph + table row) and bumped "other five Greedy entries" to "other six" on all six
pre-existing Greedy pages. No new CSS beyond two small additions
(.as-bar.covered/.as-bar.uncovered) — everything else reuses Activity
Selection's .as-timeline family verbatim.
The site's sixth Greedy entry, and the first that's never claimed to be exactly optimal: pick
the fewest sets whose union covers a universe, an NP-hard problem in general. The greedy rule —
take whichever remaining set covers the most still-uncovered elements each round — comes with a
proven H(n) ≈ ln(n)+1 approximation ceiling instead. A hand-built 5-set, 10-element
instance shows greedy landing on 3 sets against a brute-forced true optimum of 2, and a plausible
"smallest set first" alternative doing worse still at 4 — both live and switchable in the demo.
The site's fifth Greedy entry, and the first where the optimality proof needs two independent parts: sorting by profit descending picks the right jobs, but a second, separate rule — place each job in the latest free slot at or before its deadline, not the earliest — decides where they run, and getting that second part wrong costs real profit even when the sort is right. The demo lets you switch placement rules live and watches a brute-forced optimal-profit check catch the shortfall (270 vs. 240 on the default 5-job set) immediately.
The site's fourth Greedy entry, and the first where correctness depends on the input data
itself, not just the problem shape: greedy is provably optimal for U.S. coins
({1, 5, 10, 25}, a canonical system) but genuinely fails for others. The
demo cross-checks every run against a live DP optimum, showing two distinct failure modes on
small denomination sets — merely suboptimal, and outright stuck with no answer even though one
exists — plus the same coins failing on one amount and succeeding on another.
The site's third Greedy entry, and the sharpest before/after of the three: reuses 0/1 Knapsack's own five-item dataset to show the exact same rank-by-value-per-weight rule that 0/1 Knapsack's own Pitfalls section catches failing — provably succeeding once items can be split. Includes a step-through fill demo and an exchange-argument proof of why splitting is what makes the greedy rule airtight.
The site's second Greedy entry: sort activities by finish time and take each one that doesn't conflict with what's already chosen — the classic exchange-argument proof of optimality. The demo lets you switch to two other plausible-looking rules (earliest start time, shortest duration first) and brute-forces the true optimum live, so you can watch both alternatives provably fall short on the same data instead of just being told they would.
The site's first entry filed under a dedicated Greedy category: repeatedly merge the two least-frequent symbols into one node until a single tree remains, then read prefix-free binary codes straight off it — provably optimal, unlike 0/1 Knapsack's own greedy heuristic. Includes a step-through priority-queue-and-tree visualizer over an editable message, with a real measured 30.3% bit savings over a fair fixed-width baseline (not the misleading 8-bit-ASCII comparison).
Tenth Backtracking entry, and the first that searches for the best answer instead of
any valid one — every other entry on this site answers a yes/no or find-one/find-all question;
this page maximizes total value under a weight cap (0/1 Knapsack), reusing
0/1 Knapsack's own five-item dataset so the final answer
checks directly against that page's dynamic-programming table. Items are sorted once by
value-per-weight ratio, then a fractional-knapsack relaxation computed at each node gives an
honest upper bound on what the branch could still be worth; if that optimistic number can't beat
the best complete value already found, the branch is pruned even though nothing about it is
illegal. Cuts the demo's search from 43 nodes (plain backtracking, no bound) to 18, reaching the
identical best value 22 the DP table finds — by a different, equally valid tied-optimal
combination of items (Stove + Rope + Water, not Tent + Food). Two pitfalls verified against the
real shipped generator: sorting the bound's items by raw value instead of ratio breaks the
bound's validity and produces a real wrong answer (5 instead of the true 6, on a throwaway
4-item counterexample where the correct order finds it fine); updating the incumbent only at
leaves instead of at every node visited still finds the correct optimum but prunes less
(21 nodes instead of 17 on a throwaway 8-item instance). Fake-DOM harness (Node's vm,
no jsdom) drove the real shipped generator through all 65 steps and matched exactly.
Added a new "changes the question itself" section to
Choosing a Backtracking Strategy
(nine entries → ten, new table row) and bumped all nine existing siblings' "other eight" → "other
nine" cross-references. Zero new CSS — reuses .dp-item/.dp-result/
.dp-stats/.log verbatim from Subset Sum's and 0/1 Knapsack's own
demos.
Ninth Backtracking entry, and the first where the rejection rule never looks at anything
already chosen — every other entry rejects a candidate for conflicting with a placed queen,
color, or visited cell (or, for Subset Sum, a running total); this page's candidate piece is
accepted or rejected purely by checking whether it, by itself, is a palindrome. On the demo's
fixed string aabaa, the search finds all 6 valid partitions after 22 palindrome
checks across 15 recursive calls, cross-checked against brute force over all 16 possible
cut-point combinations. Pitfalls section catches a real bug that doesn't show up as a wrong
count: forgetting to undo a committed piece still reports the true number of solutions (6) while
every one after the first is corrupted with leftover pieces from abandoned branches. Second
pitfall measures a real, growing cost of skipping a precomputed palindrome table — 1.47x
redundant rechecking on this page's own string, 7.08x on a longer degenerate case.
Eighth Backtracking entry, and the first that changes the undo mechanism itself rather than just the rejection rule: built for exact cover (partition a universe exactly among chosen subsets), covering a column in a circular doubly linked list and undoing it by relinking the same nodes in the exact reverse order — an O(1) pointer restore instead of an array pop/rescan. Verified against exhaustive brute force on Knuth's own 6-row toy example (unique solution {B, D, F}) and a 3,000-trial random stress test, 0 mismatches either way. Pitfalls section measures the column-choice heuristic mattering by four orders of magnitude (10 vs. 144,436 attempts on a purpose-built instance) and catches a genuinely new failure mode: restoring columns out of order doesn't run slower, it silently returns an invalid "solution" (an item double-covered) — reproduced directly, 2 of 2,000 stress trials.
Seventh Backtracking entry, and the first where a candidate gets rejected by arithmetic instead of a structural conflict — a running sum that's already overshot the target, or a remaining budget too small to ever reach it. On the demo's 5 items and target of 9, backtracking finds all 3 solutions after 20 recursive calls against 32 brute-force subsets, split between 5 immediate overshoot rejects and 3 remaining-budget prunes. Pitfalls section catches a real double-counting bug (skip the early return on hitting the target exactly, and one solution gets recorded twice) and a positive-only assumption behind both pruning rules, verified with a throwaway script showing a real solution silently missed once negative numbers are allowed.
Sixth Backtracking entry, and the first where nothing is ever outright illegal — every knight move that stays on the board and lands on an unvisited square is legal, so the search lives or dies on candidate order rather than candidate rejection. Plain in-order search on the demo's 5×5 board needs 287 attempts and 263 backtracks; switching only the order to Warnsdorff's rule (always try the square with the fewest onward options first) needs 24 attempts and zero backtracks. The 4×4 board has no tour at all, proven by exhausting all 2,222 attempts rather than just failing to find one.
Fifth Backtracking entry: find a path spelling a target word through a letter grid's own orthogonal adjacency, marking each cell visited on commit and releasing it on backtrack — the same discipline Hamiltonian Path already uses, moved from a general graph to a fixed 2D board. A live "mark cells visited" checkbox demonstrates the pitfall directly: with it on, the word ABCB correctly comes back not-found after 4 backtracks; switch it off and the identical search reports ABCB found by illegally reusing one cell as both its second and fourth letter, zero backtracks.
Fourth Backtracking entry: extend a walk one unvisited neighbor at a time instead of assigning a value to a fixed slot, the same reject/place/backtrack shape turned toward building an ordered sequence. A goal toggle on the identical 6-vertex graph makes the cost of a stricter question concrete — "visit every vertex" (Hamiltonian path) finds one in 14 attempts and 9 backtracks, "and close back to the start" (Hamiltonian cycle) needs 20 attempts and 15 backtracks on the exact same graph and neighbor order.
Closes the forward reference both N-Queens' and Sudoku's own Complexity sections named: assign each vertex of a graph one of k colors so no edge joins two same-colored vertices, same reject/place/backtrack shape as the other two pages. The demo's own wheel graph (a hub touching a five-vertex rim cycle) has chromatic number 4, confirmed by independent brute force — pick k = 3 on the identical graph and the search correctly exhausts all 84 attempts before concluding no valid coloring exists, pick k = 4 and it finds one in 15.
The natural next backtracking page N-Queens itself named: fill a 9×9 grid one empty cell at a time, rejecting a digit the instant it collides with its row, column, or 3×3 box, backtracking the moment none of 1–9 survive. The default puzzle — 48 givens, 33 blanks, checked by independent exhaustive search to have exactly one solution — solves in 273 attempts and 12 backtracks; Pitfalls shows the same unmodified algorithm needing 445,778 attempts on a real published "world's hardest" puzzle, since reading-order cell selection isn't neutral.
The site's first genuinely new algorithmic paradigm since dynamic programming: place N chess queens so none share a row, column, or diagonal by trying placements one column at a time and abandoning a doomed partial board immediately instead of finishing it first. Includes a step-through visualizer over every rejection and every backtrack, not just the solutions found, with live attempt counts showing the real, computed gap against brute force — 15,720 attempts versus 16,777,216 full boards on an 8×8 board.
A tenth Game Trees entry, and a third independent refinement of alpha-beta alongside Principal Variation Search and MTD(f) — remembers which move caused a beta cutoff at each search depth and tries it first the next time a sibling branch reaches that same depth. Cuts an empty board's search from alpha-beta's 20,866 nodes to 8,038 (61.5% fewer), beating Principal Variation Search's own empty-board figure at a fraction of the bookkeeping. Two checked pitfalls: skipping the legality check on a stored killer plays into an occupied cell, silently corrupting the board and returning a wrong score (0 instead of -7 on the demo board, more nodes visited, not fewer); keying killers by board position instead of depth stays correct but throws away most of the benefit (zero savings on the small demo board, since no position happens to repeat).
A ninth Game Trees entry, and the first whose entire search strategy is a null-window probe — no full-window search ever runs. Repeated one-point-wide probes against a shared, bound-tagged memory table narrow a lower and upper bound together until they meet, converging on the true value in 2 to 4 probes across four tested starting guesses, always landing on the same answer (7) regardless of how good the guess was. Finally builds the exact/lower-bound/upper-bound tagging Transposition Tables' and Principal Variation Search's own pages both flag as necessary but unbuilt — skip it, checked directly, and the standard first guess of 0 silently returns 0 (a draw) instead of the true value, 7 (O can force a win).
An eighth Game Trees entry, and like Transposition Tables and Zobrist Hashing it doesn't decide a move by itself — it decides whether a search-horizon position is settled enough to trust a static evaluator's number at all. A checked capture-chain model shows a fixed depth's evaluation flickering between right and wrong depending on exactly where the horizon lands (+1, 0, +1, 0, +1 across depths 1-5), while quiescence search — which refuses to stop while a capture is still on the table — holds steady at the true value (+1) every time. A second checked pitfall shows what happens without the stand-pat option that makes that possible: +5 instead of the true +1, not a rounding error but the width of the entire exchange.
A seventh Game Trees entry, and like Transposition Tables it doesn't decide a move at all —
it's the specific technique that makes that page's own cache key cheap to maintain: precompute
one random number per (square, mark), then XOR it in on a move and out again on undo instead of
rebuilding a key from the whole board every time. Checked touch-for-touch against Transposition
Tables' own reference implementation on the same fixed board: the naive key touches all 9 cells
per node regardless of hit or miss (513 touches across 57 nodes); Zobrist touches 112 (one XOR
per move made or undone) — a 4.6x reduction. Pitfalls catches a real, checked tradeoff a
board-string key never has: at a deliberately narrow 16-bit hash width, two genuinely different
positions (OXX....OO and O.XOXO.X.) collide on the identical value.
A sixth Game Trees entry, and the first to deliberately search less than the whole tree: run to depth 1, then depth 2, then deeper, evaluating any node cut off before the game ends with a heuristic (open-line counting) instead of a real outcome, and reusing each finished iteration's best root move to order the next. Verified on the same fixed board as Minimax and Transposition Tables: depth 1 lands on the true best move for the wrong reason, depth 2 flips to a genuinely worse one, and only depth 3 recovers the right answer for good — a checked, non-monotonic convergence, not a claimed one. Also verified the redundant shallow-iteration overhead directly: 94 total nodes without root-move reuse and 84 with it, both over double a single direct depth-4 search's 40 — honest that this board's small, shrinking branching factor never gets the "nearly free" savings the usual geometric-series argument promises for a bigger game.
A fifth Game Trees entry, restating alpha-beta's exact search in negamax's single-function form and adding a cheap null-window "is this better, yes or no" scout before every expensive full-window search, re-searching only when a scout unexpectedly fails high. Checked across three move orderings on the same fixed board as Minimax: ties alpha-beta exactly (29 nodes, 0 re-searches) when the true best move is tried first, but costs more than plain alpha-beta (51 vs. 40, and 60 vs. 49 nodes) under the other two orderings. Pitfalls catches a real, checked failure mode: skipping the re-search step trusts a scout's fail-high bound as if it were exact, which returns the correct move but the wrong value from an empty board (claims a forced win, score 1, instead of the correct draw, score 0).
A fourth answer, orthogonal to the other three: instead of deciding a position's score
differently, this caches a score once fully derived so a different move order reaching the
identical board returns it instantly instead of re-searching. Checked against the same fixed
board as Minimax below — 33 fresh evaluations plus 16 cache hits against plain minimax's 57,
5,478 fresh plus 10,690 hits against 549,946 from an empty board. Pitfalls catches a real,
checked failure mode too: naively caching alpha-beta's own returned values and reusing them
elsewhere in the tree returns the wrong answer (O's score comes back 1 instead of
the correct 0) unless each cached value also records whether it's exact or only a
bound.
A third answer to "what should I play right now," for games with no adversary at all — just plain chance. Minimax and MCTS both assume a real opponent; expectimax replaces the minimizer with a chance node that averages over probability-weighted outcomes. A backward-induction demo for a push-your-luck dice game ("Push to 21") finds the exact stopping point is total 14, not the common "hit until 17" rule of thumb — standing at 16 banks 16 outright, while the naive rule's one more roll averages only 9.5, a real, checked gap confirmed by a 2,000,000-hand simulation.
Same fixed tic-tac-toe fork as the Minimax page below, but this search never gets told the rules beyond legal moves and who won — it runs random playouts and lets UCB1 balance exploring untested moves against exploiting good ones. A step-through of the exact seed shipped shows the visit leader is briefly wrong (cell 4 leads at simulation 20, cell 6 — the real forced win — doesn't take the lead for good until simulation 35), and that visit count and win rate can point at different moves (simulation 33). A 200-seed offline sweep found the most-visited move matches minimax's proven answer in all 200 runs.
The site's first Game Trees entry, and its first adversarial one: the same try-it-then-undo-it shape as N-Queens, Sudoku, Graph Coloring, and Hamiltonian Path/Cycle, but every other move is chosen by an opponent minimizing your score, not by you searching for a fit. Includes a step-through tic-tac-toe visualizer over a real forced-win position — a one-ply "win now or block now" heuristic finds nothing and settles for cell 3 (a draw), while full minimax finds cell 6, a fork forcing a win in exactly three plies — plus a checked alpha-beta toggle proving pruning never changes the answer, only the node count: 57 vs 40 on this board, 549,946 vs 20,866 from an empty board.
An eleventh Network Flow entry, the general method every other max-flow entry on this site specializes: repeatedly find any path from source to sink with spare capacity, push its bottleneck, repeat — correct for any path-choice rule, but with no speed guarantee unless a specific rule is added on top, which is exactly what Edmonds-Karp's breadth-first search adds. A live demo with a switchable path-choice rule proves it directly on an identical four-node network: a rule that prefers a thin "bridge" edge takes 8 augmentations to reach max flow 8, where Edmonds-Karp's shortest-path-first rule reaches the same 8 in 2 — verified against the shipped code via a fake-DOM harness, not just asserted. Closes a forward reference: Edmonds-Karp's own page named "Ford-Fulkerson" repeatedly in unlinked prose since it shipped.
A tenth Network Flow entry, and the first that answers a whole batch of queries instead of one: the
max-flow value between every pair of nodes, not just one fixed source and sink or one
global minimum. Built via Dan Gusfield's 1990 simplification of Gomory and Hu's original 1961
construction — n − 1 max-flow computations, each run against the current node's own
tentative parent in the tree being built (never a fixed root), packing every pairwise answer into a
tree with only n − 1 edges: the smallest weight on the tree path between any two nodes is
their true max flow. Verified exhaustively (1,024 possible 5-vertex unweighted graphs, 10,240 pairs) and
via 5,000 randomized weighted trials (95,883 pairs) against independent brute-force max flow, 0
mismatches both times. A live query tool checks any pair against a real brute-force computation on the
spot. Two toggled variants reproduce real bugs: reparenting with an already-overwritten parent pointer
corrupts one node's weight to 0 (25.6% of pairs wrong across randomized trials; 5 of 15 pairs wrong on
this page's own demo graph), and the tempting-looking "just fix one source" shortcut still finds the
correct global minimum every time but the wrong value for 22.6% of all other pairs (10 of 15 on this
page's own graph).
A ninth Network Flow entry, and the deterministic counterpart to Karger's Algorithm: the same
global minimum cut question, answered with no randomness at all. Each "minimum cut phase" runs a
maximum adjacency search — grow a set one vertex at a time, always taking whichever outside vertex
is most tightly connected to what's grown so far, the same greedy shape
Prim's Algorithm uses for spanning trees — and the cut isolating
the last vertex added is provably the true minimum cut between it and the second-to-last, which is
what lets every phase's finding survive a merge into the next, smaller graph. On the exact same
triangle-bridge-triangle graph Karger's page uses, every run finds the size-1 bridge cut, every
time. A live toggle reproduces a real bug (accumulating weight on merge with = instead
of +=): the demo's own default graph reports a minimum cut of 0 instead of 1, and the
same bug disagreed with a brute-force check on 77.8% of 3,000 randomized weighted graphs.
An eighth Network Flow entry, and the first that isn't about a fixed source and sink at all: the global minimum cut, the fewest edges whose removal disconnects the graph over every possible split, not just one. Randomized and refreshingly simple — repeatedly contract a uniformly random remaining edge until two "super-nodes" are left, and the edges still crossing them are a candidate cut. A single run's real success rate, measured live over 20,000 real trials on the demo's own bridge-and-two-triangles graph, comes in well above the guaranteed 6.7% floor the proof derives — but a single run is still not enough, so the page also measures how fast repeating it and keeping the best amplifies that toward certainty. A from-scratch check of a tempting shortcut (deduping parallel edges after a contraction instead of preserving their multiplicity) dropped the true measured success rate from 37.2% to 23.7% on the exact same graph.
A seventh Network Flow entry, and a faster direct answer to the same question Bipartite Matching already asks: the largest matching in a bipartite graph, no flow network required. Instead of one augmenting path at a time, a single BFS layers every free left node by distance, then one DFS pass peels off a maximal set of node-disjoint shortest augmenting paths at once — a phase. Verified directly against the site's own Bipartite Matching demo graph: phase 1 finds two of its three augmenting paths simultaneously, where Kuhn's algorithm (the augmenting-path method Bipartite Matching's reduction amounts to) needed two separate passes for the same two edges, reaching the true maximum in 2 phases instead of 3 searches.
A sixth Network Flow entry, picked via the staleness tiebreak (an 18-way tie at 5 entries each broken by Network Flow's newest entry, Hungarian Algorithm at 2026-08-06, being decisively older than every other tied category's newest): gives every edge a capacity and a cost, and asks which of the flows achieving the maximum value is cheapest. Reuses Edmonds-Karp's exact residual-graph machine, swapping breadth-first search for Bellman-Ford so the cheapest path wins instead of the shortest one — necessary because a reverse residual edge undoes flow that already cost something, making it genuinely negative-weight. The demo's fifth augmenting path hits that for real, rerouting through a reverse edge at cost −1; a from-scratch cycle-canceling implementation, seeded from an unrelated flow of the same partial value, independently confirms the running cost at every intermediate step is already minimal, not just the final one.
A fifth Network Flow entry, and the first where edges carry a cost instead of just existing or not: the classic assignment problem, cheapest way to match every worker to one job. Closes a forward reference Bipartite Matching left open — max flow can count units but has no notion of one edge being preferable to another. The fix: give every worker and job a "potential," restrict the search to edges where cost equals the sum of their potentials (a tight edge), and run Kuhn's algorithm inside that equality subgraph, raising potentials whenever the search stalls. The demo's third row can't reach a free job through tight edges alone — two separate potential updates and a three-pair reassignment later, it finds the true optimum (15) that greedy, checked directly, misses by settling for 17.
A fourth Network Flow entry, and the first to abandon the augmenting-path family entirely: no global search, ever. Nodes are allowed to hold excess flow temporarily (a preflow, not a flow) and fix it locally — push downhill to a neighbor one height below, or raise their own height when no such neighbor exists — until nothing is left pooled anywhere but the source and sink. Same demo graph as Edmonds-Karp and Dinic's, same final max flow of 15, same minimum cut, reached via 13 pushes and 10 relabels instead of any breadth-first search at all.
A third Network Flow entry, reusing Edmonds-Karp's exact graph for a direct comparison: instead of one breadth-first search per augmenting path, Dinic's builds a level graph once per phase and batches every path that graph supports into a single "blocking flow" before recomputing. Same network, same final max flow of 15, same minimum cut — but 2 BFS phases instead of 3, verified step by step rather than just asserted.
A second Network Flow entry, and the first showing that a problem which doesn't mention capacities, sources, or sinks anywhere in its statement can still be exactly a max-flow problem in disguise: wire a source to every left node and every right node to a sink, all at capacity 1, and Edmonds-Karp unmodified finds the maximum matching as its max flow. The demo's third augmenting path is the payoff — a long path that runs backward through an already-matched edge to un-match it, freeing up a strictly better three-pair matching that greedy, checked directly, gets stuck two short of.
A third answer to "what's best in a weighted graph," after Minimum Spanning Trees and Shortest Paths — not the cheapest tree or the cheapest path, but the most a directed network can carry from a source to a sink at once. Repeatedly finds the shortest augmenting path by breadth-first search and pushes flow equal to its bottleneck, until none remain — at which point the demo reveals the matching minimum cut live, checking the max-flow min-cut theorem rather than just stating it. A checked Pitfall shows why the shortest-path rule matters: an unlucky depth-first path order on a small pathological graph takes 2,000 augmentations to reach the same answer BFS finds in 2.
Fourteenth Number Theory entry, extending the Modular Exponentiation → Fermat-inverse reuse chain one link further: to
compute C(n, k) mod p for a prime p and an n running to hundreds of digits, decompose n
and k into base-p digits and multiply one small per-digit binomial coefficient at a time, each
strictly under p. Three checked pitfalls, all against an independent exact-BigInt ground truth
(100,000 correctness trials, 0 mismatches): the naive whole-number factorial-mod-p route silently
returns exactly 0 for every input with k ≥ p (100% of 30,000 forced trials), wrong against the
true value 27.2% of the time; a composite modulus breaks the per-digit modular inverse the same way
it breaks the Fermat-inverse page on its own (10.9% of 30,000 trials); and a loop-bound bug that only
checks n's remaining digits, not k's, silently misses trailing digits of k when k > n (8.2% of
30,000 trials forcing a true-zero case). Updated choosing-a-number-theory-algorithm.html
(ten of thirteen entries funneled → eleven of fourteen, new section + table row + reuse-chain
extension) and bumped "other twelve Number Theory entries" to "other thirteen" on all ten
pre-existing pages that carry that sentence.
Thirteenth Number Theory entry, and the direct generalization of the twelfth: Karatsuba Multiplication splits each number in two and needs 3 sub-multiplications instead of schoolbook's 4; Toom-Cook (the Toom-3 variant) splits into three parts and needs 5 sub-multiplications instead of schoolbook's 9, via evaluation at five points (0, 1, -1, 2, ∞) and interpolation rather than a direct algebraic trick. Verified exhaustively (184,041 pairs, 0 mismatches) and against 300,000 randomized pairs, plus a separate BigInt sweep to 40 digits. Measured a real 12-to-13-digit crossover against schoolbook multiplication for this reference implementation, and a checked sign-dropping bug at the algorithm's one negative evaluation point (97.8% failure rate across 300,000 trials) — a genuinely new failure mode Karatsuba's own two bugs don't share, since Karatsuba's evaluation points never go negative.
Twelfth Number Theory entry, and the other half of a forward reference Karatsuba Multiplication left open in its own closing paragraph. Where Karatsuba speeds up multiplying two numbers digit by digit, the FFT speeds up convolving two coefficient sequences directly: evaluate both polynomials at the n complex n-th roots of unity (recursively, by splitting coefficients on index parity), multiply the point-values pointwise, interpolate back — O(n log n) instead of schoolbook convolution's O(n²). Verified exhaustively (24,025 small polynomial pairs, 0 mismatches) and against 8,000 randomized trials across every length combination from 1 to 4 coefficients per side. Two checked bugs, both in the inverse transform: skipping the division by n (every coefficient comes out exactly n× too large) and reusing the forward transform's twiddle direction instead of conjugating it (silently returns the correct answer's coefficients in circularly-reversed order, not just scaled — wrong 99.9%+ of the time). A measured crossover against schoolbook multiplication lands between 16 and 32 coefficients per side (272 vs. 256, then 640 vs. 1,024).
Eleventh Number Theory entry, and a different layer from the other ten: instead of a question about the numbers themselves, it speeds up the multiplication every other entry in this category quietly treats as one cheap step. Splits each operand in half and reuses the sum of the halves to get the cross term from three half-size multiplications instead of four, giving O(nlog²3) ≈ O(n1.585) instead of schoolbook's O(n²). Verified against native multiplication across 1,287,000 pairs under 3,000 and 300,000 randomized pairs up to 8 digits, 0 mismatches. Two checked bugs: splitting each operand at its own digit length instead of a length shared by both (10 × 100 gives 100 instead of 1000; 68.7% of 300,000 random pairs disagree), and dropping one of the two subtractions in the middle term (100% of non-trivial cases wrong, nearly 4× too large on the page's own default).
Tenth Number Theory entry, and a companion to Baby-Step Giant-Step that looks alike but isn't: given a prime p and n already known to be a quadratic residue, recover a modular square root r with r² ≡ n (mod p) — in polynomial time, always, unlike recovering a discrete-log exponent. Checks Euler's criterion first, then splits on p mod 4: a direct formula when p ≡ 3, a general loop otherwise. Verified with 8,000 randomized trials plus an exhaustive sweep of every (p, n) pair for every prime p < 2,000 (277,048 pairs, 0 failures), which caught a real bug in this page's own first draft — an exponent that needed to be 2^(M−i−1), written as the bare integer M−i−1 instead, now documented live as the first checked pitfall.
Ninth Number Theory entry, and a mirror image of Modular Exponentiation: given g, h, and p, recover the exponent x with g^x ≡ h (mod p) — the discrete logarithm problem underlying Diffie–Hellman and ElGamal. Meet-in-the-middle: precompute a baby-step table of g^j mod p, then walk giant steps of h·g^(−jm) mod p checking each against it, O(√p) instead of brute force's O(p). Verified against 3,000 randomized trials (0 mismatches) and three brute-force-checked worked cases: a standard solve (x = 6), a case needing the full table where rounding the table size down instead of up silently reports "no solution" on an input that has one (x = 21, a real checked pitfall), and a genuinely unsolvable case (h outside the subgroup g generates) that terminates cleanly instead of hanging.
Eighth Number Theory entry, and the first to solve a different problem than the other seven: given a known-composite n, find an actual factor, not just decide primality. Uses Floyd's tortoise-and-hare cycle detection over the pseudorandom sequence x² + c mod n, exploiting a birthday-paradox collision mod n's unknown smallest prime factor long before the full sequence cycles mod n itself. Verified with a Node stress test (5,000 random composites, 0 mismatches against trial division) and traced concretely: 8051 = 83 × 97 in 3 steps with c = 1, the same n collapsing after 14 steps with c = 5 (a real, checked failure mode requiring a retry with a different constant), and a tiny power of two (n = 4) failing for every c from 0–5, showing why small factors need pulling out first.
Seventh Number Theory entry, the first to solve a system of congruences rather than a
question about one number. Merges congruences two at a time by reusing
Extended Euclidean's Bézout coefficients
directly, generalized past the textbook coprime-only case so it detects a genuinely inconsistent
system (via gcd ∤ difference) instead of silently mishandling it. Verified against brute
force across 20,000 random congruence sets (including ~10,000 correctly-detected inconsistent ones)
and checked for order-independence across 5,000 shuffled-input trials — both against the actual
shipped demo code, not just a scratch reimplementation.
Sixth Number Theory entry, closing Modular
Exponentiation's own forward reference: when the modulus is prime, Fermat's Little Theorem
(ap−1 ≡ 1 mod p) turns straight into ap−2 mod
p being a's inverse — one call to the same modPow routine, no
second algorithm. Checked live against Extended
Euclidean's general-purpose route: they agree on prime moduli (3 mod 7 → 5, 3 mod 11 → 4) but a
composite modulus silently breaks the Fermat route (3 mod 8 gives 1, not the true inverse 3) —
swept across 8,050 coprime pairs on composite moduli 4–200, a 93.4% mismatch rate. Also checked:
the off-by-one p−1 exponent always returns exactly 1 (Fermat's own theorem
guarantees it), and a multiple of p returns 0 instead of correctly reporting no inverse exists.
Fifth Number Theory entry, unpacking the modPow helper
Miller–Rabin already uses internally:
square-and-multiply computes base^exp mod m in O(log exp) multiplications, reducing mod m after every
step so no intermediate number ever exceeds m² no matter how large exp gets. Checked: a live toggle
that scans the exponent's bits most-significant-first instead of least-significant-first silently
computes base raised to the bit-reversed exponent, verified across 13,440 base/exp/mod combinations (0
mismatches against that model, 4,067 divergences from the true answer); the never-reduce-until-the-end
naive approach needs a 188-digit intermediate for 7^222 mod 13 where the real algorithm never exceeds
three digits; a mod-1 edge case where an unreduced starting result is masked by every set bit except
exp = 0.
Fourth Number Theory entry, closing Sieve of Eratosthenes's own forward reference: a different question again — not enumerating every prime up to a bound, but deciding whether one specific, possibly huge, number is prime. Builds on Fermat's Little Theorem, then fixes its blind spot (Carmichael numbers like 561 fool the plain Fermat test for every coprime base) with a square-roots-of-1 argument that only holds mod a prime. Checked: 2047 fools witness 2 (a real strong pseudoprime) but not witness 3; the shipped test matches trial division exactly for every n up to 300,000 against witnesses {2,3,5,7}; an off-by-one loop bound wrongly rejects genuine prime 97 by cutting the one squaring that reaches n−1.
Third Number Theory entry, and a different shape of question from the first two: instead of
relating two given numbers, it finds every prime up to a bound n in one coordinated sweep —
cross out every multiple of each newly confirmed prime, starting at p². A checked off-by-one
bug (p*p < n instead of <=) silently misclassifies perfect squares
of primes (49, 121, 169…) as prime; a separate, honestly modest ~5% operation-count saving
comes from starting each prime's marking at p² instead of 2p.
Second Number Theory entry: the same reduction loop as Euclidean Algorithm, carrying two extra running coefficients so it returns not just gcd(a, b) but integers x, y with a·x + b·y = gcd(a, b) — Bézout's identity, verified across 6,560 integer pairs. When gcd(a, m) = 1, x is (after a sign normalization checked on 39,402 (a, m) pairs) the modular inverse of a mod m, the basis for RSA key generation and division-free modular arithmetic generally.
The site's first entry under a new category — algorithms about the integers themselves,
not arrays, graphs, or strings. Repeatedly replaces the larger of two numbers with the
remainder after dividing by the smaller, since gcd(a, b) = gcd(b, a mod b) exactly. Includes a
step-through demo over the classic (1071, 462) pair and a consecutive-Fibonacci (89, 55) worst
case, checked by brute force over every pair under 100 to actually be the slowest. Pitfalls
catches two real, checked bugs: skipping Math.abs gets the magnitude right but the
sign unpredictably wrong on negative input, and the older repeated-subtraction version needs
999,999 steps where the modulo version needs 2 on the same skewed pair.
The site's eleventh Graph Traversal entry, and the third (after Eulerian Path and 2-SAT) that
isn't a DFS extension at all — no stack, no queue, no visited set. Two pointers walk the same
functional graph (every node has exactly one outgoing edge — a linked list is the classic case)
at different speeds; if there's a cycle, the gap between them shrinks by one every step and must
hit zero within one lap. A second phase — one pointer restarted at the head, both now moving at
equal speed — locates exactly where the cycle begins, using a distance argument that never needs
to know the tail or cycle length. Closes a forward reference from Pollard's Rho, which borrows this exact
mechanism to detect a collision in a pseudorandom sequence without storing it. Verified against a
brute-force hash-set walk across 255 tail/cycle-length combinations (0 mismatches). Two quantified
pitfalls: leaving the hare at double speed in phase 2, instead of slowing it to match the reset
pointer, silently returns the wrong node on 1,326 of 2,000 (66.3%) random trials; checking for the
end of the list only after both of the hare's hops instead of after each one crashes with a
TypeError on every one of six cycle-free lists tested. Updated the guide (ten →
eleven, new "functional graph, no branching" question) and all ten existing siblings' "other nine
→ other ten" cross-link sentence.
The site's tenth Graph Traversal entry, and the first that doesn't start from a graph at all — a boolean formula's two-literal clauses translate into an implication graph, and the actual work is handed entirely to Strongly Connected Components, reused wholesale rather than extended. A formula is unsatisfiable exactly when some variable's true and false literals land in the same strongly connected component (mutually reachable, not just one-way reachable) — the same site-verified Tarjan SCC routine decides it. A 42,000-trial sweep against brute-force truth-table enumeration (up to 20-clause random formulas over 4 variables) found zero mismatches. Three quantified pitfalls: adding only one direction of a clause's two implications wrong on 6.7% of trials; flipping which side of the component-number comparison means "true" — a bug this page's own reference implementation actually shipped on the first attempt — silently wrong on 88.5% of satisfiable trials while still correctly reporting "satisfiable"; testing one-directional reachability instead of requiring a full mutual-reachability cycle over-reports contradictions on 40.2% of trials. Updated the guide (nine → ten, new "boolean formula, not a graph" branch, new table row) and all nine existing siblings' "other eight → other nine" cross-link sentence.
The site's ninth Graph Traversal entry, picked via the staleness tiebreak (13 categories tied
at 8 entries; Graph Traversal was the oldest, last grown at page 207 versus every other tied
category's 217-238). Repeated depth-limited DFS, one deeper limit at a time — the first
iteration to reach the goal at all is provably via the shortest possible path, the same
guarantee BFS makes, recovered at O(d) stack
memory instead of BFS's O(V) frontier. Measured the real cost of that trade on its
own demo maze: 188 total node-visits across all iterations versus BFS's 21 for an identical
11-step answer, an 8.95x overhead from redundant shallow re-exploration. Two checked pitfalls,
both verified against the shipped script, not just described: marking a cell visited for the
whole iteration instead of only while on the current path silently returns a real but
non-shortest path (13 steps instead of 11, using less total work to get it wrong);
checking the depth-limit cutoff before checking for the goal mishandles the exact-boundary case
the same way (12 steps instead of 11). Updated the guide (eight → nine, new memory-constrained
branch off the shortest-path question, new table row) and all eight existing siblings' "other
seven → other eight" cross-link sentence.
The site's eighth Graph Traversal entry, and the second algorithm for the same question Tarjan's Algorithm already answers — no low-link value anywhere, just two full DFS passes: one on the graph as given to record a finish order, one on its transpose (every edge reversed) starting from the last-finished node first. Reuses Tarjan's exact eight-intersection demo graph, and the two algorithms find the same four components in exactly opposite order — Kosaraju's source-to-sink, Tarjan's sink-to-source — confirmed against 5,000 random graphs, not just this one. Two checked Pitfalls on this exact graph: skipping the transpose collapses all four components into one; pushing nodes in discovery order instead of finish order silently merges two of the four into one wrong component while leaving the other two correct.
The site's seventh Graph Traversal entry: two ordinary BFS searches, one from each end,
alternating by expanding whichever frontier is currently smaller and stopping the moment they
meet — same shortest-path guarantee as BFS, but roughly
2·bd/2 cells touched instead of bd. Measured on
this page's own demo maze: 49 cells visited against plain BFS's 67 (1.37x); on a sparse
50,000-node random graph (average degree 5), an average of 53.75x fewer cells across 30 random
reachable pairs, individual runs up to 124x. A random search over 200,000 adversarial graphs
found a real counterexample for the tempting-but-wrong "stop at the first single cell found in
both visited sets" shortcut — shrunk to a minimal 7-node graph where that shortcut returns 4
instead of the true shortest distance of 3 — and the shipped reference implementation (the
correct full-layer, best-of-all-candidates version) was checked clean against 11,708 random
mazes for path length, contiguity, and no wall-crossing.
The site's sixth Graph Traversal entry, picked via the staleness tiebreak (a 14-way tie at 5 entries, broken by Graph Traversal's newest entry being the oldest of all fourteen) and closing Hamiltonian Path / Cycle's own forward reference to the "similarly named" edge-covering problem. Walks an explicit stack instead of recursing, so every dead end just gets popped and spliced into the finished trail rather than aborting the walk. Three checked Pitfalls: a plain greedy walk (no backtracking) gets stuck at 3 of 6 edges even though a circuit exists; even degree at every vertex isn't sufficient without connectivity, shown on two disconnected triangles that each pass the parity test alone; and starting the real algorithm at the wrong vertex for a path (not one of the two odd-degree ones) doesn't fail loudly — it silently returns a trail claiming an edge that isn't in the graph.
The site's fifth Graph Traversal entry, reusing Strongly Connected Components's exact disc/low-link bookkeeping but turned on an undirected graph: instead of closing components off an explicit stack, two inequalities checked the moment each DFS child returns directly flag cut vertices and cut edges — single points of failure whose removal disconnects the graph. Two checked Pitfalls: dropping the root's special-case rule wrongly flags the root itself, and a value-only parent check (correct here, since this graph has none) would misreport a bridge as soon as a parallel edge exists between two vertices.
One more piece of bookkeeping on top of Topological Sort's three-state DFS: track each node's discovery time and low-link value, and the moment they match, everything still sitting on an explicit stack closes into one strongly connected component. The demo walks a one-way street map of 8 intersections, and a checked Pitfall shows two real components silently merging into one wrong component if the "still on the stack" check is dropped.
DFS with one extra idea: push each node onto a stack the moment it finishes, then reverse the whole stack. Built on a course-prerequisite graph — includes a toggle that adds a real requirements cycle and shows the algorithm correctly refusing to produce an order instead of silently returning a wrong one.
Same skeleton as BFS, but swap the queue for a stack and shortest paths stop being guaranteed. Same editable maze as the BFS page — step through and watch it dive down one branch at a time, backing up only when it dead-ends.
Point a queue's FIFO promise at a graph and you get shortest paths for free. Includes an editable maze demo — draw walls, then step through the search watching the queue itself grow and shrink until the shortest path lights up.
The Convex Hull category's eleventh entry, and a fifth "different question" — not a different
input or a skipped step, but a bigger version of the same question: compute the convex hull,
remove it, repeat on whatever's left, until every point has a layer number. Verified against an
independent nesting/coverage check across 500 random trials (17,165 points total, 0 failures) and
the real shipped demo via a fake-DOM harness (22 points, 4 rings of 8/6/5/3, exact match to the
scratch reference). Two verified pitfalls: this category's usual strict collinear-popping mode
doesn't just change a vertex count here, it silently reassigns a boundary point to the wrong layer
(a hand-built counterexample moves point B from layer 1 to a bogus layer 2); and a loop that stops
as soon as fewer than three points remain silently drops the final 1-or-2-point core, measured on
55.2% of 1,000 random trials. Complexity measured rather than assumed: a naive from-scratch resort
each round is genuinely O(n²) worst case (ratio-to-n² converges
to ~0.17 across six doublings on an adversarial nested-triangle input) and roughly
O(n1.6) on random input, since the layer count itself grows like
n0.665 empirically — worse than the naive O(n log n) guess
either way, a gap Chazelle's 1985 algorithm closes but this reference implementation doesn't.
The Convex Hull category's tenth entry, and the most different of the five "different question" entries in this category — it doesn't compute a hull, a diameter, or anything else, it just throws points away. Scans for 8 directional extremes, connects them into a small octagon, and discards every point strictly inside it: none of them can be a hull vertex, since the octagon is itself already contained in the true hull. Verified safe across 500 random trials (24,998 points, 19,097 discarded, zero false discards against a brute-force hull oracle) and measured on this page's own 22-point demo set — 8 survivors with the octagon vs. 13 with the classical 4-point quadrilateral, a live toggle. Two verified pitfalls: a strict-vs-inclusive boundary test silently drops a genuine boundary point (constructed collinear counterexample, cross product exactly 0); connecting the 8 extremes in the wrong order makes the test polygon self-intersect, silently pruning 0% of 15,087 points across 300 trials instead of crashing or answering wrong.
The Convex Hull category's ninth entry, and a third (alongside Rotating Calipers and Convex
Hull Trick) way of assuming away the sort every other entry has to pay for — not by skipping the
hull question, but by assuming the input already arrives as a simple polygon's own boundary, in
order. A single pass with a deque, each new vertex tested against only the two edges at the
deque's current ends, gets a genuine O(n) instead of any entry's O(n log n)
floor. Verified against an independent brute-force hull across 19,755 randomly generated simple
polygons (0 mismatches; a separate check confirmed 245 generated candidates were rejected for
genuinely self-intersecting first, not silently included as false passes), then the shipped demo
— ten vertices tracing a five-pointed star — via a fake-DOM harness driving all 9 real Step
clicks, landing on the same 5-vertex hull as the reference implementation. A verified pitfall:
feeding the identical ten points in a shuffled order instead of the star's own boundary order
produces a confidently wrong 4-vertex hull, missing a real vertex outright, with no error raised
anywhere. A second, caught pre-ship: an early version of the demo's own display logic marked a
point "not on the hull" the instant either of its two duplicate deque copies got popped, without
checking whether the other copy was still sitting at the deque's far end — flagged three genuine
hull vertices as simultaneously on and off the hull at once, fixed by deriving "not on hull" from
the deque's actual current contents instead of watching individual pop calls.
The Convex Hull category's eighth entry, and the second (alongside Rotating Calipers) to
assume no point set at all — given many linear functions, which is the maximum at a query
x? Keeps only the lines that are ever the best answer somewhere in a deque, popping
any line proven unnecessary the instant a new one arrives, then answers a non-decreasing stream
of queries with a single pointer that only ever advances. Framed as five royalty contracts
($m per copy plus a signing bonus $b): one contract is popped the
moment a better one is inserted, without a single sales projection run, and the surviving four
answer five queries with only 3 total pointer moves. A verified pitfall: running the identical
code on the same five contracts in their original, not royalty-sorted order doesn't crash — it
silently answers 4 of 5 queries wrong, off by as much as $16,000, confirmed against a 2,000-trial
stress harness (0 mismatches sorted, 1,794/2,000 failures shuffled).
The Convex Hull category's seventh entry, and the first to assume the hull already exists
rather than build one — given a convex polygon, find its diameter (farthest pair of vertices)
by walking two pointers around the boundary in O(n) instead of checking every pair
in O(n²). The vertex farthest from a given edge only ever advances forward as the
edge itself advances, never backward, so the search for one edge's farthest vertex can pick up
exactly where the previous edge's search left off. Verified against a brute-force all-pairs
oracle across 20,000 random convex polygons (sizes 3–32) plus explicit squares, rectangles, and
regular polygons up to 20 sides — zero mismatches, including the tied-antipodal-vertex case
parallel edges create. A checked pitfall: the bounding box's diagonal is not the polygon's
diameter — a 45°-rotated square's bounding-box diagonal measures 282.84 against an
actual vertex-to-vertex diameter of 200, since the box's own corners sit in empty
space no vertex touches.
The Convex Hull category's sixth entry, and the third (alongside Graham Scan and Monotone
Chain) to reach a guaranteed O(n log n) — by merging rather than sorting-and-
sweeping or wrapping. Every point starts as its own trivial one-point hull; neighboring hulls
merge upward in pairs by finding their shared upper and lower tangent lines, walking a pointer
around each hull at most O(|L| + |R|) steps total, until one hull remains for the
whole input. Verified against a brute-force oracle across more than 20,000 random trials
(sizes 1 through 40 per side, many deliberately collinear-heavy) with zero mismatches, plus a
genuine bug caught mid-build: an unrefined tangent search accepted a collinear point strictly
between the true endpoints as if it were the tangent itself, silently dropping a real corner —
fixed by walking out to the farthest collinear point before accepting a candidate. A second
checked pitfall: the naive all-pairs way to find a tangent line is O(|L| · |R|),
which breaks the algorithm's own O(n log n) headline at the top-level merge —
measured at roughly 250 million point-tests for a single merge at n = 1,000
against the pointer walk's 2,000.
The Convex Hull category's fifth entry, and the second (alongside Graham Scan) to reach a
guaranteed O(n log n) — by a genuinely different sort. Instead of picking a pivot
and sorting by angle, sort every point by plain (x, y) coordinate once, then sweep
that flat order twice — left to right for a "lower" chain, right to left for an "upper" one —
with the same cross-product push/pop test Graham Scan uses for its single sweep. Verified
directly against this page's own point set: the lower-hull pass lands on
I → H → G → F → E, which — despite the name — sits near the top of the
canvas, not the bottom, the same y-down coordinate flip Graham Scan's own page already found,
just showing up as a flipped label instead of a flipped turn direction this time. A concrete
four-point counterexample (a vertical segment plus one point off to the side, tested in three
input orders) confirms skipping the coordinate-tie secondary sort isn't cosmetic: one of the
three orderings without it drops a genuine hull corner and keeps an interior boundary point
instead, the same order-dependent-bug shape as Jarvis March's own tiebreak pitfall.
The Convex Hull category's fourth entry, and unlike the other three, not a fourth way to solve
the problem from scratch but a way of combining two of them: Graham Scan on small groups, a
Jarvis-March-style wrap across just the resulting mini-hulls, and a group size that starts small
and doubles whenever a wrap attempt fails to close in time. A live checkbox picks the group size
directly — a guess of m = 4 turns out too small for the demo's real 7-vertex hull and
aborts partway through with a message explaining why; m = 8 closes on the first
attempt. Verified directly, not just asserted: a 200-trial random stress test against an
independent brute-force hull found zero mismatches, and the reference implementation's full
guess-and-double loop needs exactly three rounds (m = 2, 4, 8) on this page's own
point set, matching ⌈log₂ h⌉ rather than a count tied to how bad the first guess
was.
The Convex Hull category's third entry, and a genuinely different shape from both Graham
Scan's sort-then-sweep and Jarvis March's one-vertex-at-a-time wrap: divide-and-conquer, the
same strategy as its sorting namesake. Fix the two most extreme points in x, then recursively
find whichever remaining point is farthest from the current baseline edge — a guaranteed hull
vertex that splits the rest into two smaller sub-problems and throws away everything now
provably interior. Verified the worst case is real, not just textbook: a steeply bowing,
unevenly spaced point set forces the recursion into one unbalanced split after another, and its
op-count-to-n² ratio converges instead of shrinking as n grows (0.49 →
0.31 → 0.27 → 0.24), the signature of true O(n²) — a genuinely mixed random point
cloud measured the same way shrinks toward zero instead (0.25 → 0.07 → 0.02 → 0.005), the
average-case O(n log n) shape. A live checkbox reproduces Graham Scan's own
strict/loose collinear-point choice from inside completely different code, landing on the exact
same 8- vs 9-vertex hull on the exact same point set.
The Convex Hull category's second entry: gift wrapping instead of Graham Scan's sort-then-
sweep, building the hull one vertex at a time by repeatedly finding whichever remaining point
keeps every other point on one consistent side. Measured, not just asserted, that its
O(nh) cost is real: point-comparisons scaled roughly quadratically on points
arranged so every one sits on the hull, but roughly linearly when the hull stayed a fixed
3-vertex triangle regardless of how many extra points were packed inside it. Reused Graham
Scan's own offline collinear counterexample to show a sharper pitfall than Graham Scan's: skip
the exact-tie tiebreak and the algorithm's output silently depends on input order — same points,
same true hull, a 4-vertex answer in one array order and a wrong 6-vertex answer in another.
The site's first entry in a new Convex Hull category, and its first from computational
geometry — comparing directions instead of values. Fix one point guaranteed to be on the hull
(lowest, ties broken leftmost), sort every other point by the angle it makes from there, then
walk that order with a stack that pops whenever the last three points on it stop turning the
same way. A live checkbox switches whether a dead-straight (collinear) triple counts as "wrong
way": on the demo's own point set, the strict rule pops a point sitting exactly on the hull's
bottom edge (cross(C, B, A) = 0), landing on an 8-vertex hull, while the looser
rule keeps it for a 9-vertex hull that accounts for every boundary point — both checked against
an independent brute-force hull. A second, offline-verified pitfall shows what happens without
the angle-tie sort's secondary distance key: not just a different shape, but a "hull" that
fails a direct containment check against one of its own input points.
The eleventh Geometry entry, and the first built to be self-intersecting on purpose — a square with a smaller square nested inside it, both wound the same direction and stitched into one boundary by a zero-width seam, so the inner square is genuinely enclosed twice. Point in Polygon's ray-casting parity and this page's signed running total agree everywhere the boundary is simple and provably diverge once it isn't: at the doubly-wound center, ray casting sees an even crossing count (outside) while the winding number sums to 2 (nonzero, correctly inside). A 53,671-point grid sweep confirmed the disagreement is confined to exactly the inner square's own area (3,600 points, an exact match, not an approximation) and agreement elsewhere (13,300 more, exactly the ring's area). A verified pitfall: dropping the "which side" check that limits a crossing to the point's own ray makes the tally depend only on the query's height, never its position sideways — 18.7% of a wide sampled grid comes out wrong.
The tenth Geometry entry, closing a forward reference both
Point in Polygon and
Slab Decomposition had left open since their own
sessions — deferred for 18 sessions afterward as too large a risk to attempt without dedicating a
full session to it, per the same standing caution that had earlier deferred
Fortune's Algorithm. Builds a search DAG by
inserting a polygon's edges one at a time in random order, splitting whichever trapezoids each
edge crosses, for O(log n) expected point-location queries — the fix for
Slab Decomposition's own worst-case
O(n²) preprocessing. One deliberate, honestly-flagged simplification: this build
finds each new edge's crossed trapezoids by re-using the same DAG search that answers queries,
instead of the textbook's separate trapezoid-to-trapezoid neighbor pointers — an early
neighbor-pointer version had a real silent bug, and dropping that whole mechanism in favor of one
unified search removed the bug class instead of just the bug. The DAG-only approach found a
different, louder bug of its own: an x-node tie-break using full lexicographic order instead of
comparing x alone turned the crossed-trapezoid walk into an infinite loop, crashing the stress
harness on 6 of the first 7 random polygons tried. Fixed and reverified clean across five RNG
seeds (roughly 14,500 random simple polygons, 436,000 point-location queries) against an
independently-built oracle — brute-force slab decomposition merged into trapezoids, cross-checked
a third way against plain crossing-number point-in-polygon — plus a separate run up to 34-vertex
polygons, 0 mismatches throughout.
The ninth Geometry entry, and a direct follow-up to Voronoi Diagram, which named this page in its own
Complexity section and left it unbuilt. Builds the diagram directly by sweeping a line down the
plane and maintaining a "beach line" of parabolic arcs whose breakpoints trace the actual Voronoi
edges live, without ever building the dual Delaunay mesh first. A step-through demo over the same
8 points as the Delaunay/Voronoi pages fires every event kind (site arrivals, real circle events,
and stale circle events skipped after a neighbor changed), finding the identical 8-vertex set —
including the known off-canvas (−70, 50) vertex — as the half-plane-clipping Voronoi
page's own independent dual-graph check. Two verified pitfalls found while building it: sites that
tie exactly on the sweep's y-coordinate need a direct two-way insert instead of the usual
three-way arc split, or a spurious zero-width arc gets wedged in permanently (149 of 6,300 stress
trials wrong before the fix, concentrated entirely in tied/collinear configurations, 0 after); and
splitting an arc must hand its two outer edges to the new copies, not just wire up the two
new inner ones, or an edge gets silently orphaned mid-trace and rendered straight through a third
site's territory (55,780 of 292,560 sampled boundary points — 19% — wrong before the fix, 0
after).
The eighth Geometry entry, and a direct follow-up to Delaunay Triangulation, which named this page in its own Complexity section and left it unbuilt. Partitions the plane into one nearest-site region per point by intersecting half-planes (Sutherland-Hodgman clipping against every other site's perpendicular bisector), built independently of the Delaunay mesh so the demo's live duality check — click a point, confirm its cell's vertices are exactly its incident Delaunay triangles' circumcenters — is a genuine cross-check, not reused structure. One verified pitfall: a site interior to the point set's convex hull still doesn't guarantee its true cell fits inside a fixed drawing window — one of the demo's own 8 points has a circumcenter that lands off-canvas despite being interior, and across 5,000 random 8-point layouts (13,041 interior-site instances), 68.7% hit the same issue.
The seventh Geometry entry, and the first that starts from a bare point set instead of a boundary already given. Builds the triangulation point-by-point (Bowyer-Watson): insert a point, remove every triangle whose circumcircle now contains it, and fan new triangles from it across the resulting hole. A step-through demo over 8 points shows how long the algorithm runs against an invisible bootstrap triangle before any real output triangle appears at all. One verified pitfall, found the same way Polygon Triangulation verifies its own tiling: an ordinary-looking, plenty-large bounding triangle (20× the point set's own span) silently dropped a real 205-square-unit triangle from a 9-point configuration — every shipped triangle individually still passed the empty-circumcircle test, and the hole reproduced on all 1,000 random insertion-order shuffles tried, ruling out bad luck. A 1,000,000× margin fixed it, verified clean across 10,000 further random point sets (372,307 triangles checked).
The sixth Geometry entry, and the first that decomposes a whole polygon into many pieces
instead of answering one query about it. Repeatedly clips off "ears" — convex vertices with no
other vertex inside their candidate triangle — leaving n − 2 triangles that exactly
tile the original simple polygon, reusing Point in
Polygon's own seven-vertex arrow. A step-through demo shows two genuine status flips on that
exact polygon: two reflex vertices become ears once clipping changes their neighbors, and one
convex-but-blocked vertex becomes an ear the moment its blocker turns into its own direct
neighbor instead of a third-party point. Two verified pitfalls: skipping the "anything else
inside my triangle" check produces the right triangle count but a wrong tiling (57,000
vs. an overlapping 67,000 on this page's own polygon); skipping the neighbor-recheck after each
clip looks like it works on this one small example but gets stuck or produces a wrong
triangulation on 849 of 3,000 random simple polygons tested — the other 2,151 only happen to come
out right.
The fifth Geometry entry, and the first that preprocesses a polygon once to answer many later
queries cheaply instead of solving one query from scratch — closes the forward reference in
Point in Polygon's own Complexity section. Slices
the plane into vertical slabs at each vertex's x-coordinate; since no polygon vertex
sits inside an open slab, the edges crossing it and their top-to-bottom order never change within
it, so locating a query point becomes two binary searches (which slab, then where among that
slab's edges) instead of one linear scan of every edge. Reuses Point in Polygon's own seven-vertex
arrow and six query points directly, confirmed to agree with its ray casting on every one. Two
verified pitfalls: a left-open slab-boundary convention silently misclassifies every point on the
polygon's leftmost edge (373 of 1,500 targeted trials disagree with the shipped right-open rule),
and an adversarial "staggered teeth" polygon shows genuine O(n²) preprocessing growth
(1,122 total slab/edge pairs at n=132, 4,290 at n=260) — both still agreeing with ray casting on
every point of 50,000 random trials, so the blowup is in preprocessing cost, not correctness.
The fourth Geometry entry, and the first that processes a whole set of segments rather than
one pair or one polygon — finds every intersecting pair among n segments by
sweeping a vertical line left to right and only ever testing pairs once they become adjacent in
a top-to-bottom "status structure," instead of brute-forcing all C(n,2) pairs.
Closes the forward reference named in Line
Segment Intersection's own Complexity section. A 5-segment, 6-crossing step-through demo
shows the mechanism honestly: this dense example doesn't beat brute force's pair-test count
outright (the win is asymptotic, not universal), which the page states directly rather than
implying otherwise. Two verified pitfalls: skipping the re-check on a segment's removal misses
a real crossing (a concrete 3-segment example, checked against brute force), and checking a
new/removed segment against every active segment instead of just its neighbors stays correct
but measurably destroys the efficiency win (136 vs. 6,338 pair-tests at n=80, worse than a flat
3,160-pair brute-force pass).
The third Geometry entry, and the first that works on a concave shape — unlike every
Convex Hull entry, the polygon here can cut back into itself. Ray casting (crossing number)
settles it: cast a ray from the query point and count boundary crossings, odd means inside.
A seven-vertex arrow with two genuine concave notches is the demo shape; the "upper notch"
preset sits inside the arrow head's bounding box and on the interior side of the wing's one
slanted edge, yet the real crossing count is zero — outside — confirmed against a
from-scratch winding-number implementation (a genuinely different algorithm) across 50,000
random trials with zero mismatches. A second pitfall found the same way "why don't I trust a
stress test alone" caught session 189's: relaxing the crossing test's strict >
to >= on both sides passes 200,000 random trials clean, then visibly diverges
from the canonical version the moment a query point is placed exactly on a vertex-height
edge — not a hypothetical, a checked, reproducible flip.
The site's first entry with O(1) as its actual top-line complexity — everything
else in Geometry and Convex Hull processes a whole point set, this decides a single pair of
segments in a fixed number of steps. Reuses Convex Hull's own cross-product/orientation
primitive for a different job: two segments cross exactly when each one's endpoints are turned
opposite ways by the other's line. A six-case interactive demo covers the general rule plus
every collinear special case it can't resolve alone — verified against an independently
implemented parametric line-intersection solver across 300,000 random trials (small integer
coordinates deliberately forcing frequent collinear/touching cases) with zero mismatches. One
real bug caught pre-ship: an early draft's "shared endpoint" demo case turned out to already be
solvable by the general rule alone (a corner touch between non-collinear segments always is,
confirmed by re-deriving why), so it was replaced with a genuinely collinear touching-point case
before any claim about it was published.
The site's first entry in a new Geometry category — a genuinely different question from
Convex Hull's "what's the boundary": given a set of points, which two are nearest each other?
Sort by x, split in half, solve each half recursively, then handle the one
non-obvious case: the true closest pair can straddle the dividing line. Only points within the
best distance found so far need checking against the line, sorted by y and bounded
by the same distance — no re-scan of every cross-half pair. Verified against a brute-force
oracle across 20,000 random trials (small coordinate ranges deliberately forcing frequent
duplicate/tied points) with zero mismatches. A concrete pitfall confirmed directly on the demo's
own 12-point set: skipping the strip check entirely returns E-F (d=94.02)
instead of the true closest pair, F-G (d=10.00), which straddles the final
split — the wrong answer, not a crash, which is exactly why the strip step isn't optional.
Tenth Disjoint Set entry, a fifth application built on top of Union-Find — but the only one that never answers a question afterward at all. Lay a wall between every pair of adjacent rooms in a grid, shuffle the walls into random order, and knock one down exactly when Union-Find says the two rooms it separates are still unconnected — the identical cycle check Kruskal's algorithm runs before accepting an MST edge, just with a random shuffle standing in for sorted weight, since a maze has nothing to minimize. Interactive 6×6-room demo colors each Union-Find group live as walls come down, converging to one color once the maze is finished. Verified: 5,000 simulated trials always produce a valid spanning tree (connected, zero cycles); a fake-DOM harness confirms the real shipped script always removes exactly 35 of 60 candidate walls and leaves the other 25 standing, over 200 fresh randomized runs. Two pitfalls: skipping the cycle check removes all 60 walls (0 standing) instead of 35; keeping the check but skipping the shuffle still yields a valid spanning tree but a degenerate one — 4 branch points and 6 dead ends in one raster-order run, against an average of 8.39 branch points and 11.40 dead ends across 2,000 shuffled runs of the same grid. No new CSS — reuses .bfs-grid/.bfs-cell (a doubled grid: even/even cells are rooms, one-odd-coordinate cells are candidate walls, odd/odd cells are permanent corner posts) and the .cg0-.cg3 group-coloring classes Chan's Algorithm already established (reusing Graph Coloring's own WCAG-checked colors).
Ninth Disjoint Set entry, and the first one that isn't a variant of or built on Union-Find at
all — the literal opposite primitive: start with every element in one group, and repeatedly
split it by a set S instead of ever merging groups together. The building block
behind Hopcroft's DFA-minimization algorithm and Lex-BFS chordal-graph recognition, run live
against a real six-state DFA (converges to its true minimal classes, {A},
{B}, {C}, {D, E, F}, in exactly three verified splits) and
cross-checked against an offline reference implementation, plus 2,000 randomized-click trials
against a fake-DOM harness with zero exceptions and zero partition-invariant failures. Two
measured pitfalls: skipping the "whole class already inside S" check spuriously splits 37.3% of
random (partition, splitter) pairs; scanning every element instead of only S still
produces the right answer but touches 200,000× more elements on a million-element, five-element-
splitter example. No new CSS — reuses .cells/.cell (.cell.range
for "toggled into the splitter," .cell.sorted-half for the one accepting state) inside
a new, minimal .pr-block wrapper.
Eighth Disjoint Set entry, closing a forward reference
Union-Find with Rollback's own page and the Union-Find
guide had both named but never linked. Recurses a segment tree over time itself instead of over array
indices: decompose each edge's active [start,end) window onto the tree nodes that exactly cover
it, union on the way in, undo — via Rollback Union-Find's own O(1) undo — on the way out, and a
whole batch of connectivity queries gets answered in one DFS. Verified against an independent brute-force
recheck (fresh Union-Find rebuilt per instant) built into the page itself; skipping the undo step entirely
was checked directly too — all 8 demo queries report true, including the 3 whose correct answer
is false. No new CSS — reuses .bst-wrap/.bst-canvas/.bst-node (segment-tree.html's own tree
layout) and .uf-canvas/.uf-node (the Union-Find family's own graph layout) side by side.
Seventh Disjoint Set entry, a third application built on Union-Find rather than a fourth extension of it: replay Kruskal's own sorted-edge merges as a 2n-1-node binary tree instead of a plain parent array, and any pair's minimum-bottleneck-path answer collapses to one lowest-common- ancestor lookup — the tree's own heap order bakes the max-fold in at build time. Verified against an independent brute-force minimax check (170,332 queries across 20,000 random graphs, zero mismatches); a broken variant that skips repointing the merged component's "top" pointer fails 16,110 of 17,072. Re-verified the real shipped step-through and query controls via a fake-DOM harness.
Sixth Disjoint Set entry, and like Offline LCA, not a variant of find/union itself: a rule for merging whatever data rides along with each set. Always copy the smaller side's data into the larger and every element moves at most O(log n) times in total, across any sequence of unions — drop that one size check and the same sequence can cost O(n²) instead. Interactive demo steps through two fixed union sequences under either rule, live move counters; Why It Works section proves the O(n log n) bound with the doubling argument and backs it with measured totals (7 vs. 28 at n=8) plus a 2,000-trial random-sequence stress test confirming the bound never breaks.
Fifth Disjoint Set entry, and the first one that isn't a variant of the structure itself: one DFS pass over a fixed tree, unioning each node into its parent's set on the way back up, answers a whole batch of lowest-common-ancestor queries using nothing but plain union-by-rank-with-compression. Verified on a fixed 8-node tree and six queries (checked against a brute-force ancestor-chain walk, and separately against 5,000 random (tree, query-batch) trials — zero mismatches), plus a 2,000-node stress test citing real counted operations (1,999 unions, exactly n − 1; 20,511 total find calls). Live checkbox toggles the one-line ancestor-pointer update after each union: off, three of the six queries — each correctly 1 — wrongly report 2 instead, verified against the real shipped script through a fake-DOM harness, not just reasoned about. No new CSS — reuses .topo-wrap/.topo-node/ .topo-edge from Graph Coloring/Hamiltonian Path's demos and .stat-table from Extended Euclidean Algorithm.
Answers a different question than Rollback Union-Find's single-step undo: "were x and y connected as of version v," for any past v, in any order, without mutating or rewinding anything — every version stays queryable forever. Interactive demo with a clickable version strip that jumps the graph, set chips, and Find results to any past state live; Complexity section proves the persistence bookkeeping costs O(1) extra space per union rather than the O(log n)-per-version blowup a general persistent structure pays.
Drops path compression to make every union exactly reversible: a history stack records the single parent pointer (and, at most, one rank) each union changes, so the most recent merge can be undone in constant time — the building block behind offline dynamic connectivity. Interactive demo with a live union/undo history stack; Pitfalls section adds compression back into a real variant and shows the exact wrong connectivity results it produces after an undo.
Extends Union-Find so every union also carries a known numeric offset between two elements, and a new constraint that contradicts what's already implied gets caught instead of silently applied. Interactive demo over the same 8 elements, with editable union weights and live contradiction detection; Pitfalls section runs a real broken variant that forgets to update the offset during path compression, showing the exact wrong number it produces.
Track a partition of elements into groups and answer "same group?" / "merge these two groups" in near-constant time — union by rank keeps the underlying trees shallow, path compression flattens them further on every lookup. Includes an interactive find/union demo over 8 elements showing the parent pointers, the compression happening live, and the actual partition into sets.
The fourth collision-resolution strategy the site covers for the same put/get/delete
contract, and the first to get a hard worst-case bound on get without a second
table: every key is guaranteed to live within a fixed neighborhood of its own home slot, and a
per-home hop-info bitmap tells get exactly which of that neighborhood's slots to
check — bounded, not average. The trick moves entirely into put: an insert that
lands too far from home repeatedly hops the empty slot backward through legal displacements
until it's back in reach. Three checked pitfalls: skipping the hop-back step leaves a key
physically present but permanently unreachable to a correct lookup; dropping a
+ size correction on a wraparound subtraction turns JavaScript's negative-modulo
behavior into spurious, unnecessary resizes (8 slots to 16 for the same five keys the correct
version handles with no resize at all); and a full neighborhood of same-home keys can force a
resize well below the usual 0.75 load factor, which is correct behavior, not a bug.
Linear Probing's own forward reference, closed: instead of a fixed one-slot step, each key gets its own stride from a second hash function, spreading collisions instead of merging them into one run. The interactive demo forces a broken step two different ways — one that returns zero and never moves, one that's even and only ever reaches half the table — both reporting "table full" on a mostly-empty table until a one-line fix (forcing the step odd) closes both gaps at once.
The plain open-addressing baseline this site's Robin Hood Hashing and Cuckoo Hashing pages both name and compare against but never build: one table, one hash function, no eviction rule — just walk forward to the next slot. The interactive demo shows a naive null-delete stranding two still-present keys behind an empty slot, then a from-scratch "tombstone-fill" run where an insert that won't reuse a dead slot reports "table full" on a table with zero live entries.
Every other Hash-Based entry grows by a full rehash sooner or later. Extendible hashing keeps a small directory of pointers to buckets instead of one big array: a bucket that overflows splits on its own, doubling the directory only when that one bucket's own depth has already caught up to the table's — every other bucket, and most directory pointers, untouched. The interactive demo doubles the directory from 1 slot to 8 over nine words, then demonstrates the one case splitting can never fix: four real strings that hash identically, driving six consecutive doublings before the demo's own safety cap gives up.
Every other Hash-Based entry assumes the key set keeps changing; perfect hashing assumes
the opposite — the whole set is known before the table is ever built, so a two-level scheme
(hash into buckets, then build a small collision-free private table per bucket) can guarantee
O(1) worst-case lookups, not just average. The interactive build+lookup demo
shows a degenerate hash collapsing all keys into one bucket (10× the space of 10 keys) when
the balance check is skipped, and a measured jump from ~1.2 to ~7+ average retries when a
bucket's private table shrinks from m² to m slots.
Open addressing like cuckoo hashing, but one table and one hash function: an inserting key that's traveled further from its own home than the resident it collides with steals that resident's slot, keeping every key's probe distance tightly clustered instead of letting one unlucky key's chain run long. The interactive demo inserts the same six keys with the rule on and off — same total probe count either way, but the worst single key's probe length drops from 5 to 1.
Every key gets exactly two possible homes — one slot in each of two separate tables —
so get only ever checks two fixed slots, a genuine worst-case guarantee the
site's chaining hash table below can't offer. The interactive demo ships a real
displacement cascade that runs into an unresolvable cycle and forces a live rehash, not a
staged one.
The naive hash(key) % N sharding scheme remaps nearly every key when a
server joins or leaves. Placing servers and keys on the same fixed ring instead means
only the keys next to the changed server move — the interactive demo measures it directly:
1 of 8 keys move under consistent hashing versus 6 of 8 under naive mod-N, for the same
add or remove.
Trade certainty for space: a fixed bit array and k hash functions answer "have I seen this?" without storing a single key. Can never wrongly say no, but can wrongly say yes — the interactive demo ships a real false positive alongside a real true negative, not staged ones.
Turn a key into a number, use that number as a direct index into an array of buckets — no comparing required to find the right neighborhood, only within it. Includes an interactive put/get/delete demo (preloaded with a three-way collision) showing the hash computed and which bucket's chain it lands in.
A fixed-size cache that evicts whatever's gone longest untouched. Pairs a hash map (O(1) lookup by key) with a doubly linked list (O(1) reorder-to-front) so both halves of the job stay O(1) together, even though neither structure gets you there alone. Includes an interactive get/put demo showing the chain and the map staying in sync.
Same node shape as Segment Tree, but every node keeps its whole range sorted instead of one combined value — answering "how many elements ≤ x lie in [l,r]" via one binary search per canonical node, the plain-arrays alternative to Wavelet Tree's bit-vector mechanism, at the cost of O(n log n) space and no updates once built. Verified against a brute-force scan over 200,000 randomized trials (0 mismatches), then re-verified the shipped demo's own script the same way (432 combinations of range and threshold, 0 mismatches). Two checked pitfalls: a strict-less-than binary search that silently undercounts whenever a value ties the threshold, wrong 32.9% of the time; and an off-by-one on the out-of-range test that drops a real boundary element whenever a query range lines up with a tree node's own boundary, wrong 45.4% of the time — worse, since that alignment is common, not rare.
The hash-table-based counterpart to Van Emde Boas Tree: same three questions, same O(log log U) query time, but a hash table per bit-level instead of a preallocated recursive skeleton, found via a binary search over trie levels rather than one guaranteed recursive call per level. Verified across three universe sizes (0 mismatches over 1,984,000 point-checks), then re-verified via a fake-DOM harness against the real shipped demo (96 query checks, 0 mismatches). Caught a real subtlety by instrumenting the reference code rather than assuming symmetry with vEB: insert is O(log U), not O(log log U) — every insert touches exactly w+1 hash-table levels (confirmed on 110 randomized inserts across three universe sizes), since there's no empty-cluster shortcut to skip a level the way vEB's recursion has. Two checked pitfalls: skipping the ancestor descendant-pointer update during insert leaves membership 100% correct while successor/ predecessor go wrong on 23.9%-35.5% of queries; linear-scanning levels instead of binary searching them stays fully correct but needs 32 hash-table checks where binary search needs 6, on a constructed worst case.
The double-ended answer to Binary Heap's single
extreme: levels alternate between guaranteeing a minimum and guaranteeing a maximum against
every descendant, not just children, so both extremes come out in O(1) and both deletions stay
O(log n) from one array, no second unsynchronized heap needed. Verified against a naive
multiset reference across 20,000 randomized interleaved insert/delete-min/delete-max trials (0
mismatches) plus a full two-directions drain-sort check (3,000 trials, 0 mismatches), then
re-verified the exact shipped demo code the same way. Three measured pitfalls: comparing
against the parent instead of the grandparent while trickling up breaks the invariant 99.6% of
the time; skipping the grandchild's-own-parent recheck while trickling down leaves a silent
violation 10.8% of the time; a naive findMax that skips the size-1/size-2 special
cases is wrong 100% of the time at exactly those two sizes.
Closes a forward reference from Convex Hull Trick: the same "which line wins at query x" question, answered by a segment tree over the x-axis instead of a deque, with no ordering requirement on inserts or queries at all. Verified two ways: a naive swap-only implementation that never pushes a midpoint's loser further down answers wrong on 1,079 of 2,000 randomized trials (2,176 of 16,000 queries), and querying outside the tree's fixed built domain comes back wrong on 6,401 of 20,000 trials (32.0%) versus 0 of 160,000 for any in-domain query — then re-verified the shipped step-through demo itself via a fake-DOM harness against an independent brute-force max, 0 mismatches across all 8 scrambled queries.
Every other entry in this category speeds up queries against one changing array. Fractional
cascading speeds up the same query repeated across k separate sorted catalogs:
binary search for real exactly once, in an augmented top list built by merging each catalog with every
other element promoted up from the one below it, then follow a down-pointer and check at most two
neighbors per remaining catalog — O(1) a level instead of O(log n). Verified exhaustively (5,796 ways to
split 8 distinct values across 3 non-empty sorted catalogs, 63,756 checks, 0 mismatches) and via 300,000
randomized checks against independent per-catalog binary search, then re-verified the shipped
generator-based demo via a fake-DOM harness across 141 query values, 0 mismatches.
Every other tree-shaped structure in this category splits an array by position. A wavelet
tree splits by value instead: route each element left or right by whether it's in the
lower or upper half of the current alphabet range, repeat recursively, and answer access/rank/
select in O(log σ) — the alphabet size, not the sequence length. Verified two ways
from scratch: exhaustively (all 16 length-4 sequences over a 2-symbol alphabet, 240 checks, 0
mismatches) and 5,000 randomized trials (156,634 checks, 0 mismatches), then re-verified via a
fake-DOM harness cross-checking all 136 valid access/rank/select queries on the real shipped
demo's own 12-symbol example against a plain-array reference — 0 mismatches.
Every other ordered-set structure on this site measures its cost against n,
the number of elements stored. A Van Emde Boas tree measures it against U, the
size of a fixed universe of integers the values must come from, and gets member/insert/
successor/predecessor down to O(log log U) — for a billion-integer universe,
about 5 steps instead of 30. The trick verified from scratch (exhaustively, all 65,536
possible subsets of the demo's 16-value universe): every insert makes exactly one
recursive call, never two, because a structure's own min is never duplicated into its
children — confirmed by instrumenting the real code across 40,000 calls, 0 exceptions.
Every other entry here answers range queries online, one at a time, as they arrive. Mo's
Algorithm is for a fixed batch of queries known in advance: sort them by block of L,
then by R, and a single sliding window can walk from query to query adding or
removing one array element at a time — no associative combine needed, which is what makes
"count distinct values in a range" tractable at all despite having no efficient merge. A live
toggle on the shipped demo proves the sort isn't cosmetic: the exact same four queries cost 17
pointer moves sorted versus 42 unsorted on this page's own 12-element example, and 13-19× more
at a few thousand elements in a from-scratch randomized check.
A segment tree gets range-minimum query and point update to O(log n) with an
actual tree. Sqrt decomposition settles for O(√n) instead, in exchange for no
tree at all — one flat array chopped into blocks of size √n, each holding its own
precomputed minimum, so a query touches at most two partial blocks scanned by hand plus a run
of whole blocks read straight from the table. Verified against a naive scan across 20,000
randomized trials, and against the real shipped demo via a step-by-step fake-DOM harness — the
default query correctly reuses block 1's precomputed minimum instead of re-scanning three more
elements by hand.
A plain segment tree only ever has one state, "right now." This version keeps every past
version queryable forever by never mutating a node — an update allocates only the
O(log n) nodes on the path to the changed leaf, reusing the other 11 of 15 nodes
by reference, verified node-for-node against the shipped generator (exactly 4 new nodes per
update on the demo's 8-leaf tree, every earlier version still answers correctly after 4 more
updates on top of it).
A segment tree answers a range query in O(log n) and supports updates in
O(log n) too. A sparse table gives up updates entirely — the array is frozen once
built — and gets the query down to O(1): precompute every power-of-two-length
range, then answer any query by combining two of them, letting the middle overlap. That overlap
trick only works when the combining operation doesn't mind being asked twice: demo's
min mode matches a naive scan on all 36 possible ranges over the default
8-element array, checked exhaustively; switching to sum mode reuses the
identical two-block logic and is wrong on all 36 — even ranges whose length is already a power
of two, which pick the same table cell twice and silently double the true answer.
The plain segment tree's update only ever touches one index — adding a value to a whole
range means one point update per element. Lazy propagation gets range updates down to
O(log n) too: when an update's range exactly covers a node, stop there and park
the change as a pending tag instead of walking into its subtree, only paying to push that tag
down later if some other operation needs to see underneath. Demo tracks range-sum instead of
range-min, with a live badge on every node still holding a pending tag; step-through confirms
a Range Sum query that partially overlaps two still-tagged nodes forces exactly the push-downs
needed and lands on the same total a naive recomputation gets, 30, versus 10 if the push-down
were skipped.
A Fenwick tree needs an invertible operation (subtraction undoes addition, so it can do prefix sums) — a segment tree only needs an associative one, so it can answer arbitrary range queries a Fenwick tree structurally can't, like range minimum. Includes a step-through demo of both point-update and range-min query, drawing the actual node-link tree and highlighting which O(log n) nodes each operation touches, with a live self-check against a naive scan on every query.
Neither a plain array (O(1) update, O(n) prefix sum) nor a precomputed running-total array (the reverse trade) — a Fenwick tree stores a small set of partial sums, keyed by each index's lowest set bit, so both update and prefix-sum query run in O(log n). Includes a step-through demo showing exactly which stored slots an update or query touches, and why, with a live self-check against a naive sum on every query.
Give up almost all ordering, keep only "parent smaller than both children," and the tree shape stops depending on insertion order — a heap is always a complete binary tree, packed into a plain array with zero pointers. Includes an interactive insert/extract-min demo that draws the array as a tree and highlights the sift-up/sift-down path.
Eleventh Probabilistic entry, and the first to answer "draw repeatedly from a fixed, arbitrarily-weighted distribution" rather than a question about stream items. Walker's 1974 idea, refined to O(n) construction by Vose (1991): scale weights so their average is exactly 1, split into "small"/"large" piles, then repeatedly pair one from each so every index ends up with a probability and (usually) an alias to fall back on — one uniform index pick plus one coin flip per draw, forever, no matter how skewed the weights. Verified with a 300,000-draw sampling check landing within 0.2 points of the true weighted proportions, plus two measured pitfalls: forgetting to scale by n silently collapses every draw to uniform (50,000-trial check landing at an even ~20% each instead of the true 5/10/15/20/50% split), and patching one weight in place instead of rebuilding silently keeps sampling the old distribution entirely unchanged. Updated Choosing a Probabilistic Structure (ten entries → eleven, a fourth standalone question alongside Locality-Sensitive Hashing).
Tenth Probabilistic entry, and the simplest of the site's fixed-memory stream summarizers: Robert Morris's 1978 approximate counter needs no hash function and no item identity at all — it just counts events, incrementing a single small counter with probability 1/2c instead of tallying every one. Proved unbiased by induction (E[2c] = n + 1) and checked live: 20,000 trials at n=100 landed a single counter's mean at 100.38 against a measured standard deviation of 71.04 (theoretical √(n(n+1)/2) = 71.06) — correct on average, but wide, the honest headline pitfall. Averaging 16 independent counters shrank that spread to 17.55 (theoretical 17.77), and a provable off-by-one bug (probability computed as 1/2c+1 instead of 1/2c) exactly halved the estimate in both the algebra and the measurement (49.42 vs. true 100). Updated Choosing a Probabilistic Structure (nine entries → ten, the stream-summarization family eight → nine).
Ninth Probabilistic entry, and Count-Min Sketch's unbiased sibling: same d×w counter grid, but every add also flips a random per-row sign before touching the counter, and every query multiplies that sign back in before taking the median of the d readings instead of the minimum. Where Count-Min Sketch can never undercount but always leans high, this trades that one-sided guarantee for an error centered on zero. Measured across 5,000 independently-seeded sketches on the same skewed stream: 37.3% of estimates landed above the true count, 37.7% below, 25.0% exact (mean error 0.003) versus a parallel Count-Min Sketch's 99.4% overestimate rate (mean error +4.198) on the identical stream. Three quantified pitfalls: taking the min instead of the median (biased the wrong direction, 80.5% understating); forgetting to re-multiply by sign before the median (mean error −40.3 against a true count of 40); and deriving the sign from the index's own parity instead of an independent hash (a structural bug, not a matter of degree — collisions can no longer partially cancel, so 100% of trials overestimated). Re-verified the real shipped demo (bird/fish exact, cat/dog real underestimates, owl a real overestimate, lion reading a genuine negative −1 for an item never added) via a fake-DOM harness. Updated Choosing a Probabilistic Structure (eight entries → nine) and Count-Min Sketch's own page with a forward link. No new CSS beyond two small modifiers — reuses .fw-matrix/.cms-probe/.changed/ .cs-caption/.dp-stats/.bloom-added verbatim from Count-Min Sketch's own demo.
Where the Bloom Filter sets shared bits and the Cuckoo Filter displaces fingerprints one at a time, the XOR Filter is built once from the whole key set via peeling: repeatedly pull out any key whose slot is touched by no one else left, then assign values in reverse order so every key's fingerprint reconstructs as the XOR of exactly three fixed slots. No add or delete after construction. Includes a real peel-construction demo (0 false negatives across all 20 words, a measured false-positive rate close to the 8-bit fingerprint's theoretical ~0.39% ceiling) and a Pitfall isolating the actual cause of unreliable construction: not hash-seed correlation (tested directly and ruled out) but hash avalanche quality — a weakly-mixed hash dropped peel success from 90.0% to 47.0% at n = 1,000 (300 trials each) while deliberately correlating three well-mixed hashes' seeds changed nothing.
Every other Probabilistic entry spends randomness on one item at a time; LSH spends it on a question between two items — are these approximately similar? MinHash signatures estimate Jaccard similarity in a fixed k-length signature per item, and banding buckets similar items together without ever comparing every pair. Includes a live pairwise-estimate demo and a banding demo with a real measured trade-off: a strict scheme misses 66% of true near-duplicates to get zero false positives, a loose scheme catches all of them but flags 59% of unrelated pairs too.
The Bloom Filter's shared-bit design can't support delete without a whole separate counting variant — a Cuckoo Filter sidesteps the problem by storing a small fingerprint in one specific slot, found via the same displacement idea as Cuckoo Hashing, so delete becomes a real, first-class operation. Includes an interactive add/query/delete demo with a real insertion failure (5 of 20 candidate words can't find a slot, verified against the shipped code, not staged) and a real fingerprint collision that makes deleting a false positive silently corrupt a genuine member.
A different way to reach the same balanced-search guarantee Skip List earns with coin flips: give every inserted key a uniformly random priority and keep the tree BST-ordered by key, max-heap-ordered by priority. Insert bubbles a new leaf up while it outranks its parent; delete trickles a node down toward its higher-priority child; search never rotates at all, unlike a splay tree. Includes an interactive insert/search/delete demo, plus a checked Pitfall showing a heap-valid-but-unbalanced tree from non-random (insertion-order) priorities.
A different fixed-memory question over the same kind of unbounded stream HyperLogLog answers: not "how many distinct items," but "give me k of them, chosen fairly." Each item past the first k draws one random number deciding whether it evicts a current reservoir slot. Includes a step-through demo plus a live 50,000-trial frequency check catching a real off-by-one bug — a shrunk random range that doesn't crash or look wrong on any single run, only a measured, exact skew (3/11 vs. 4/11 vs. the true 1/3) across many.
Completes the trio: the Bloom Filter answers "have I seen this?" and the Count-Min Sketch answers "roughly how many times?" — HyperLogLog answers "roughly how many distinct items?" in the same fixed memory. Each add hashes once, keeps only the longest leading-zero run seen per register. Includes an interactive add demo with a real, checked overshoot: the raw estimator reads almost double the true count at this scale, fixed by the small-range correction shown working right alongside it.
The Bloom Filter's counting cousin: same fixed-memory trade, but answering "roughly how many times?" instead of "have I seen this?" Each add touches one counter per row across d independent hash functions; each query reports the minimum of the d readings, the least-polluted one available. Includes an interactive add/query demo with a real overestimate (from partial collisions) and a real full collision between two words that were never both added, where the sketch genuinely cannot tell them apart.
Same balanced-search problem as AVL and red-black trees, solved with no rule to enforce at all: each element flips coins to pick its own height across several stacked, sparser-going-up linked lists, so a search can skip whole runs of the bottom list before dropping down. Includes an interactive insert/search/delete demo drawing every level, with a real forced-worst-case check and measured level-count-vs-log(n) figures in Pitfalls.
A genuine gap flagged and deferred back at session 214 (Rope was the more tractable pick that session): every earlier tree-path structure here is either static (Binary Lifting, Heavy-Light Decomposition — no edge changes) or offline (Offline Dynamic Connectivity — the whole timeline known up front). This one drops both restrictions — link, cut, and findRoot/connected in any order, no advance knowledge — by covering the forest with changing vertex-disjoint "preferred paths," each held as its own splay tree, so the same zig/zig-zig/zig-zag rotations and amortized argument carry straight over. Verified from scratch against an independent represented-forest oracle (2,000 trials × 300 ops on 12 nodes, 500 trials × 800 ops on 40 nodes — a million operations total, zero mismatches), then re-verified the exact shipped functions via a fake-DOM harness driving real node-click/button sequences, including a live cross-check against an independently walked parent array after every findRoot/connected call. Measured, not asserted, for the amortized bound: 20,000 random accesses on a single worst-case n-node chain average 11.5/14.7/18.6 rotations at n=1,000/4,000/16,000 — 1.16×-1.33× log₂n at every size, not growing linearly. Two checked pitfalls, both concrete answer flips: an isRoot check weakened to "has a parent" instead of "is a real child" lets splay cross a path-parent boundary it shouldn't, flipping 2 of 4 connectivity answers wrong after a cut; and dropping access()'s own final splay(x) call (easy to assume redundant since every ancestor was already splayed) leaves x buried mid-tree, so cut() detaches the wrong subtree and flips all 4 checked answers to false. Added a "where splay trees show up" bullet on Splay Tree's own page.
The site's seven comparison-based search trees all answer "is x present?" — this one adds a single subtree-size field to a Treap and answers two different questions instead: select(k), the k-th smallest stored value, and rank(x), how many stored values are smaller than x, both in O(log n). The balancing mechanism is untouched — same rotation loop, same random priorities — the size field just rides along, recomputed in O(1) at the two nodes any rotation touches. Verified from scratch against an independent sorted-array oracle (3,000 seeded trials, 180,000 operations, 405,166 checks including a full recursive size recount after every single operation, zero mismatches), then re-verified the real shipped insert/delete/select/rank functions with a click-driven fake-DOM harness (400 sessions, 4,774 checks against an independently seeded reference model fed the identical priority stream, zero mismatches). Self-tested against two deliberately broken variants first: dropping the two size-fix calls from both rotation functions corrupts the size field while leaving BST order, heap order, and every parent pointer perfectly intact — invisible to any check that doesn't look at size directly, caught in 1,971/2,000 trials the instant rotations fired; a one-character rank() boundary bug (strict "<" instead of "<=") silently double-counts the queried value whenever it's present, wrong in all 35,990/35,990 checks that hit that case. Zero new CSS — reuses treap.html's own .bst-node.treap-node two-line node verbatim, showing subtree size instead of priority.
The one genuine gap left in the site's own mergeable-priority-queue family: the structure that came first (J. Vuillemin, 1978), six years before Fibonacci Heap was built specifically to beat its decrease-key bound. A forest of binomial trees, at most one per degree, whose shape is literally the binary representation of its own size — merge is binary addition with carry, insert is "add one." Unlike Fibonacci/Pairing Heap's amortized decrease-key and Leftist/Skew Heap's decision not to build it at all, this page gives decrease-key a genuine worst-case (not amortized) O(log n) bound, the "no free lunch" member of the family. Verified with a seeded 20,000-trial stress harness (800,000 operations) checking heap order, the binomial-tree shape invariant, the binary-representation invariant, and the cached min pointer after every operation — 0 failures — then re-verified against the actual shipped handlers via a fake-DOM harness (8,000 more trials, 320,000 operations, 0 mismatches). Both harnesses self-tested against deliberately broken variants first (a wrong-parent link bug and a stale-min-pointer bug), each caught immediately. Measured, not asserted: inserting into an all-ones-bits-set heap of size 2^k−1 costs exactly k link operations at every k tested (2 through 15), and the deepest leaf in a single degree-k tree is always exactly k levels down, confirming both the O(log n) worst-case insert and decrease-key bounds directly. Updated the search-tree guide (four mergeable-heap routes → five) and cross-linked from all four sibling pages.
A fourth route to the mergeable-priority-queue question Fibonacci Heap, Pairing Heap, and Leftist Heap already answer: drop Leftist Heap's null-path-length field entirely and swap every merged node's two children unconditionally, no comparison at all — the whole structure is that one rule. The cost: no worst-case bound survives, only an amortized O(log n) one, proven by a heavy/light potential argument (Sleator & Tarjan, 1986). Verified with a seeded 20,000-trial stress harness (800,000 operations) checking heap order and key set after every operation — 0 failures — then re-verified against the actual shipped handlers via a fake-DOM harness (8,000 more trials, 240,000 operations, 0 mismatches). Measured, not asserted: a single adversarial merge of two hand-built n-node right-chains costs exactly 2n − 1 recursive calls (genuinely O(n), no bound at all) yet collapses the result's right spine to 1 node — the same expensive call that breaks the bound is what pays for it; ordinary random usage instead holds a flat ~2 calls per operation from n = 1,000 to 100,000, comfortably inside the amortized bound. The same skip-the-swap bug as Leftist Heap's own demo degenerates the tree into a full-length chain, but total rather than partial — there's no invariant field left standing once the swap is gone. Updated the search-tree guide (nineteen entries → twenty) and cross-linked from all three sibling pages, fixing a confusing wording bug in Leftist Heap's own forward reference to this page along the way.
A third route to the mergeable-priority-queue question Fibonacci Heap and Pairing Heap already answer: one integer per node (null path length) and a swap-if-needed rule keep the tree's right spine within ⌊log₂(n+1)⌋, giving merge/insert/extract-min a worst-case (not amortized) O(log n) bound at the cost of not building decrease-key at all. Verified with a seeded 20,000-trial stress harness (800,000 operations) checking the leftist property, heap order, and key set after every operation — 0 failures — then re-verified against the actual shipped handlers via a fake-DOM harness (8,000 more trials, 240,000 operations, 0 mismatches), including a self-test confirming the bound really breaks with the buggy checkbox checked. Measured, not asserted: inserting 1 through n ascending — the adversarial case — leaves a right spine of exactly 3/6/9/12/13/15 nodes at n = 10/100/1,000/5,000/10,000/50,000, matching the ⌊log₂(n+1)⌋ bound exactly at every size; the same input with the leftist swap disabled degenerates into a straight chain of length n every time. Updated the search-tree guide (eighteen entries → nineteen) and cross-linked from both sibling pages.
The simpler sibling of Fibonacci Heap: one merge rule (smaller root wins, other becomes its child) replaces marked bits and cascading cuts entirely, deferring all consolidation to a two-pass merge at extract-min time. Verified with a seeded 20,000-trial stress harness (800,000 operations) checking heap order, parent pointers, no duplicate nodes, and extract-min against an independent full-tree scan after every single operation — 0 failures — then re-verified against the actual shipped functions via a fake-DOM harness driving real Insert/Extract/Decrease clicks (8,000 more trials, 328,000 operations, 0 mismatches). Measured, not asserted: inserting k increasing values under an established smaller root, then extracting once, leaves a tree of depth 3 regardless of whether k is 10, 100, 1,000, or 5,000 under the real two-pass merge, but a naive one-pass left-to-right fold on the identical input leaves a straight chain of depth exactly k every time — the shape difference the two-pass method's proven O(log n) amortized bound actually depends on. A live "skip the cut" checkbox reproduces a real bug: without the cut, decrease-key mutates a key in place with no restructuring, and peek() keeps confidently reporting the stale old minimum while a true-minimum-by-full-scan readout right next to it quietly disagrees. The most interesting fact on the page isn't a bug at all: decrease-key's own amortized bound has been a genuinely open question since 1999, when Fredman proved a lower bound of Ω(log log n) that the structure's best proven upper bound (2005) still doesn't match — reported honestly as an unresolved gap rather than rounded to a single number. Fixed a real pre-existing staleness bug found while updating the search-tree guide: it still said "sixteen" Node-Linked Trees entries, a count that was already wrong before this session touched anything (Cartesian Tree was never added to its tally) — now eighteen, with both Cartesian Tree and Pairing Heap folded into its "outside the comparison" enumeration.
A forward reference Treap's own "where treaps show up" section named without linking: build a treap-shaped tree over an array using the array's own values as priority instead of randomness, and the result is exactly a Cartesian Tree — deterministic, not randomized, with the lowest common ancestor of any two indices always landing on the range minimum between them. Verified the core claim directly against the exact shipped O(n) monotonic-stack construction and a naive parent-walk LCA: 30,000 randomized trials, 0 mismatches, checking both that the LCA always holds the correct minimum value and that it falls within the queried range, plus a fake-DOM harness driving the real Step/Load buttons and cell-click query handler through several arrays. Measured, not asserted, for the height claim: average tree height across dozens of random-array trials each came out 12.4 (n=100), 21.1 (n=1,000), 30.6 (n=10,000), 38.2 (n=100,000) — growing far slower than n, consistent with the expected O(log n) height well-shuffled data gets. One verified pitfall inherited directly from the first Pitfall on Treap's own page: a sorted array is the worst case, not a best case — the same 8-element demo array that builds height 3 unsorted degenerates to height 7 (a full chain) once sorted ascending, confirmed live via the demo's own "sorted (worst case)" preset, and unlike a Treap there's no random priority left to reach for to dodge it.
A third route to the same question Trie and Ternary Search Tree already answer (string storage, prefix queries): collapse every chain of single-child nodes into one edge labeled with the whole shared substring, instead of spending one node per character. Verified from scratch against a plain-array oracle three ways — an exhaustive sweep of all 64 subsets of a 6-word set, an exhaustive sweep of all 720 insertion orders of that same set (confirming results never depend on arrival order), and 45,000 randomized interleaved trials across three alphabet sizes, 0 mismatches throughout, plus a structural invariant (no non-root, non-word node may have exactly one child) checked after every single operation. Re-verified the exact shipped functions the same way (10,000 more trials, 0 mismatches) and via a fake-DOM harness driving the real click handlers through insert/search/prefix/delete, including a genuine mid-edge split and a delete that merges two edges back into one. Measured, not asserted: the classic seven-word PATRICIA example costs 14 nodes here versus 28 as a plain trie, and searching its longest word (10 characters) takes 4 edge traversals instead of 10. Two verified pitfalls: a search that forgets to check it landed on a real node boundary (not just partway through a compressed edge) falsely reports 10 of 41 truncated, never-inserted queries as found; and a delete that removes dead leaves but never re-merges a parent left with one child erodes the tree back to one node per character, measured concretely as 2 nodes (correct) versus 21 (buggy) after removing 19 side branches from one shared-prefix family.
B-Tree's database-index cousin: internal nodes hold nothing but routing-key copies, every real
key lives in a leaf, and the leaves are threaded into a linked list — turning a range query into
one descent plus a straight walk instead of a scatter of independent searches. Verified from
scratch against a plain-array oracle (500 trials of 60 mixed insert/delete/search/range
operations, 30,000 operations total, 0 mismatches), then re-verified the exact shipped functions
via a fake-DOM harness (a further 15,000 operations plus the page's own guided "Try it"
sequence). Measured, not asserted: a range query for 6 results touches 2 internal nodes plus 4
leaves (6 node visits) against this page's own demo tree, versus 18 node visits for the same 6
results via six independent single-key searches — the same 2 internal nodes re-read 6 times
over. Two verified pitfalls, both about delete's leaf-level borrow, the one place a B+ tree's
rebalancing has to diverge from B-Tree's: reusing B-Tree's move-the-separator-down borrow logic
corrupts the tree in 119 of 200 stress trials against the shipped code, because a B+ tree's
separator is a copy, not real data free to relocate; and moving the sibling's real key correctly
but forgetting to recompute the separator afterward leaves every structural invariant clean while
search wrongly reports "not found" for the just-moved value in 165 of 800 trials.
A balanced binary tree of small string chunks, answering yet another question this category's
other entries don't: not ordering, not prefix lookup, but efficient mid-string editing. A plain
JavaScript string copies the whole thing on any mid-string edit; a rope caches each internal
node's "weight" (its left subtree's total length) so index and split can route straight down one
root-to-leaf path, and concatenation is a single O(1) pointer join instead of a copy. Verified
against a plain-string oracle (300 random strings, 30,000 interleaved index/insert/delete/split
operations, 0 mismatches), then re-verified the real shipped functions via a fake-DOM harness.
Measured the payoff directly: inserting into a 2,000-character, 1,023-node rope creates exactly 5
new node objects, reusing the other 1,018 unchanged — the same "path copying" persistence this
site's Persistent Segment Tree page names directly, discovered here as a side effect rather than
the explicit design goal. Three verified pitfalls: an off-by-one in the weight comparison that
silently returns undefined for 31.6% of characters instead of crashing; unbounded
growth from repeated single-character concatenation (depth 1,000 for a 1,000-character string,
against depth 9 for the same string built in one shot); and a broken "fast" leaf-mutation path
that corrupts every other rope sharing that leaf, concretely breaking a draft/draft-plus-
signature version pair that should have stayed independent.
A second structure answering Trie's exact question (store strings, answer prefix queries) a
completely different way: one character and exactly three pointers — left, mid, right — per
node, so the "which way to branch" choice at each character becomes an ordinary binary search
instead of an array or map lookup. Verified from scratch against a brute-force Set oracle
(40,000 interleaved insert/search/startsWith/prefix/delete operations, 0 mismatches after fixing
a real bug the first draft had) plus an exhaustive 32-subset sweep, then re-verified the real
shipped functions and click handlers via a fake-DOM harness. Measured, not asserted: a trie and
a TST always end up with exactly the same node count for the same words (12 either way for the
8-word demo shared with Trie's own page; 2,071 either way at 500 random words) — the real
difference is what each node costs to store, not how many exist. Two verified pitfalls: a naive
startsWith that only checks "does this node exist" reports 29 false positives across
40,000 trials, because a reachable node can be kept alive purely by an unrelated sibling word; and
a delete-pruning check that forgets to test left/right (not just
isEnd and mid) wrongly deletes all seven other demo words when "cat" is
removed, despite none of them sharing a letter with it beyond the root.
A different kind of decomposition from its nearest sibling, Heavy-Light Decomposition: instead
of flattening the tree into an array for one range structure to sit under one path at a time,
this builds a second tree over the same nodes by repeatedly removing whichever node's removal
splits the remainder into pieces no bigger than half of what came before. The halving guarantees
the resulting centroid tree is only O(log n) deep regardless of the original tree's shape, which
is what turns "do something for every pair of nodes" from an O(n²) problem into O(n log n).
Verified the depth bound two ways (5,000 random-tree trials plus path graphs to n = 2,048, zero
exceeding ⌈log₂ n⌉) and the centroid property independently (a fresh BFS per removal, not a
reuse of the search's own subtree-size array) across 3,980 trials before writing content, then
re-verified the real shipped demo via a fake-DOM harness. Worked out and verified the classic
"count pairs within distance K" application from scratch against a brute-force all-pairs BFS
(10,710 trials, zero mismatches). One checked pitfall, the loudest kind: skip the
already-removed-node check and the very first recursive call rediscovers the whole original
tree and finds the same centroid all over again — a guaranteed infinite loop, crashing with
RangeError: Maximum call stack size exceeded before producing any output.
A genuine gap alongside this category's other two tree-path structures: Offline LCA answers ancestor queries in O(1) but only in one known-up-front batch, and Binary Lifting answers them online but via a static O(n log n) jump table that can't cheaply absorb a single value changing. Heavy-Light Decomposition flattens the tree into a plain array instead — the same domain Segment Tree/Fenwick Tree already operate over — so any path becomes at most O(log n) contiguous ranges, letting a range structure underneath support point updates and direct subtree queries neither LCA structure offers. Verified the light-edge bound empirically (max 10 chain transitions across 1,290 random trees up to 2,000 nodes, against log₂(2000) ≈ 10.97) and path-sum correctness across 47,200 random-tree trials before writing content, then re-verified the real shipped demo via a fake-DOM harness. Reuses Binary Lifting's own 11-node example tree and its exact (8, 11) query pair for a direct side-by-side. One checked pitfall: comparing raw node depth instead of chain-head depth to decide which side climbs — on this page's own tree, 46 of 110 ordered query pairs walk straight past the root and corrupt the sum to NaN, 64 coincidentally land on the right answer anyway, and a separate sweep across smaller random trees found the same bug can also return a wrong-but-finite number elsewhere, not just crash loud.
Closes a forward reference Johnson's Algorithm's own Complexity section named twice with nowhere to link. A forest of trees with almost no shape rule — inserts are free, and the deferred work all comes due on extractMin's degree-based consolidation pass. The payoff is decrease-key, amortized O(1) via a marked-bit cascading-cut scheme, versus a binary heap's inability to do it cheaply at all. Verified two ways: a seeded, reproducible 10,000-trial stress harness against a from-scratch reference model, and a second 10,000-trial run against the exact shipped demo functions extracted via Node's vm module — the second run caught a real transcription bug the first couldn't (node/parent transposed in the shipped cascadingCut), honestly written up in the page itself. Also includes a direct measurement of a single extractMin's real cost after n lazy inserts (up to 9,991 merge operations at n=10,000), demonstrating the "amortized, not worst-case" distinction concretely rather than just asserting it.
The online counterpart to Offline LCA — closes forward references on that page and on Second-Best Spanning Tree. Precomputes each node's 2k-step ancestors once (the same doubling idea Sparse Table uses for arrays, aimed at a tree instead), then answers any lowest-common-ancestor query in any order afterward. Interactive step-through with a live toggle reproducing a real bug: skip the depth-equalization swap and two of the tree's own queries come back wrong, verified against the shipped script. Also covers the path-max extension Second-Best Spanning Tree's own Complexity section names, checked against a brute-force path walk on 15,000 random-tree trials.
Not a search tree at all — a binary tree of hashes answering a different question: does this one item really belong to this dataset, provable without shipping the rest of it. Real SHA-256 via the Web Crypto API, domain-separated leaf/node hashing, and the actual RFC 6962 recursive split construction that avoids the padding bug behind CVE-2012-2459 (Bitcoin's odd-leaf-count merkle root vulnerability). Interactive rebuild/prove/verify demo showing only the edited path's hashes change, and a stale proof correctly failing against an unrebuilt edit.
Zero balance metadata per node — no height, no color, no priority — the only tradeoff of the site's four self-balancing trees. Rebalances by occasionally flattening and rebuilding a whole unbalanced subtree instead of rotating on every write. Includes an interactive insert/search/delete demo (loaded with 1 through 8 ascending, still within its own height rule) where inserting 9 triggers a partial rebuild of exactly the unbalanced piece, and three follow-up deletes trigger a full-tree rebuild via the global size-drop rule.
Every other tree here branches at most two ways; a B-tree node holds several sorted keys and branches one more way than it has keys, staying wide and shallow instead of deep — the shape every disk-backed database index and filesystem directory tree actually uses. Includes an interactive insert/search/delete demo (loaded with 10 through 90 ascending, the same input that collapses a plain BST into a chain) that stays at height 3 throughout and names every split on insert or merge/borrow on delete.
No shape invariant at all, unlike AVL or Red-Black — instead, every insert/search/delete rotates the touched node all the way to the root via zig/zig-zig/zig-zag splaying, trading a worst-case guarantee for an amortized one. Includes an interactive demo (loaded with the same 1-through-7 sequence AVL/Red-Black used, landing in a full height-7 chain this time) that shows the tree's height dropping live as a search splays, and names every zig/zig-zig/zig-zag step.
Same balance guarantee as AVL, paid for differently: every node gets a red/black color under four rules instead of a cached height number, trading AVL's stricter balance for cheaper rebalancing. Includes an interactive insert/search/delete demo (loaded with the identical 1-through-7 sequence AVL used, for a direct side-by-side) that highlights every node a fixup recolors or rotates and names the exact double-black case delete's own fixup fires.
One node per character instead of one node per key, so words sharing a prefix share the same nodes on the way down. Includes an interactive insert/search/prefix/delete demo that draws the actual branching tree, with a real autocomplete-style Prefix query and a Delete that prunes only as far back up the tree as it safely can.
Same binary search tree as before, plus one rule enforced after every insert: every node's left and right subtree heights differ by at most 1. Break that rule and the tree repairs itself with a rotation — a small, O(1) fix that turns the BST's hopeful "O(log n) on average" into a real guarantee. Includes an interactive demo (loaded with 1 through 7 inserted in ascending order — the exact case that turns a plain BST into a line) that highlights which nodes rotate and names the case.
Binary search's halving trick, freed from the array. Every node keeps everything smaller to its left and everything bigger to its right. Includes an interactive demo that draws the actual tree and lights up the comparison path for insert/search, and narrates which of the three delete cases (leaf, one child, two children) fired.
The site's 285th page and 11th Linear entry, and the first that isn't a sequence storage
option at all: a fixed-universe membership set, not "how should this be stored" but "is v
currently in the set." Two arrays — dense packs the actual members,
sparse[v] points back at v's slot in dense — and the trick is that
sparse is never cleared, ever; a reverse-validation check
(sparse[v] < n && dense[sparse[v]] === v) tells stale garbage from a
real member, which is what makes clear() free: just set n = 0 and
every check fails instantly, no O(U) reset. Verified against a plain Set model
over 200,000 randomized operations (0 mismatches), then re-verified the shipped demo's real
script the same way via a fake-DOM harness (5,000 more operations, 0 mismatches). The
Pitfalls section reproduces the structure's one real gotcha with concrete numbers: skipping
the reverse-validation half and trusting sparse[v] < n alone is a confirmed
false positive (insert 3, insert 5, delete 3 — naive check says 3 is still a member, real
check correctly says it isn't). Added a fourth exception to Choosing a Linear Data Structure,
the first set aside for answering a different question rather than a different environment
or a technique layered on an existing shape.
Tenth Linear entry: the same bidirectional traversal as Doubly Linked List, at half the per-node
memory, by storing the XOR of the previous and next addresses instead of both pointers
separately — XOR being its own inverse, whichever neighbor's address a walker already has in
hand recovers the other. Verified against a plain-array model over 30,000 randomized
operations (forward and backward walk checked after every op), plus a hand-traced
4-node example matching the shipped demo's numbers exactly, confirmed with a fake-DOM harness
driving the real shipped script before shipping. The real cost isn't memory: given only a node's own address, its link
field is one equation in two unknowns, genuinely unsolvable — this structure has no equivalent
of a doubly linked list's O(1) removeNode(node) given just a bare reference, and
a measured pre-ship bug (forgetting to XOR-toggle the old tail's link on append) silently
truncated a forward walk to a single node with no error at all. Also needs a real memory
address to XOR, which JavaScript never hands out — this page's own reference implementation
fakes one with an array index, a real limitation covered honestly rather than glossed over.
Added a new section to Choosing a
Linear Data Structure explaining why it's set aside from the guide's four-question funnel
for a different reason than Monotonic Stack and Monotonic Deque.
The site's ninth Linear entry and the two-ended sibling of Monotonic Stack: the same pop-before-push invariant applied from both ends of a Deque instead of one end of a stack, keeping the front always equal to the current sliding window's max (or min) in one O(n) pass instead of an O(n·k) recompute-per-window scan. Closes a real named-but-unlinked forward reference — Deque's, Monotonic Stack's, and this guide's own text all described a "monotonic deque" sliding-window variant by name with no page to point to. Verified from scratch against a brute-force oracle (30,000 randomized trials across array size, window size, and max/min mode, 0 mismatches), then re-verified the shipped step-through demo the same way via a fake-DOM harness. Measured, not asserted: unlike Monotonic Stack, it's window size — not data order — that decides the winner against a naive per-window rescan (naive wins at k=2, ties around k=4, then falls behind as k grows: 104 vs. 57 comparisons at k=5 widening to 224 vs. 56 at k=15 on a 30-element array). Two reproduced bugs: omitting the front-eviction check returns a stale answer 45.2% of the time across 20,000 trials; emitting a result before the window has filled is a real off-by-one that shifts every later answer, not just a harmless extra entry.
The site's eighth Linear entry, and the first that isn't a competing storage shape or access-discipline wrapper but a technique layered on top of a plain Stack: pop anything that breaks a chosen order before every push, and the next-larger-value question for every array index resolves in one O(n) scan instead of an all-pairs O(n²) check. Step-through demo plus a measured ops-vs-brute-force comparison across a worst case (falling run then one big value: 19 ops vs. 45 comparisons) and an honest best case where brute force actually wins on raw count (already increasing: 19 ops vs. 9 comparisons) — the guarantee, not raw speed on every input, is the real advantage. A live toggle reproduces a real silent-wrong-answer bug: strict vs. non-strict comparison disagrees on duplicate values with no error or crash.
Adds and removes at both ends in O(1) amortized — generalizes a Stack (use only the back) and a Queue (push back, pop front) at once. Growable-array backed like a Circular Buffer's wraparound plus a Dynamic Array's doubling, with one extra wrinkle neither alone needs: growing a wrapped deque has to unwrap it first, verified live by comparing a naive raw-index copy (silently loses elements) against the unwrap-aware version the shipped code actually uses.
A Queue with capacity fixed forever: instead of
reallocating when full, the write position wraps back to index 0 and reuses slots a
pop() already freed. Demo includes a live overwrite-vs-reject toggle for what
happens when a full buffer gets another push, plus a one-click check exposing the classic
ring-buffer bug: after filling a buffer exactly to capacity, head === tail —
indistinguishable from empty unless something (a count, or a deliberately wasted slot) tracks
fullness explicitly.
Adds a prev pointer alongside next. That second pointer buys
two things a singly linked list can't do: walk backward from the tail, and unlink any node
you already have a reference to in O(1) with no predecessor search — the exact trick a
hash map + linked list LRU cache depends on.
Demo includes a bidirectional get(index) that starts from whichever end is
closer, and a per-node × that removes it directly by reference.
A plain array with one more trick: when push runs out of room, it allocates a bigger backing array and copies everything over. Demo pushes past capacity live (dashed cells are allocated but unused, and stay that way after a pop — capacity never shrinks on its own), plus a measured cost comparison showing why the growth rule has to multiply capacity, not add to it: growing by a fixed amount instead of doubling measured 61× more total copying over 1,000 pushes, turning O(1) amortized push into O(n).
Nodes connected by pointers instead of one contiguous block — a scavenger hunt of clues, each pointing to the next. Includes an interactive insert/delete/find demo, and covers the core trade against arrays: O(1) splice anywhere you have a reference, O(n) random access and search.
Enqueue at the rear, dequeue from the front — a line at a checkout counter. Includes an
interactive enqueue/dequeue/peek demo, and covers the classic shift()
performance trap and where queues show up: breadth-first search, task queues, round-robin
scheduling.
Push, pop, peek — a stack of plates you can only touch from the top. Includes an interactive push/pop/peek demo, and covers where stacks show up: the call stack, undo/redo, bracket matching, depth-first search.
The site's eleventh Spatial entry, and — like Z-order Curve — a second way to answer "which points are near X" with no bespoke tree at all, but a completely different mechanism: carve space into fixed-size cells chosen up front, and bucket each point by a plain integer division of its coordinates, no sorting or comparison against any other point required. That buys O(1) insert, update, and delete — no other Spatial entry on this site supports moving a point without risking a rebalance. Two verified pitfalls, both stress-tested against a brute-force oracle: checking only the query point's own cell instead of the full range covering the query radius is wrong 36.2% of 20,000 trials (on this page's own demo, Q's own cell is empty, so a single-cell check would find zero of the two real matches); and moving a point without removing it from its old cell first is wrong 34.6% of 5,000 trials, with bucket entries growing 9× after 200 moves with zero net new points. A third, non-bug finding: a fixed cell size can't adapt to clustering the way every tree-based entry here can — 300 points crammed into a tenth of one cell touch all 300 on every query, against an average of 1.05 touched for the same count spread uniformly.
The site's tenth Spatial entry: like Ball Tree, indexes by pairwise distance alone, no coordinates required — but anchors each split with one point from the data (the vantage point) and the median distance to it, instead of Ball Tree's two far-apart anchors and a computed centroid. That buys a real guarantee Ball Tree can't make: depth is always ⌈log₂ n⌉, measured directly against Ball Tree on adversarial clustered-plus-outlier input (Ball Tree ran 30-60% deeper at every size tested). Two verified pitfalls, both stress-tested at 20,000 trials against a brute-force oracle: only checking the branch containing the query distance is wrong 40.1% of the time; treating internal nodes as pure routing instead of real candidate points is wrong 62.5% of the time, the more damaging of the two.
The site's ninth Spatial entry, and the sibling Z-order Curve's own closing paragraph named and deferred: a space-filling curve that rotates its recursive sub-curve at each level so it never makes Z-order's diagonal quadrant jump — measured as 0 non-unit jumps across 255 transitions on a 16×16 grid versus Z-order's 127. Build + query demo reusing the exact same ten points and rectangle as the Z-order page, showing that better path locality does not make Z-order's own corner-to-corner range-query trick safe to port over: it produces a real false negative on this demo's own data, and an exhaustive 32×32 sweep finds 84.6% of tested rectangles miss at least one true match. Where the locality genuinely does pay off — measured, not just cited — is Hilbert R-tree bulk-loading: 27.4% tighter leaf bounding boxes than the same bulk-load in Z-order.
The site's eighth Spatial entry, and the first to build no tree at all: interleave each point's
x/y bits into one Morton code, sort, and query with a plain binary search
over a flat array — the same trick MongoDB's legacy 2d index and geohashing use, turning
a 2D indexing problem into an ordinary 1D sorting problem that can piggyback on an existing sorted
store or database column instead of needing bespoke tree code. Build + range-query step-through demo,
with a measured 34.36× scan-waste penalty (candidates touched per real match) for a
query rectangle placed at a random offset versus a clean 1.00× for the identical
rectangle aligned to the curve's own power-of-2 grid, plus an exhaustive 4.3-million-pair check
confirming that waste never costs a missed match, and a concrete silent-collision bug when a
coordinate exceeds the interleave loop's assumed bit width.
The site's seventh Spatial entry, and the second (after Interval Tree) to answer a genuinely different question from the other five: not "what's near X," but "in what order do these possibly-overlapping surfaces need to be drawn so occlusion is correct from any viewpoint" — the classic Doom-engine painter's-algorithm structure. Build + viewpoint-driven traversal demo over a deliberately cyclic three-wall scene where no single global draw order is correct (all six possible whole-wall orderings get at least 6.4% of 360 test rays wrong), with a verified bug — skipping the per-node viewpoint side check — that looks correct from some viewpoints (0 of 72 columns wrong) and is silently 26% wrong from others, plus a measured Θ(n²) worst-case node-count blowup from naive partition selection.
The site's sixth Spatial entry, and the first built from nothing but pairwise distances — no coordinates, no axis, ever inspected on their own — so the identical code works over any distance function, not just 2D points. Build + nearest-neighbor step-through demo, with a verified pruning bug (forgetting to subtract a ball's radius from its center distance) that's wrong 18.3% of the time (20,000-trial stress test), a measured 29.8% sibling-ball-overlap rate absent from every other Spatial entry's clean space partition, and a direct high-dimensional test that debunks the common "ball trees win in high dimensions" claim rather than repeating it.
The site's fifth Spatial entry, and the first to trade space for a worst-case guarantee: a BST
split on x alone, with every node also carrying its whole subtree sorted by
y so a range query decomposes into O(log n) whole "canonical" subtrees
plus a binary search each, instead of the distance-based pruning KD-tree and Quadtree use. Build + range-query step-through demo, with
a verified bug where skipping a search-path node's own point (as opposed to its canonical
subtrees) silently drops real matches in 38.5% of trials, plus a measured case confirming the
canonical-subtree count stays near log₂ n even on the same collinear-point input that
made KD-tree visit 11× more nodes, at the cost of measured O(n log n) total space
(5.8×–15.7× a plain one-node-per-point tree, growing with n).
The site's fourth Spatial entry, and the first with no spatial partitioning at all: a plain binary search tree ordered by each interval's low endpoint, augmented with each subtree's max high endpoint so whole branches can be ruled out at once. Build + overlap-query step-through demo, with a verified bug where forgetting to merge children into that max field still passes every leaf but silently drops a real match 30.2% of the time (20,000-trial stress test), plus a measured case where a single very wide interval nearly triples the average nodes visited per query (13.45 → 39.76 over 500 intervals) by poisoning the prune check on every ancestor along its path to the root.
The site's third Spatial entry, and the first to index rectangles instead of points: groups entries bottom-up into overlapping minimum bounding rectangles (MBRs) via Guttman's quadratic split, rather than partitioning space top-down the way KD-tree and Quadtree both do. Build + range-query step-through demo whose own tree has one genuinely overlapping sibling-leaf pair — the query walks straight into it, visiting a leaf that turns out to hold zero matches, plus a 30,000-trial correctness stress test and a measured 500-duplicate-rectangle case that stays perfectly balanced where Quadtree's equivalent case silently lost every point.
The site's second Spatial entry: splits its bounding region into four fixed quadrants by geometric center once a box overflows capacity, instead of the KD-tree's data-driven median split. Build + range-query step-through demo, with a verified bug where skipping the max-depth guard doesn't crash on duplicate-coordinate points — it silently deletes them (500 inserts, 3 report success, 0 survive in the finished tree), plus a from-scratch stress test (5,000 trials) confirming range-query pruning itself never misses a real match.
The site's first Spatial category — a binary tree over 2D points that alternates splitting axis by depth (x, then y, then x again) instead of relying on one total order the way every other search tree here does. Build + nearest-neighbor step-through demo, with a verified pruning bug that silently returns the wrong answer 16% of the time (3,193/20,000 stress-test trials) if the backtrack-into-the-far-side check gets skipped, plus a measured pitfall where a depth-balanced tree over collinear data still visits 11× more nodes per query than a random point set of the same size.
The site's first guide: a cross-cutting comparison across all nine Approximate Match entries, organized by the problem you actually have (search inside a longer text vs. compare two whole strings vs. score similarity vs. a phonetic equality bucket vs. check a whole dictionary at once) rather than by algorithm name, plus a side-by-side table of what each one answers, its complexity, and whether it needs a bound chosen in advance.
A cross-cutting comparison across all six Shortest Paths entries, organized by three questions — negative edges possible? one source or all pairs? is a heuristic available? — rather than by algorithm name, plus a side-by-side table of what each one answers, its complexity, and its negative-cycle-detection guarantee.
A cross-cutting comparison across all seven Comparison Sorts entries — the site's largest category — organized by three questions: is n small? does stability matter? is a worst-case guarantee required? Plus a side-by-side table of time, space, and stability for each.
A cross-cutting comparison across all seven Exact Match entries, organized by how many patterns you're matching and how many times you'll search (one pattern vs. many, one search vs. repeated queries) before falling back to worst-case guarantee vs. average-case speed, plus a side-by-side table of complexity and failure modes.
A cross-cutting comparison across all eleven Searching entries, organized by access pattern (indexable vs. forward-only), whether the length is known up front, and whether the data's distribution is verified uniform — plus a note on Ternary Search, Quickselect, and Binary Search on Answer, which answer different questions (a unimodal peak; a given rank; a feasibility boundary) rather than competing on the same axis as the other seven, and Saddleback Search, which answers the same question on a matrix instead of an array.
A cross-cutting comparison across all seven Non-Comparison Sorts entries, organized by key type (continuous vs. integer) and range rather than by algorithm name — plus a note on why pigeonhole sort never beats counting sort outright, and why bead sort's natural-algorithm model rarely applies in software — with a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across all nine Minimum Spanning Trees entries, splitting first on whether five of them (Kruskal's, Prim's, Borůvka's, Reverse-Delete, Euclidean MST) are even competing for the same job — they build the identical tree by five different mechanisms, the last one only for points in the plane — before the other four turn out to answer a different question (bottleneck instead of total, next-cheapest instead of cheapest, verifying a candidate instead of building one, or trading a logarithm for randomness) entirely, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across all eleven Network Flow entries, splitting first on whether four of them (Ford-Fulkerson, Edmonds-Karp, Dinic's, Push-Relabel) are even competing for the same job — they compute the identical max flow, the last three by three different mechanisms all specializing Ford-Fulkerson's shared general method — before the rest turn out to answer a different question entirely (matching size, cheapest assignment, cheapest flow, the global minimum cut, or every pair's max flow at once), plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across all eight Game Trees entries, splitting first on whether a real adversary or plain chance is driving the uncertainty, then whether the tree is small enough to search to a real outcome at all, before setting Transposition Tables, Zobrist Hashing, and Quiescence Search apart as an orthogonal cache, the incremental key that makes it cheap, and the check that a cutoff position is settled enough to evaluate, rather than a sixth, seventh, and eighth way to pick a move, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across six of the site's eleven Convex Hull entries, which don't split by different questions the way most guides do — all six compute the identical hull — so this one splits by mechanism and cost instead: is the hull small relative to the input, and does a guaranteed bound beat typical-case speed, plus a shared collinear-boundary-point question most of the six answer identically and two get sharply wrong without their tiebreak. The other five are set aside up front as five genuinely different questions instead of a seventh, eighth, ninth, tenth, and eleventh way to answer this one.
A cross-cutting comparison across six of the site's eleven Array-Backed Trees entries (Binary Heap, Mo's Algorithm, Van Emde Boas Tree, Wavelet Tree, and Fractional Cascading each answer a different question), organized by whether old versions must stay queryable, whether the array ever changes, whether an update touches a whole range or one element, and whether the combining operation is invertible — plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across four of the nine Disjoint Set entries — Union-Find, Weighted Union-Find, Union-Find with Rollback, and Persistent Union-Find — organized by two independent questions (does a union carry a numeric relationship to query, does anything need to reach into the past) rather than one decision chain, with Offline LCA, Small-to-Large Merging, Kruskal's Reconstruction Tree, and Offline Dynamic Connectivity set aside as applications built on Union-Find rather than alternatives to it, and Partition Refinement set aside as a fifth exception — the literal opposite operation, sharing no code with Union-Find at all — plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across five of the six Node-Linked Trees entries — Binary Search Tree, AVL Tree, Red-Black Tree, Splay Tree, and B-Tree — with Trie set aside as answering a different question entirely (prefix lookup, not key comparison), organized by storage medium, whether every operation needs its own worst-case guarantee, and read-heavy vs. write-heavy access, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across three of the ten Hash-Based entries — Hash Table (chaining), Cuckoo Hashing, and Robin Hood Hashing — the only three that answer the same collision-resolution question, with Consistent Hashing, Bloom Filter, LRU Cache, Extendible Hashing, Perfect Hashing, Linear Probing, and Double Hashing set aside (each for a different reason — Linear Probing and Double Hashing specifically because they're both strictly dominated by Robin Hood Hashing for this exact contract), organized by whether a hard worst-case lookup guarantee is required, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across all six Linear entries — Dynamic Array, Linked List, Doubly Linked List, Stack, Queue, and Circular Buffer — organized as a four-question funnel rather than a flat table, since Stack/Queue/Circular Buffer are access-discipline wrappers rather than a third storage shape: indexed access, ends-only vs. middle splicing, LIFO vs. FIFO, and whether capacity is naturally bounded, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting guide across all ten Number Theory entries, organized by what you actually have in hand (two numbers, one primality candidate, a bound, an exponentiation, a square root to recover, an exponent to recover, or a system of congruences) rather than by algorithm name, tracing the two reuse chains underneath — Extended Euclidean feeds Chinese Remainder Theorem, Modular Exponentiation feeds Miller–Rabin, the Fermat inverse shortcut, Tonelli–Shanks, and Baby-Step Giant-Step — plus a side-by-side table.
A cross-cutting guide across all eight Probabilistic entries, split by two unrelated needs rather than one flat table: a randomized alternative to a rotation-based balanced tree (Skip List vs. Treap) and a fixed-memory summary of an unbounded stream (Cuckoo Filter, XOR Filter, Count-Min Sketch, HyperLogLog, Reservoir Sampling), plus the Bloom Filter pulled in from Hash-Based as the stream family's fifth member — with Reservoir Sampling flagged as the one structure here that's exact, not approximate.
A cross-cutting comparison across all eleven Dynamic Programming entries, organized as a nine-question funnel by subproblem shape rather than a flat table: an exponential subset, a tree node, the digits of a single number, two sequences or one, a shared depleting capacity or a positional/temporal compatibility, and how far back each cell needs to look — from Held–Karp's bitmask down to Kadane's Algorithm, which collapses to a single running variable, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across all six Graph Traversal entries, organized around what four of them layer on top of plain DFS — a three-state flag for Topological Sort, a disc/low-link pair for Strongly Connected Components, the same pair turned undirected for Articulation Points and Bridges — with BFS split off first by its shortest-path guarantee and Eulerian Path set apart as the one entry that isn't a DFS extension at all, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across eight of the site's eleven Spatial entries — KD-tree, Quadtree, R-tree, Range Tree, Ball Tree, VP-Tree, Z-order Curve, and Spatial Hash Grid — organized by whether the data has real extent, whether the worst case needs a guarantee, nearest-neighbor versus independently-addressable regions, and tree-based versus tree-free indexing, plus a side-by-side table of complexity and when to reach for each. Interval Tree and BSP Tree are set aside up front as each answering a genuinely different question; Hilbert Curve isn't folded into the comparison yet.
A cross-cutting comparison across all ten Geometry entries — the site's largest category, and one that had gone without a guide the longest — organized by three genuinely different questions (is a point inside a polygon, do segments cross, what structure describes a whole point set or polygon interior) rather than by algorithm name, tracing the Delaunay/Voronoi duality and where Closest Pair sits apart from it, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across all nine Greedy entries — unlike every other guide, these nine don't compete for the same job, so this one sorts by trust tier instead of by problem shape: exact by exchange argument (five entries including Huffman Coding and Activity Selection), exact by a lower-bound/upper-bound match (Interval Partitioning), exact only for the right input (Coin Change's canonical vs. non-canonical denominations), never exact but provably bounded (Set Cover's approximation ratio), or never exact and not bounded by anything at all (Greedy Coloring's vertex-order sensitivity) — plus a checklist for testing a new greedy idea against these four tiers, using 0/1 Knapsack as the standing example of a rule with none of the four.
A cross-cutting comparison across all eight problem-solving Backtracking entries — like Greedy, these eight don't compete for the same job, so this one sorts by what actually varies under their shared reject/place/backtrack shape: what makes a candidate illegal (structural conflict, arithmetic budget, a self-contained property check, or nothing at all — Knight's Tour), whether candidate order changes only speed or the answer too (Sudoku's MRV, Graph Coloring's start vertex, versus Word Search's every-starting-cell requirement), and whether a faster non-backtracking algorithm is even known (Graph Coloring's k = 2 bipartiteness special case against its own k ≥ 3 NP-completeness) — plus a ninth entry, Dancing Links, that changes the undo mechanism itself.