a field guide to algorithms and data structures, stacked one stone at a time
A twelfth Searching entry answering the exact same question its sibling Ternary Search does — the peak of a unimodal sequence — just cheaper: splitting at the golden ratio instead of thirds means one of the two probes survives into the next iteration unchanged, so only one fresh evaluation is needed per step instead of two. Verified 0 wrong across 200,000 randomized unimodal arrays; on the identical 31-element arrays Ternary Search's own demo uses, needs only 11–12 evaluations across 5 iterations against ternary search's 19 across 8. Two pitfalls: skipping the reuse never gives a wrong answer, just 42% more evaluations on average, defeating the entire point; rounding the search bounds to integers at every step instead of keeping them as floats until the final scan silently discards the true peak 28.7% of the time, because exactly one window width (4, out of every width from 3 to 2,000 checked) makes the two probes round onto the same index and produce a false tie.
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.
A fourteenth entry, closing a forward reference Damerau–Levenshtein Distance's own Complexity
section left open: the true (unrestricted) distance, which lets a transposed pair be edited again
afterward — something the site's existing OSA distance forbids. Replaces OSA's fixed two-rows-back
transpose check with an alphabet-indexed "last seen" lookup (the Lowrance–Wagner algorithm),
letting the transpose option reach back to any earlier row. An interactive demo toggles True vs.
OSA on the same CA/ABC pair the sibling page's Pitfalls already names,
settling at 2 vs. 3 live. Verified against a brute-force search over 14,641 string pairs (zero
mismatches) and a backtracked-and-replayed edit script checked across 150,000 random pairs.
A thirteenth entry, closing a forward reference named on two separate pages at once:
Smith-Waterman's own local floor-at-zero search fused with Gotoh's three-matrix affine-gap
machinery — what BLAST actually runs. The floor lives only in the M matrix; a
from-scratch check confirmed Ix/Iy never need their own floor, since any
gap always bottoms out at an earlier M cell that's already ≥0. Verified against an
independent brute-force substring-enumeration oracle (0 mismatches, 3,000 trials); two pitfalls
measured: reading the answer from the bottom-right corner instead of scanning for the true maximum
is wrong on 93.9% of trials, and dropping the floor entirely silently reduces the whole page to
plain Gotoh, wrong on 99.8% of trials.
A twelfth entry, closing a forward reference Smith-Waterman's own Pitfalls section named directly: affine gap penalties, charging a steep one-time cost to open a gap and a cheap per-character cost to extend it, so one long indel scores better than several short ones. Needs three cooperating DP matrices instead of one, because a single matrix can't remember whether a cell's score came from mid-gap or not — the exact information the next cell needs to charge the right price. Verified against a brute-force oracle (0 mismatches, 3,000 trials); two pitfalls measured: an off-by-one in the gap-cost formula wrong on 83.4% of trials, and collapsing the three matrices into one silently loses the true optimum on 16.8% of trials.
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.
The Exact Match category's 16th entry, and a refinement on Suffix Tree rather than a new path of its own — closes
the forward reference that page's own Complexity section named directly: Ukkonen's algorithm
builds the identical compressed tree "not implemented" there. Processes one character per phase:
a shared, mutable end pointer grows every existing leaf for free (Rule 1), a next-character-already-
present check ends a phase immediately once true, carrying any still-pending suffixes into later
phases (Rule 3), and an active point tracked across extensions plus a suffix link wired from each
freshly split node skip the walk back to the root (the trick beneath both). The total count of real
(non-skipped) extensions across a whole build turns out to be an exact invariant, not just a bound:
always precisely n, the text's own length including the terminator — checked directly
across 5,000 random texts, matched every time — because every real extension creates exactly one
new leaf and the finished tree always has exactly n leaves. Measured on Suffix Tree's
own n = 800 repeated-character worst case: 801 explicit extensions
against that page's own 320,400 insertion steps — and unlike the two Suffix Array
builders above, this exact input is close to this algorithm's cheapest case, not a stress
test, since the same repetition that makes naive comparison expensive is exactly what the early-stop
rule exploits for free. Two checked pitfalls, both verified against brute-force search across 20,000
random trials: freezing a new leaf's end at creation instead of pointing it at the shared, growing
value silently truncates every leaf and returns a duplicate phantom occurrence on the page's own
mississippi example — wrong 99.8% of the time; letting the
already-present check fall through and consume a pending suffix instead of leaving it for a later
phase silently drops real occurrences — wrong 80.2% of the time. Verified against
the naive trie-build-then-compress reference implementation on Suffix Tree's own page: structurally identical trees across
5,410 random and edge-case texts, and identical query results across 59,400 pattern checks — the
real shipped construction script, not a reimplementation, driven through a hand-rolled fake-DOM
harness (no jsdom in this environment).
The Exact Match category's 15th entry, and a further refinement on Suffix Array rather than a new path of its own — closes
the forward reference Suffix Array
Construction (Prefix Doubling)'s own closing paragraph named: "SA-IS's stronger
O(n) bound is a further step past that one, still not built here." Classifies every
suffix as S-type or L-type, uses that to induce most suffixes' positions from a small
LMS subset's order rather than comparing text directly, and recurses on a provably
at-most-half-sized reduced problem only when that subset's own order isn't fully known yet — the
classic mississippi example is the demo's default specifically because it needs that
recursion (its two issi LMS substrings collide under naming), while
banana alongside it shows a text where naming alone already settles everything.
Measured against that page's own n = 800 repeated-character worst case: counting
every array read/write across all recursion levels, 8,008 operations, growing at
an exact 2.00× per doubling of n (200/400/800/1,600/3,200 →
2,008/4,008/8,008/16,008/32,008) against Prefix Doubling's own measured
~2.16× — a real but modest gap at this scale, and this input is actually
SA-IS's cheapest case (no recursion at all), not its worst one, unlike the naive sort it makes
obsolete. Two checked pitfalls, both verified against an independently sorted reference order
across 30,000 trials: naming LMS substrings by a fixed comparison window instead of requiring
both to reach their own LMS boundary together treats one substring as a match for a longer one
it's merely a prefix of — wrong 2.2% of the time, live on bababab; classifying a
tied character as the wrong type instead of inheriting the next suffix's breaks the "S means
smaller" invariant every later phase assumes — wrong 40.6% of the time, and on caac
leaves an array slot entirely unfilled rather than merely misordered. Verified three ways before
any prose was written: a standalone design checked against brute-force sorting across 250,000+
random trials, the exact shipped <pre> reference snippet re-run standalone
against 100,000 more, and the real demo's own step-through logic driven end-to-end via a Node
vm fake-DOM harness across eight texts plus both bug toggles — which caught a real
bug this way: three of the nine step captions (classify, name, recurse) initially fell through to
a generic "phase: X" placeholder instead of a real description, fixed before shipping. Folded into
Choosing an Exact-Match String
Matcher as a new aside alongside Prefix Doubling's own, not a new branch in its ten-way
comparison; also fixed the six sibling pages whose own "other N exact-match entries" counts
needed to move from thirteen to fourteen, plus closed the forward reference on Suffix Array's own Pitfalls section directly. Zero new
CSS — reuses .cell/.cell.range/.cell.chain-start for the
S/L/LMS classification strip and .stat-table/.dp-wrap/tr.sa-match/tr.sa-wrong
verbatim from the two sibling suffix-array pages.
The Exact Match category's 14th entry, and a refinement on Suffix Array rather than a new path of its own — closes
the forward reference that page's own Pitfalls section named: comparing suffixes by slicing and
comparing full strings costs up to O(n) character work per comparison, making the
naive sort O(n² log n) on repetitive text. This page instead keeps a rank table
that already knows, from the previous round, how every suffix compares up to some prefix length,
and doubles that known length each round by combining two already-computed ranks instead of
rescanning text — producing the identical array Suffix Array's own binary search relies on.
Measured against that page's own n = 800 repeated-character worst case:
8,287 comparator calls against its 320,399 character
comparisons, a gap specific to repetitive text (on random text the two run within a small
constant factor of each other either way, since a naive comparison there usually diverges within
the first character or two). Two checked pitfalls, both verified against an independently sorted
reference order across 30,000 trials: skipping rank deduplication after a tied round hands tied
suffixes distinct ranks straight from sort position, freezing an arbitrary order permanently
instead of letting a later round resolve it with real evidence — wrong 79.7% of the time, clean
on "aaa" and reproducible on the demo's own default "mississippi";
treating a suffix that runs off the end of the text as tied with real rank-0 content instead of
as unconditionally smaller — wrong 38.4% of the time, live on "baabaab". Verified the
shipped step-through demo via a Node vm fake-DOM harness driving the real Step button
to completion across five inputs (both bug toggles, in both bug and correct states, on
mississippi/baabaab/banana), exact match to independently
computed suffix arrays. One new CSS rule (.stat-table tr.sa-wrong), reusing the exact
--danger/--danger-soft pair already verified for
.uf-node.contradiction — no new colors. Folded into Choosing an Exact-Match String
Matcher as a new aside mirroring Galil's Rule's own treatment, not a new branch in its
ten-way comparison; also fixed six sibling pages whose own "other N exact-match entries" counts
had drifted as far back as "other nine" (should have been "other twelve" even before this
session), plus confirmed three more reading "all ten" need no change since that number tracks the
guide's compared subset, not the category total.
The Exact Match category's 13th entry, and a refinement on Boyer-Moore rather than a new path of its own — closes a
forward reference that page's own Pitfalls section named: after a full match, the next
alignment's overlap with text already read is a genuine period of the pattern, so re-comparing it
is provably redundant. On the exact adversarial input Boyer-Moore's own page measures (1,000
'a's searched for ten 'a's), this page needs 1,000
comparisons against that page's 9,910 and naive search's 10,000
— a genuine O(n+m), not a marginal gain. Two checked pitfalls: the scan's lower
bound must be >=, not > — with the wrong comparison, a
two-character pattern against a three-character text reports two phantom matches where none
exist, wrong on 37.0% of 50,000 randomized trials; generalizing the same skip to ordinary
mismatch-driven shifts (not just full-match shifts) reuses a formula that's only sound when the
known-safe region is anchored at pattern position zero, which is true for a full match but not
for a general mismatch — wrong on 0.25% of the same trials, rarer but just as real. Verified the
shipped step-through demo via a Node vm fake-DOM harness across four inputs
(the periodic default, a non-periodic case reusing Boyer-Moore's own numbers exactly, a no-match
case, and the overlong-input rejection path). Zero new CSS — reuses .cells/.cell/.dp-table/.dp-stats/.cell.discarded
verbatim from Boyer-Moore's own demo. Folded into
Choosing an Exact-Match String
Matcher as a new aside (mirroring the Game Trees guide's refinement-aside pattern), not a
new branch in its ten-way comparison.
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, for clarity — the real O(n) Ukkonen's-algorithm build is
its own later entry, Suffix Tree
Construction) 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 twelfth non-comparison sort, and the first here whose per-level cost never depends on the
alphabet size. Answers the same variable-length-string question MSD String Sort does, but three-way partitions each
range on one character (low/equal/high against a pivot) instead of counting into an
R-sized bucket array — the same low/equal/high split a ternary search tree encodes as a node,
applied here as an in-place scan, recursing low/high at the same character position and equal
one position deeper (skipping the recursion entirely once the pivot itself has run out of
characters). Verified against Array.prototype.sort across 60,000+ trials (random,
forced-prefix, and duplicate-heavy), zero mismatches. Two pitfalls, both measured: recursing the
low/high groups one character deeper instead of at the same position is wrong on 76.1% of 30,000
trials (clean counterexample: ["cx","ba","aa"] sorts wrong without it); dropping the
guard that skips recursion once the pivot is exhausted hangs on any duplicate key, 44.4% of
20,000 duplicate-forced trials and still 0.84% of pure-random ones. Measured the alphabet-size
win directly: simulated MSD-style bucket overhead on the same 200 six-character words grows from
2.1× this entry's own cost at R=26 to 81,920× at R=1,114,112
(full Unicode). Verified the real shipped demo via a Node vm harness driving the
Step button through multiple word sets and every validation path, exact match throughout. Folded
into Choosing a Non-Comparison Sort as
a new alphabet-size fork alongside the guide's existing fixed-width fork; bumped ten sibling
pages' "other ten" → "other eleven" counts (and rewrote bead sort's own "all get their speed
via arithmetic" claim, since this entry is the one exception) in the same pass. Zero new CSS —
reuses .cell.wide/.range/.mid/.probe/.found/.chain-start/.log
verbatim.
An eleventh non-comparison sort, and the mirror image of MSD String Sort: applies
radix sort's exact count → prefix-sum →
place scheme to string keys instead of numbers, one character position at a time (26 buckets
instead of 10 digits), starting from the rightmost character. Requires every key to already be
exactly the same length — unlike numbers, which get an equivalent guarantee for free via
implicit leading-zero padding, strings have no such convention. Measured that requirement is
load-bearing, not a soft preference: a naive port that computes width from the longest word
instead of validating every word matches doesn't sort wrong when lengths differ, it crashes
outright — 100% of 19,507 random trials where lengths actually differed, via an out-of-bounds
character read one pass after a too-short word silently drops from the array. Second pitfall:
running passes left-to-right (reading order) instead of right-to-left breaks the stability
induction the moment two words tie on an early character — wrong 92.9% of 20,000 trials.
Verified the reference implementation against Array.prototype.sort across 30,000
random same-length-word trials, zero mismatches, and the real shipped demo via a Node
vm harness driving its actual Load/Step controls. Folded into
Choosing a Non-Comparison Sort as a
new fixed-width-vs-variable-width framing for string keys alongside MSD String Sort (new
section + table row, "four questions" → "five questions"); bumped all ten pre-existing
Non-Comparison Sorts pages' "other nine" cross-reference to "other ten." Zero new CSS — reuses
.cells/.cell/.cell.wide/.cell.mid/.cell.discarded
and .dp-wrap/.dp-table/.cs-caption/.log
verbatim from MSD String Sort and Radix Sort.
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 twelfth Comparison Sorts entry, and the first one that doesn't restructure the input array at all: deals each value onto the leftmost pile whose current top is ≥ it (binary search — the exact method this site's own Longest Increasing Subsequence page already runs for an unrelated reason, LIS length instead of a full sort), then recovers sorted order with a k-way merge across however many piles that produced. Verified against a plain sort oracle (30,000 random trials, 0 mismatches) and against the site's own shipped demo script via a Node vm harness (0/300 general-purpose mismatches plus a 500-trial duplicate-heavy sweep, also clean). Two checked pitfalls: confusing a pile's top with its bottom during the merge — the natural bug if a pile is popped from the wrong end — breaks the sort outright, wrong on 80.8% of 20,000 trials, not just miscounted; separately, this page's linear-scan merge makes an already-ascending array its worst case and an already-descending array its best (measured at n=1,000: 1,000 piles / 500,500 merge comparisons ascending vs. 1 pile / 1,000 descending, real O(n²) vs. O(n)) — backward from how insertion sort, bubble sort, and Timsort treat the same two patterns. Not stable (99.4% of 2,000 duplicate-heavy trials had an out-of-order equal pair). Updated Choosing a Comparison Sort (eleven → twelve entries, new section, added to the live race with new race-specific commentary) and fixed eleven sibling pages' own stale "other N comparison sorts" counts, including a pre-existing off-by-one on Cycle Sort's own page that had already gone stale before this session.
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 12th Minimum Spanning Trees entry, and the first that's directed — every other entry in
this category assumes an undirected graph, where the cut property that makes Kruskal's, Prim's,
and Borůvka's each correct has no directed equivalent (a cut can be crossed by the "wrong"-way
edge for free). Chu-Liu/Edmonds' algorithm picks each non-root vertex's cheapest incoming edge
independently, then — the one genuinely new idea — contracts any cycle that selection forms into
one vertex, reweighting every edge that enters it by subtracting the internal edge it would let
the recursion drop for free, before recursing on the smaller graph. Verified against an
independent brute-force oracle across 40,000 random directed graphs (3-7 vertices, varying
density), 0 mismatches, including graphs needing two or three nested contractions. Two checked
pitfalls: stopping after the first per-vertex selection without handling a cycle doesn't just
give a worse answer, it silently orphans whichever vertices the cycle traps — wrong on 45.6% of
20,486 random trials; a plausible-looking fix (discard the cycle's priciest internal edge, patch
the open vertex with its own next-cheapest option) is wrong 71.8% of the time on the graphs that
actually form a cycle, split between landing on a genuinely worse total (31.1%) and failing to
produce any valid arborescence at all (40.8%), because it decides which vertex reopens by
internal cost alone rather than the reweighted arithmetic. Verified the real shipped demo via a
Node vm fake-DOM harness driving all 12 steps of the actual Step button, checking
every node/edge CSS class at every step, not just the final log message. Folded into
choosing-a-minimum-spanning-tree-algorithm.html as a new section + table row
("last four" → "last five" of the not-competing entries) and bumped "all eleven of this site's
Minimum Spanning Trees entries" to "all twelve" on all eleven pre-existing MST pages' footer
cross-links, plus this homepage's own guide blurb. Zero new CSS — reuses
.bf-wrap/.bf-canvas/.bf-edge(.cycle-edge/.relaxed/.current)/.bf-edge-label(.relaxed)/.bf-node(.cycle/.current)/.bf-stats
verbatim from Bellman-Ford's own directed-weighted-graph family.
The 11th Minimum Spanning Trees entry, picked by category balance (three categories tied at
10) — Euclidean MST's own page restricts Kruskal to a point set's Delaunay triangulation when
edge weight is straight-line distance, and this entry asks the same question under Manhattan
(L1) distance instead. Checked first, rather than assumed, whether Euclidean MST's own
Delaunay-triangulation shortcut could just be re-weighted: it can't — Delaunay triangulation is
built entirely from Euclidean circumcircles, and a 5,000-trial stress check found it disagrees
with the true Manhattan MST about 1% of the time. The real shortcut splits each point's
neighborhood into 8 octants (each quadrant cut again along its diagonal) and keeps only the
nearest point per octant, verified against a brute-force oracle across 20,000 random point sets
(3-60 points each), 0 mismatches. Designed a specific 7-point demo set (not left to random
chance) where a plausible-looking 4-quadrant simplification of the same idea fails outright —
total weight 1160 against the true 1144 — because merging two octants into one quadrant drops a
required edge that neither endpoint proposes from its own side; a 20,000-trial sweep found that
shortcut wrong about 0.5% of the time on average, and a second checked pitfall (ranking octant
candidates by Chebyshev/L∞ distance instead of Manhattan distance itself) wrong about
1.2% of the time. Verified the real shipped demo via a fake-DOM harness driving its actual
candidate-edge-set toggle, not just the standalone stress scripts — all three options' edge
counts (15/21/12) and totals (1144/1144/1160) matched exactly. Updated
choosing-a-minimum-spanning-tree-algorithm.html (ten entries → eleven, new section
+ table row, "six ways" → "seven ways") and bumped "all ten of this site's Minimum Spanning
Trees entries" to "all eleven" on all ten pre-existing MST pages' footer cross-links, plus
randomized-mst.html's own meta description ("other nine" → "other ten"). Zero new CSS — reuses
.kruskal-canvas/.kruskal-node/.kruskal-edge verbatim from
Kruskal's and Euclidean MST.
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 thirteenth Shortest Paths entry, closing a gap 0-1 BFS's own Pitfalls section names and leaves unbuilt: generalizing its two-ended deque to a circular array of C + 1 buckets handles any small bounded-integer edge weight, not just 0 or 1. Verified against a from-scratch Dijkstra reference across 3,000 random grids, zero mismatches. Sizing the bucket buffer to C instead of C + 1 — an easy off-by-one — silently loses nodes 17.2% of the time in random trials; a bucket array is also a net loss once C grows large relative to the graph, measured 3x more total work than a priority queue at C = 500 on the same grid that's a clear win at C = 4.
The twelfth Shortest Paths entry, closing a gap Suurballe's Algorithm's own Pitfalls section names and leaves unbuilt: edge-disjoint paths can still share a vertex. Splits every node but the source and target into an in-copy/out-copy pair joined by a zero-cost edge, so passing through a node and using that node's one edge become the same event — then runs Suurballe's algorithm completely unmodified on the transformed graph. Verified against brute-force enumeration across 3,000 random graphs; splitting the source or target too (a plausible-looking mistake) breaks the algorithm outright in 100% of 5,740 solvable trials.
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 fourteenth dynamic-programming entry, and a second speedup technique rather than a
new subproblem shape — this one narrows a range-split dp[i][j] = min over k of dp[i][k-1] +
dp[k+1][j] + w(i,j) transition from O(n³) to O(n²) by bracketing
the optimal split point between two already-known neighbors. A live Optimal Binary Search Tree
demo measures the real savings (30 of 50 candidate checks on six keywords, growing to 134x fewer
at n=800); a direct test shows the superficially identical-looking Matrix Chain Multiplication
recurrence can't use the same trick (16.7% of split points violate the needed monotonicity).
The site's thirteenth dynamic-programming entry, and the first that isn't a new subproblem
shape at all — a speedup technique for the common dp[i] = min over j<i of dp[j] +
cost(j,i) transition, cutting O(n²) to O(n log n) whenever the
best predecessor never moves backward as i grows. A live demo splits twelve days of
forecast volume into two shift blocks, needing only 41 of the 66 split-point checks a plain scan
would require; a hand-built five-day counterexample shows the trick silently returning a wrong
answer once that monotonicity is dropped — wrong on 86.3% of 20,000 random trials when it's
missing entirely.
The site's twelfth dynamic-programming entry, and the first whose answer isn't read from the table's bottom-right corner: it's read from whichever cell holds the highest value seen anywhere in the table, because a mismatch resets the running count to 0 instead of carrying the better neighbor forward like Longest Common Subsequence does. On the same two strings both pages use as their worked example, that one rule change drops the answer from a 4-character common subsequence to a 2-character common substring — and a 20,000-trial sweep found reading the corner instead wrong 93.7% of the time.
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 twelfth Greedy entry, and the first that asks a frequency question — is there a
candidate with a strict majority of the votes, and if so who — rather than a scheduling or
covering one. One candidate, one counter: a matching vote increments the counter, a mismatching
one decrements it, and a counter that hits zero throws the current guess away and backs a fresh
one. On a 10-vote election where A wins 6-4, the running candidate swings to D, then B (twice),
before A's own votes take over for good at index 5 — only the final candidate means anything,
not any leader along the way. Proof is a cancellation-pair argument, a fifth Tier-1 shape
alongside the guide's existing four: a majority candidate holds more votes than every other
candidate combined, so it can never be fully cancelled away, since every cancelling pair needs
one non-majority vote to trigger. Two checked pitfalls: skipping the required verification pass
reports a majority even when none exists — wrong on 100% of 16,900 no-majority trials (out of
20,000 total), and in 56.7% of those the named candidate isn't even the single most-frequent
vote in the array; and the leftover counter is not the true margin of victory (4 vs. the real
margin of 2 on the demo's own election, and mismatched on 9.7% of 20,000 engineered-majority
trials). Verified against the real shipped demo via a Node vm harness driving the
Step button through both presets and the skip-verification checkbox, exact match to an
independently computed trace. Folded into
Choosing a Greedy Strategy as a new Tier 1
paragraph and table row; bumped "other ten Greedy entries" to "other eleven" on all eleven
pre-existing Greedy pages. Zero new CSS — reuses .dp-table
(.current/.match/.empty/.path.taken)/.dp-result/.dp-stats/.log
verbatim.
The site's eleventh Greedy entry: one machine, jobs with processing times and deadlines, schedule to minimize the worst lateness across all of them. Sort by deadline (earliest first) and run — but the proof is an adjacent-exchange argument, not the single-item substitution every other exact Greedy entry on this site uses: swapping any two adjacent out-of-deadline-order jobs can only help, so a schedule with zero such inversions (sorted by deadline) is optimal. Verified against a brute-force oracle over all orderings on a hand-built 5-job set (max lateness 6, matched by 2 of 120 permutations) via a fake-DOM harness driving the real shipped script through all three ordering rules. Two checked pitfalls: shortest-processing-time-first ignores deadlines entirely and misses the optimum on 84.6% of 20,000 random trials (26 vs. 6 on the default set); least-slack-first looks better-informed but still misses 41.2% of trials (13 vs. 6), because slack conflates a loose-deadline/long job with a tight-deadline/short one that happens to share the same subtraction result.
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).
Twelfth Backtracking entry, and the first where every decision point has exactly two
candidates and neither is ever illegal on its own: at a *, the search can skip it
(zero occurrences) or consume one more repetition and re-ask the same question, an
OR across exactly those two recursive calls rather than a menu of many candidates
to reject or accept. Covers . (any character) and * (zero or more of
the preceding token), anchored so the whole pattern must match the whole string. Verified
against JavaScript's own RegExp as an independent oracle across 30,000 random
pattern/string pairs, 0 mismatches. On the demo's own aab vs. c*a*b,
reaches MATCH in 8 recursive calls (3 accepts, 2 rejects, 2 backtracks) — confirmed via a Node
vm harness driving the real shipped Step button to completion, exact match. Two
pitfalls, both measured: treating * as "one or more" instead of "zero or more"
(dropping the zero-occurrence branch) is wrong on 18.3% of 30,000 random trials, with a
one-character counterexample (s = "b", p = "a*b", true answer
true, buggy answer false); and without memoization, chained
* groups cause genuine exponential blowup, the same root cause behind real-world
ReDoS reports — measured directly with an instrumented call counter, not just asserted: 12
chained a* groups against 12 a's costs 7,904,455 calls, against 16 a's costs
82,317,689, a 10.4× jump from 4 more characters. Folded into
Choosing a Backtracking Strategy as
a ninth problem-solving entry (nine entries plus the same three mechanism/objective/skip
exceptions) and bumped all eleven existing siblings' "other ten" → "other eleven"
cross-references. Zero new CSS — reuses .cells/.cell
(.found/.mid/.discarded)/.cs-caption/.dp-result/.dp-stats/.log
verbatim from this site's existing string-matching and backtracking demos.
Eleventh Backtracking entry, and the first that can assign a variable's value with no trial
at all: before ever guessing, DPLL applies unit propagation (a clause with one
literal left unresolved forces it true) and pure-literal elimination (a variable
appearing with only one sign among unsatisfied clauses can be set to satisfy all of them) —
proven-safe shortcuts, not guesses, something no other entry on this site does even once. Solves
general Boolean satisfiability (three or more literals per clause, NP-complete), the harder
relative of 2-SAT's own linear-time special case. On a
5-variable, 7-clause formula the search reaches SAT in 5 nodes — 2 decisions, 1
backtrack, 2 forced unit propagations, 2 pure-literal assignments — against
52 nodes for plain guess-every-variable backtracking, a 90.4% reduction, with two
variables left honestly unassigned once every clause is already satisfied. Two pitfalls verified:
flipping which value a pure literal gets (the natural "appears only negated, so set it true"
mistake) turns a sound rule into one that reports real satisfiable formulas as UNSATISFIABLE —
34.6% wrong across 20,000 random 6-variable trials, plus a tiny hand-checkable 3-variable
counterexample; checking for unit clauses in a single top-to-bottom sweep instead of looping to a
fixpoint still finds the right answer but needs 7 search nodes instead of 1 on a twelve-variable
forced-implication chain. Fake-DOM harness confirmed the real shipped generator matches this trace
exactly. Added as an eleventh entry to
Choosing a Backtracking Strategy
(a third exception alongside Dancing Links and Branch and Bound) and bumped all ten existing
siblings' "other nine" → "other ten" cross-references. Two new CSS modifiers, both reusing
already-WCAG-verified color pairs: .dp-item.false-val and
.topo-order-chip.found/.contradiction.
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.
The Game Trees category's 12th entry, and a fourth refinement on alpha-beta alongside
Principal Variation Search, MTD(f), and the Killer Move Heuristic — before trying any real
move at a node, skip the turn entirely and probe a reduced-depth search of the opponent's
reply; if that cheap hypothetical already proves the position good enough, prune the whole
branch without ever searching a real move. Checked at scale on an empty-board search: 55.1%
fewer nodes at depth limit 5 with reduction R=3 (803 vs. 1,787), for the identical final
answer. Two checked pitfalls, both real engineering tradeoffs behind the technique's real-world
safeguards: a reduction that lands the probe exactly on the depth cutoff trusts a raw heuristic
guess over any real search and picks a genuinely worse move on a hand-built position (cell 0,
score 9, instead of the true best cell 4, score 12); a reduction too small relative to the
depth budget is a pure performance own-goal, up to 3.9x more nodes than not pruning at all
(80,790 vs. 20,866) without ever becoming wrong. Verified against the real shipped demo via a
Node vm fake-DOM harness across all 24 mode/depth/reduction combinations on the
interactive board — zero errors, always agreeing with plain alpha-beta there. Zero new CSS —
reuses .bfs-grid/.bfs-cell/.dp-stats/.log
verbatim from Minimax and Iterative Deepening.
An 11th Game Trees entry, and the first that doesn't pick a move at all — it proves a position's true value outright by keeping a proof number and disproof number at every node it's touched and always expanding whichever untouched node looks likeliest to finish the proof next. Verified against a brute-force AND/OR oracle across 20,000 random trees (0 mismatches), touching an average of 30.9% of nodes before proving or disproving the root — on this page's own 15-node demo tree, just 5 expansions prove the root, leaving 4 nodes untouched. Two checked pitfalls: swapping the mirror-image OR/AND update formulas returns a flatly wrong verdict 21.0% of the time and hangs outright 64.6% of the time (a 3-node example reports a forced loss despite an available winning move); skipping the walk back to the root after an expansion does all the same correct work, then never notices the proof is already finished two steps earlier.
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.
A thirteenth Network Flow entry, closing the forward reference both Bipartite Matching and Hopcroft-Karp named in their own Pitfalls sections:
general-graph maximum matching, where odd-length cycles break the two-sided distance-parity trick both of
those pages depend on. Contracts any such cycle (a "blossom") into one logical vertex mid-search rather
than needing a separate expansion pass — verified against brute-force maximum matching across 4,534
random graphs (0 mismatches), with a live demo tracing a real five-vertex blossom contracting twice on a
seven-vertex graph, the second time proving no augmenting path exists rather than merely failing to find
one. A genuine measured pitfall: forgetting to reset one bookkeeping array between searches doesn't
degrade the matching, it zeroes it completely (3→0 pairs on the demo graph, reproduced at two larger
scales). Folded into Choosing a Network Flow
Algorithm as a new section and table row; bumped nine sibling pages' stale "other eleven"/"all twelve"
Network Flow counts in the same pass. Zero new CSS — reuses
.kruskal-wrap/.kruskal-canvas/.kruskal-node(.confirmed/.endpoint/.cg0)/.kruskal-edge/.kruskal-stats/.log
verbatim.
A twelfth Network Flow entry, and a fourth path-choice rule fed into Ford-Fulkerson's general method — but bounded by the
capacities' own magnitude instead of the graph's size, the exact fix Minimum-Cost Maximum Flow's own Pitfalls section names
for its cheapest-path-first rule's capacity-dependent augmentation count. Only ever uses an edge whose
residual capacity clears a threshold that halves each phase, starting at the largest power of two no
bigger than the network's biggest capacity. Verified on Ford-Fulkerson's own bridge network, reusing its
identical bridge-preferring path order: that page's own rule needs 2C augmentations as C grows (8 at
C=4, scaling linearly); this page's threshold needs exactly 2, for every C from 4 to 32 — same order,
same graph, same final answer. A second, asymmetric network shows a real correctness pitfall: stopping
one phase early misses a unit of flow only reachable through the low-capacity bridge, landing on 6
instead of the true 7 — a wrong answer, not just a slower one. Verified the shipped demo via a Node
vm harness driving all four scenarios (symmetric at four capacities, asymmetric, and both
deliberately buggy variants) to completion, matching hand-checked numbers exactly. Closes the forward
reference on both ends. Folded into Choosing a Network Flow Algorithm as a new
paragraph in its "Three ways" section (now four) plus a table row; fixed nine sibling pages' stale
"other ten"/"all eleven" Network Flow counts in the same pass. Zero new CSS — reuses
.kruskal-wrap/.kruskal-canvas/.kruskal-node/.kruskal-edge/.kruskal-stats/.log
verbatim from Ford-Fulkerson's own demo.
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.
Fifteenth Number Theory entry, also called Stein's Algorithm: computes the exact same
gcd(a, b) as Euclidean Algorithm, but
replaces every division with bit shifts and subtraction, historically a real win on hardware
with no fast divider. Measured directly against that page's own shipped implementation rather
than assumed: 0 mismatches across 20,000 random trials plus an exhaustive brute-force
cross-check of every pair in [0, 300]², but slower in JavaScript every way tested — 1.4x-1.5x
slower wall-clock on ordinary random input, and 5.6x-7.7x slower on its own theoretical best
case (two numbers sharing a large power of two), since V8's single % instruction
collapses in one step what the shift-based loop walks off one bit at a time. Two checked
pitfalls: the shipped bitwise implementation silently returns a wrong answer above 2³² − 1
(JS's 32-bit bitwise coercion) with no error; forgetting to multiply the extracted power of two
back into the final answer is wrong on exactly 25.0% of pairs (precisely when both inputs are
even). Updated choosing-a-number-theory-algorithm.html (eleven of fourteen entries
funneled → twelve of fifteen, new paragraph + table row) and bumped "other thirteen Number
Theory entries" to "other fourteen" on all eleven pre-existing pages that carry that sentence.
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.
Answers the same question as Floyd's Cycle
Detection — does a functional graph loop, and where — but replaces Floyd's always-moving
second pointer with one that only teleports at power-of-two intervals. The common claim that this
makes Brent's unconditionally faster turns out to be only half true: measuring real
.next dereferences directly (cross-checked against a hash-set walk across 255
tail/cycle combinations first, 0 mismatches) found Brent's ahead by up to 1.65x when the cycle is
short relative to the tail (λ < μ, the shape Pollard's Rho actually produces), but Floyd's
winning outright in 93.5% of cases where the cycle is as long as or longer than the tail (λ ≥ μ) —
a real crossover, not a uniform win. Two verified pitfalls, both unusually loud rather than
silent: forgetting to reset the step counter after a teleport hangs 73.3% of the time across 240
tested tail/cycle combinations instead of just giving a wrong answer, and reusing Floyd's phase-2
trick on Brent's last checkpoint (which isn't a guaranteed meeting point here) hangs 75% of the
time instead.
The site's twelfth Graph Traversal entry, and a direct sequel to Articulation Points and Bridges: the
same discovery-time/low-link bookkeeping, plus an explicit edge stack that pops into one finished
component the instant the identical low[v] ≥ disc[u] inequality fires. Every
bridge turns out to be a component of size one; every articulation point is exactly a vertex
shared by two or more components. A genuine simplification over the sibling page: the popping
test needs no root special-case at all, verified directly on a "bowtie" graph (two triangles
meeting at one shared vertex) where the unmodified reference implementation correctly splits it
into two components with no extra code. Two quantified pitfalls, checked against the reference
implementation across 5,000 random graphs each: tracking the parent by vertex instead of edge
index silently drops one of a pair of parallel edges from the output entirely, not just
mislabels it (74.3% of trials with a duplicate edge present); pushing a back edge from both
endpoints instead of only the ancestor-ward direction lets one edge land in two components at
once, breaking the partition on a perfectly ordinary graph (44.6% of trials). Updated the guide
(eleven → twelve, new paragraph in the existing "undirected failure" question, new table row) and
all eleven existing siblings' "other ten → other eleven" cross-link sentence. Zero new CSS —
reuses .topo-canvas/.topo-node/.topo-edge(.heavy/.bridge-edge),
.dfs-stack, and .topo-order verbatim from Articulation Points and
Bridges and Topological Sort.
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 twelfth entry, and a sixth "different question" — the first one in this category that's genuinely online: points arrive one at a time, in any order, with no full point set known upfront, and the hull has to be correct after every single insertion, not just once at the end. Distinct from Melkman's Algorithm's own one-at-a-time walk, which only works because its points already arrive in simple-polygon order — this page makes no such assumption. Verified against an independent from-scratch oracle across 50,000 randomized insertion sequences, 0 mismatches, hull strictly convex after every single insertion. Two verified pitfalls: patching only the nearest hull vertex instead of finding the whole visible chain of now-obsolete vertices is wrong on 98.0% of 20,000 trials; skipping the check for "is this point already inside" before searching for a chain to remove corrupts the hull on 82.6% of 20,000 trials, and does so silently — no error, no crash, just a wedged-in point that a later, unrelated insertion can coincidentally sweep back out again, erasing the evidence. Folded into Choosing a Convex Hull Algorithm's own "set aside up front" list as a sixth different question.
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 twelfth Geometry entry, and the first whose answer is a shape sized to fit the whole input at once rather than a fact about one point, one pair, or one polygon's interior — the smallest circle containing every point in a set, via Welzl's randomized incremental construction. Every support point is provably a convex hull vertex (0 violations across 3,000 trials). Verified against an O(n⁴) brute-force oracle across 5,000 trials, 0 mismatches, plus degenerate cases (collinear, duplicate, single, and two-point inputs) checked directly. Two pitfalls: skipping the shuffle doesn't break correctness but does break the expected-linear time guarantee it exists for — the same 8 demo points cost 59 inside-checks in a bad order versus 12 in a good one, and a 1,600-point stress test showed the gap widening to 45×; and the tempting "just take the two farthest points as a diameter" shortcut is simply wrong whenever the true answer needs all three support points, failing on 27.7% of random triangles (a clean equilateral triangle example: true radius 5.7735 vs. the shortcut's 5.0000, missing the third vertex by over 70% of its own radius).
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.
The Compression category's sixth entry, and the first that's a pure transform rather than a
standalone compressor — it never shrinks a message by itself, only turns locally-recurring
symbols into a small-number-heavy code stream a follow-on Huffman or RLE pass can crush harder
than the original symbols. Closes the forward reference Burrows-Wheeler Transform's own page left
open since it named bzip2's real pipeline (BWT, then Move-to-Front, then Huffman) without
building the middle step. Measured by Huffman-coding five inputs with and without this transform
first: a real 22-28% cut on inputs with local clustering (including one, a perfectly
flat-frequency string, where Huffman alone gains nothing at all), but one bit worse on
abracadabra — the same shared default example this site's Huffman/RLE/LZW pages
use — because its repeats are real but never close together.
The Compression category's fifth entry, and the first to stack two of the site's own shapes in one format instead of bringing a new one: LZ77's window-bounded substring search (by way of LZSS, the flag-bit variant LZ77's own page names but never builds), then Huffman-coded instead of packed at a fixed width — with no separate flag bit at all, since literals and match lengths share one alphabet. Measured on the same six strings LZ77's own page used: each layer compounds on its own (LZSS roughly halves LZ77's bits, Huffman-coding the result halves it again), but the two Huffman trees this needs cost enough to transmit that full DEFLATE is the worst of all four formats on every short message — and the best by a wide margin (3-6x over LZ77) once the message is long and repetitive enough to amortize two tables instead of one.
The Compression category's fourth entry — a bounded sliding window and lookahead instead of
LZW's unbounded dictionary, and the real mechanism behind
DEFLATE/gzip/PNG. Measured against LZW on the same short strings LZW's own page already used:
the classic always-emit-a-triple format loses to both LZW and doing nothing on short input (e.g.
75 bits vs. LZW's 32 on abracadabra), but wins decisively once matches run long
enough to amortize the per-token tax. A one-character-narrower window can erase a match
completely — verified at 7 tokens vs. 12 (zero compression) on the same 12-character message,
nothing in between.
The Compression category's third entry, and the first to take on Huffman Coding's own turf directly: encodes a whole message as one number by narrowing an interval instead of walking a tree, so a symbol's cost can be fractional instead of rounded up to a whole bit. Measured on a 90%/10% two-symbol message where that matters most: Huffman is forced to spend exactly 1 bit/symbol regardless (20 bits total, verified by running its own reference implementation), arithmetic coding's guaranteed bound costs 11. The flip side, also measured rather than assumed: a naive floating-point implementation silently starts corrupting messages around length 25 (double-precision mantissa bits run out), and fully collapses — two different messages encoding to byte-identical output — on a low-entropy source by symbol 120.
The Compression category's second entry — the simplest idea in it, replacing each maximal run
of a repeated character with one (count, symbol) pair, no dictionary and no shared state for
encoder and decoder to fall out of sync on. Measured head-to-head against
LZW Compression on six real inputs: RLE wins by nearly 4x on one
long uninterrupted run (7 bits vs. LZW's 26), but loses badly — expanding the message instead of
shrinking it — the moment repeats aren't physically adjacent, as on abracadabra, which
LZW compresses and RLE doesn't.
The site's first entry in a new Compression category — Huffman Coding (Greedy) and Burrows–Wheeler Transform (Exact Match) are
both already compression-adjacent but filed elsewhere for their own real reasons; this is the first
entry whose whole subject is building and transmitting a compressed encoding. Builds its dictionary
adaptively from the message itself — no table to transmit, unlike Huffman — by repeatedly extending
a matched string until the extension isn't already known, then emitting a code and adding the
extension as a new entry. A step-through encode demo on the classic textbook example
ABABABABA doubles as the first pitfall: the "5 codes for 9 characters" story sounds
like compression, but packed at the real variable code width each code needs, it costs
11 bits against a 9-bit fixed-width baseline — a verified loss,
not a win, on the input chosen specifically because it's easy to trace by hand. A second verified
pitfall is the decoder's one genuinely ambiguous case: a 20,000-trial fuzz test found zero
round-trip failures, but hit the special-cased "code not in my dictionary yet" branch 28,842
times — not a rare corner, the normal cost of the decoder trailing the encoder's dictionary by
exactly one entry.
The algorithm Peterson's Algorithm simplified: the first published two-process mutual
exclusion solution (1965), using the same flag-and-turn idea but reaching it through an
explicit backoff-and-retry loop instead of one combined check. Exhaustively verified: the full
algorithm holds at 0 violations up to 197 reachable states. Dropping the backoff (and
turn with it) reduces to the most obvious first attempt — and deadlocks in exactly
2 clicks, the same failure shape as Peterson's own flag-only variant, arrived at from the
opposite historical direction. Forgetting to re-raise a flag after backing off is a different,
sharper bug: unlike any broken variant on the other ten Concurrency pages, it breaks mutual
exclusion itself, not just progress — a process can enter the critical section with its own
flag still reading false.
A different kind of Concurrency entry: not mutual exclusion over one critical section, but
n processes each needing two of n shared resources arranged in a
cycle, where a fork is never double-allocated by construction — so the only real question is
liveness, not safety. Exhaustively verified: the naive always-left-first pickup rule deadlocks
at every table size tried (3 through 7), in exactly n moves; Dijkstra's own
resource-hierarchy fix (take the lower-numbered fork first) never does, for a reason that holds
for any n, not just the sizes checked. A tempting third option — alternate pickup
direction by parity — looks like it should only work on an even-sized table, but the exhaustive
search finds it deadlock-free at every size tried too, odd and even alike.
Closes a forward reference Peterson's Algorithm's own page left open: the generalization from
two processes to any fixed number n, using numbered tickets instead of a flag and a
turn. Ticket-taking is modeled as two separate steps (read the current max, then write), not one
atomic assignment — real non-atomicity that lets two processes genuinely tie on the same number.
Exhaustively verified: the full algorithm holds at 0 violations up to 2,013 reachable states;
dropping the id tie-break on a tied ticket lets both processes into the critical section together
(1 violation at the smallest configuration); dropping the choosing flag breaks it a
different, subtler way documented since Lamport's original paper. Neither broken variant ever
deadlocks — the mirror image of Peterson's own two broken variants, which deadlock or starve but
never violate exclusion.
Closes the forward reference the Treiber Stack's own Pitfalls section left open: how to
actually free a popped node's memory without reintroducing the exact ABA corruption that page
demonstrates. Exhaustively verified on the identical two scenarios: publishing a hazard pointer,
re-validating it against a fresh read of head, and deferring reclamation until no
thread's hazard still points at a node drops the Treiber Stack's own 1-in-59 and 3-in-179
corrupting schedules to 0 in both. Publishing without the re-validation step isn't enough — the
identical class of corruption reopens at similar rates (1-in-90, 3-in-299), now producing a
duplicated value and a fully lost one rather than the original bug's own symptom.
One of this site's other three CAS-based Concurrency entries, alongside the Treiber Stack — but a FIFO
queue needs two independently-raced pointers (head and tail) instead
of one, and that's exactly the new hazard a single-pointer structure has no analogue for: tail
can legitimately lag one node behind the real end of the list. Exhaustively verified: the
textbook fix (any thread that notices a lagging tail helps advance it before proceeding) never
once reports a wrong answer, 0 occurrences across every scenario tried. Collapsing dequeue's
head == tail check straight to "empty" — skipping that one help-and-retry step —
reports a phantom empty queue in as few as 4 moves, 2 of 18 reachable states in the minimal
case; no value is ever actually lost or duplicated by the bug, confirmed separately, just
momentarily denied to the one call that asked at the wrong instant.
The site's first entry in a new Concurrency category — every other page assumes one control
flow executing its own steps in order, and this is the first one where an adversarial scheduler is
free to interleave two processes' individual reads and writes in any order. Two shared variables
(a flag per process, plus a turn that breaks the tie) are enough to guarantee mutual
exclusion with no lock and no hardware compare-and-swap. Verified by exhaustively searching every
reachable interleaving of a small state machine rather than asserting the textbook proof holds:
0 mutual-exclusion violations across every configuration tried (up to 194 reachable states).
Dropping turn still never violates mutual exclusion but deadlocks outright — both
processes spin forever — after as little as two clicks; dropping the flags instead never
deadlocks under equal load but can starve one process forever on behalf of another that never
even asks for the resource, a bug exhaustive search finds requires asymmetric demand to expose.
A fourth kind of Concurrency entry: not mutual exclusion, not circular-resource deadlock, and not
starvation, but a two-resource acquisition-order bug. The textbook-correct bounded
buffer (two counting semaphores plus a mutex) never wedges in any configuration tried. Swapping either
role's own first two lines — mutex before the counting semaphore instead of after — makes a real
deadlock reachable, but not equally: the buggy producer only wedges once it attempts more pushes than
the buffer has room for (exactly attempts − capacity), while the buggy consumer wedges on
attempt 1 regardless of buffer size, because an empty buffer — every buffer's starting condition — is
already the trigger.
A third kind of Concurrency entry: not mutual exclusion, and not deadlock (nothing here can get
permanently stuck), but starvation — can one class of request keep getting skipped
forever even while the system as a whole keeps moving? Exhaustively verified: under
readers-preference, the number of readers that cut in front of an already-waiting writer has no
ceiling, measured at exactly readers × attempts-each in every configuration
checked; writers-preference has the mirror failure on the reader side, scaling exactly with the
writer's own attempt budget. A Lamport-bakery-style ticket order closes both at once, holding each
count at exactly 0 across every configuration tried.
The first Concurrency entry built on hardware compare-and-swap rather than plain shared-memory
reads and writes — the primitive this site's own mutual-exclusion guide already measured beating
Peterson's algorithm, but never built anything on top of until now. Exhaustively verified: plain
push/pop over one CAS'd head pointer never corrupts the stack at 0 corrupt states
across every scenario tried, as long as every node identity is permanently fresh (matching real
garbage-collected behavior). Switching to a recycling allocator that hands a freed node's own slot
back out to a later push reproduces the classic ABA problem in the smallest scenario tried: a
stale compare-and-swap succeeds against a slot that was freed and reused, silently losing a push
and double-returning a pop in as few as 8 moves.
Closes a forward reference named on two separate pages: the Treiber Stack's own Pitfalls section and Hazard Pointers' own Pitfalls section each name epoch-based reclamation as the sibling scheme and build neither. Exhaustively verified on the identical scenarios: pinning a thread to the current epoch for its whole operation, then freeing retired nodes only once the global epoch has advanced two full steps past their retirement, holds at 0 corrupt states everywhere. A 1-epoch margin reopens real corruption in both scenarios (1-in-86, 9-in-342); dropping the straggler check that gates when the epoch may advance at all reopens it only in the larger one (7-in-308) — a measurably different fault line, not just a second copy of the same bug. The same gate that buys correctness also measurably holds every node retired since a stalled thread pinned hostage: 1,000 cycles of unrelated work by a healthy thread leaves exactly 1,000 nodes stuck, where Hazard Pointers can only ever block the one id it last published.
The first new CAS-based shape on this site since the Michael-Scott Queue — Hazard Pointers and Epoch-Based Reclamation both retry the Treiber Stack's own push/pop rather than defining a structure of their own. Exhaustively verified: physically unlinking a node from its predecessor without marking it logically deleted first can silently drop a concurrent insert anchored at that exact node — the insert's own CAS succeeds, but a racing delete's stale read overwrites it right back out of the chain, in as few as 4 moves (1 of 12 reachable states in the minimal case). Marking the node's own next pointer before ever touching its predecessor closes this to 0 occurrences across every scenario tried, forcing the insert to fail cleanly and retry instead of vanishing.
The site's tenth Cryptography entry — not Argon2 itself, which bcrypt's own page still names as the one remaining unbuilt
piece, but the hash function Argon2 uses internally for every mixing and finalization step, the
same way PBKDF2 leans on this site's own HMAC-SHA256 rather than reinventing a hash. A genuinely distinct
construction in its own right: 64-bit ARX mixing instead of SHA-256's 32-bit words, a fixed
message-word permutation each round instead of a derived schedule, and keying plus variable
output length built directly into its first block rather than bolted on with a separate nesting
construction the way HMAC needs. A live demo hashes a message
(optionally keyed, at a chosen output length), flips one bit to show the same avalanche property
SHA-256 has, and replays SHA-256's own length-extension
forgery against it — the one-bit finalization flag BLAKE2b's last compression step carries, and
SHA-256's construction lacks entirely, stops the forgery cold. Verified against Python's own
standard-library hashlib.blake2b (no extra install needed) across block-boundary
edge cases, keyed and variable-length cases, and 3,000 randomized trials, 0 mismatches.
The site's ninth Cryptography entry, closing the "memory-hard password hash" forward reference
SHA-256's, HMAC's, and PBKDF2's own Pitfalls sections all name and leave open. Built on a
from-scratch Blowfish cipher and its modified "EksBlowfishSetup" key schedule — every guess rebuilds
roughly 4 KB of internal P-array/S-box state completely from scratch, not just one small running
accumulator the way PBKDF2's chained HMAC calls do. A live demo
hashes a password, a second verifies a password against a stored hash (parsing the cost and salt
straight out of the hash string itself), and a third times the cost factor's doubling live. Verified
against the official Blowfish test vector and against Python's own trusted bcrypt
library across 35 random password/cost/salt combinations, 0 mismatches, before any of it shipped.
Honest about its own limit: the 4 KB footprint is fixed, not independently tunable the way Argon2's
own memory parameter is — named alongside bcrypt on all three forward references, Argon2 remains the
one piece still unbuilt.
The site's eighth Cryptography entry, closing the forward reference Choosing a Cryptographic Primitive's own
"layered" section named and left unbuilt: a real handshake needs, "for the bulk of the actual data,
once a secret is agreed — a fast symmetric cipher this site hasn't built yet." Built from scratch
over GF(2⁸) — this site's first finite-field arithmetic — with the full Rijndael key
schedule, round structure, and MixColumns diffusion step. A live demo encrypts and
decrypts a single 16-byte block; a second demo encrypts two identical plaintext blocks under ECB
and shows the ciphertexts come out byte-for-byte identical every time — the classic "ECB penguin"
pattern leak, reproduced live. Verified against the official FIPS-197 test vector and fuzzed against
Node's own native AES across 5,000 random blocks, 0 mismatches, before any of it shipped.
The site's seventh Cryptography entry, closing the forward reference RSA Encryption's own Pitfalls section named and left
unbuilt: "real deployments pad the message (OAEP) before encrypting" so textbook RSA's
determinism and multiplicative structure never reach a real ciphertext. Built entirely from this
site's own SHA-256 via MGF1 (two chained mask-generation
rounds, nothing new under the hood) plus a real BigInt RSA keygen — Miller–Rabin-tested ~448-bit
primes, far bigger than RSA Encryption's own toy n = 3,233, generated live in the
browser in under a second. A live demo encrypts the same message twice and shows two completely
different ciphertexts every time; a second demo flips one bit of a valid ciphertext and shows
decryption fail with the exact same generic "decoding error" regardless of which internal check
actually broke — the fix for a real padding-oracle attack (Manger, 2001), not a missing detail.
Verified in both directions against Node's own native OAEP implementation before any of it
shipped.
The site's first entry in a new Cryptography category, built entirely out of two Number Theory entries already here: Modular Exponentiation for the forward direction, Baby-Step Giant-Step for why reversing it is hard. Two people agree on a shared secret over a channel anyone can listen to, by each combining the other's public value with their own private one. Demonstrated, not just explained: at this page's deliberately tiny modulus, Eve — who only ever sees the public values, never either secret — cracks all 441 possible secret pairs using the exact same baby-step giant-step search as that other page, every time, in at most 5 giant steps, which is exactly why real deployments use primes with hundreds of digits instead of two.
The site's second Cryptography entry, and the first built entirely out of four pages that already named it as their own real-world motivation without ever linking to it: Modular Exponentiation (encrypt/decrypt), Extended Euclidean (deriving the private key), Miller–Rabin (generating real-sized primes), Pollard's Rho (an attacker factoring a key that's too small). A live keygen/encrypt/decrypt demo, then Eve — who sees only the public key and the ciphertext, never the private exponent — factors a toy modulus herself with the exact same tortoise-and-hare search Pollard's Rho's own demo already runs, recovering the original message every time.
The site's third Cryptography entry, and the first with no key or trapdoor at all — a
cryptographic hash function, built bit-by-bit in plain JavaScript (padding, message schedule,
64-round compression) and checked live on every keystroke against the browser's own
crypto.subtle. A one-bit flip changes roughly half the 256 output bits, measured
live, not just asserted. The Pitfalls section runs a real length-extension forgery: given only a
published hash and a secret's byte length — never its contents — it builds a second hash that's
provably valid for the secret plus attacker-chosen data appended to it, the exact structural
weakness that makes naive keyed hashing unsafe as a MAC.
The site's fourth Cryptography entry — the fix for the exact weakness
SHA-256's own Pitfalls section demonstrated: nesting the hash
with a secret key through two fixed padding constants (ipad/opad) so that
a published tag is never a resumable internal state. Built on top of this site's own SHA-256
primitives rather than a new hash. The live demo runs the identical length-extension forgery that
broke naive SHA-256(secret‖message) on SHA-256's own page, against HMAC's tag instead
— and shows it fail, with the forged and true values computed and compared live rather than just
asserted to differ.
The site's fifth Cryptography entry, closing the forward reference Diffie–Hellman Key Exchange's own Pitfalls
section left named but unbuilt: "certificates, digital signatures" layered on top of a key
exchange for real authentication. Built by reusing RSA Encryption's own keygen/
modpow/modinv verbatim, with the two exponents' roles reversed — signing
applies the private exponent first, verifying applies the public one. A live demo signs and
verifies a message, with both the message and the signature independently editable so a visitor
can watch tampering with either one fail. A second demo forges a valid signature for the product
of two messages by multiplying their real signatures together — no private key, no factoring —
exactly the multiplicative shortcut a raw, unhashed signature scheme can't prevent, then shows the
identical trick fail once hashing is interposed.
The site's sixth Cryptography entry, closing the "deliberately slow, salted key-derivation function" forward reference SHA-256's and HMAC's own Pitfalls sections both left named but unbuilt. Chains this site's own HMAC-SHA256 thousands of times rather than defining anything new, making the repeat count the entire security knob. A live demo derives a key on click (not on every keystroke — it's slow on purpose) and measures its own elapsed time growing with the iteration count; a second demo derives the same password under three different salts to show why a unique salt per record, not secrecy, is what defeats precomputed tables. Honest about its own limit: PBKDF2 is time-hard but not memory-hard, the real reason bcrypt and Argon2 — named but still not built here — exist as stronger alternatives against parallel cracking hardware.
The category's third entry, and the first that doesn't count bits — it finds one. Answers a
different question than its siblings: given a nonzero 32-bit integer, which bit is the lowest
one set (count trailing zeros)? A de Bruijn sequence turns that into a fixed four-step
lookup instead of a shift-until-odd loop. Measured (Node, 3,000,000 random 32-bit integers per
pattern, warm-up plus median-of-9 trials, averaged across 3 runs): the naive loop swings nearly
3x between input patterns, the de Bruijn version at most 1.4x. Three verified bugs: skipping the
lowest-bit isolation step is wrong on 96.88% of random inputs; n = 0 silently
returns 0 instead of 32 without an explicit guard; using a signed shift instead of an unsigned
one returns undefined on 2.93% of inputs.
The site's first entry in a new Bit Manipulation category: counting an integer's set bits by
repeatedly clearing the lowest one, n & (n - 1), instead of checking all 32
positions. Measured directly (Node, 3,000,000 random 32-bit integers, warm-up passes plus
median-of-9 alternated trials): Kernighan's own worst case is still 35% faster than the naive
scan despite running the identical 32 iterations, and the naive scan's own time swings 2.6–3.3x
between predictable and random bit patterns running the exact same fixed iteration count — branch
prediction, not big-O, explains the gap. A precomputed byte lookup table beats both. Also
demonstrates a real correctness bug: guarding the loop with x > 0 instead of
x !== 0 silently undercounts 49.9% of random 32-bit integers, because JavaScript's
& operator re-signs its result every time.
Same population-count problem as Brian Kernighan's Algorithm, solved by a structurally different mechanism: five fixed shift-mask-add steps fold 32 one-bit lanes into one 32-bit answer, no loop over bits and no memory table. Measured (same methodology as Kernighan's own page, averaged across 4 independent runs): flat across every input pattern like the lookup table, but trailing it by 3–6% rather than overtaking it — still 2.3x faster than Kernighan's algorithm on uniform random bits. Also demonstrates a real correctness bug: masking only the shifted operand and not the unshifted one corrupts 92.5% of random 32-bit integers.
The 12th Disjoint Set entry, picked by category balance — Disjoint Set was the sole category
still at eleven while every other category had reached twelve. A seventh application built on
top of plain Union-Find, and the first one to redefine what find's own parent
pointer means rather than build unchanged on top of it: force every union to point toward larger
indices only, never the reverse, and the same walk-and-compress find answers "what's
the next available slot at or after this one?" instead of "same group?" — with the forced
direction doing union-by-rank's job, since there's no longer a balance decision to make. Verified
against an independent linear-scan oracle across 30,000 random occupy/query sequences, 0
mismatches. Argued and then measured why path compression alone is enough here even though the
textbook "compression alone" bound is only O(log n) amortized: every
occupy attaches one brand-new singleton onto an already-resolved chain, never merges
two populated trees the way an adversarial general Union-Find sequence could — occupying
n = 1,000 up to 1,000,000 slots costs a flat ~1 hop per operation at every scale
tested, under both random order and an order specifically built to defeat compression, no
log² n growth trend at all. Three measured pitfalls: reversing the union
direction looks identical and never crashes, but answers wrong on 99.97% of 30,000 random trials
(returns an already-taken slot as available); skipping the sentinel slot leaves the last real slot
lying about its own availability 100% of the time it's tested; dropping path compression stays
correct but the whole benefit evaporates, measured directly (100/1,000/10,000/100,000-slot runs,
the compression-vs-not gap climbing from 33.6× to a flat 50× — exactly the number of
repeat queries in the test). Verified the real shipped demo via a Node vm fake-DOM
harness driving the actual Occupy/Next Available/Step buttons, checking parent-array state and
node classes at each step, not just the final log line. Folded into Choosing a Union-Find Variant as a seventh
application ("six more"/"all six" → "seven more"/"all seven", "the eleventh, Partition
Refinement" → "the twelfth") and cross-linked from Union-Find's own Pitfalls section as a new
"redefining parent" extension. Zero new CSS classes beyond two trivial reuses: .occupied
is the same --danger/--danger-soft pair as .uf-node.contradiction
(already WCAG-verified), .sentinel is a border-style-only marker with no color at
all — otherwise reuses .uf-wrap/.uf-canvas/.uf-node(.root/.onpath/.found-root/.selected-a)/.uf-edges/.uf-edge(.onpath/.new)/.uf-sets/.uf-set-chip
verbatim from Union-Find's own family, laid out in a horizontal row instead of a circle with
parent pointers drawn as arcs that visibly collapse when compression fires.
Eleventh Disjoint Set entry, a sixth application built on top of Union-Find — picked while
rereading the category for a genuine gap rather than by balance alone (Disjoint Set and
Non-Comparison Sorts were tied at ten). Two virtual nodes turn "does this n×n grid
of open/blocked sites connect top to bottom?" into one find comparison instead of an
O(n²) flood fill per query — the first entry in this category whose real engineering
problem sits on the query side rather than the union side. Verified the demo's own witness-path
highlight and percolation detection via a Node vm harness driving the real shipped
script (Step/Run/Reset), confirming Run always auto-stops at the exact step percolation first
fires and Step still works past that point for exploration. Two measured pitfalls: reusing one
Union-Find structure (with both virtual nodes) to answer both percolates() and
per-site isFull() queries — the classic "backwash" bug — reports open sites merely
touching the bottom row as full whether or not they have a real path to the top, wrong in 79.5%
of 20,000 random-run trials at the moment of first percolation (8.80% of individual open-site
checks); a hand-checkable 4×4 example isolates one falsely-full site with no real neighbors at
all. Second: 8-directional (diagonal) adjacency instead of the correct 4-directional model isn't
a bookkeeping bug — both graphs get answered correctly — but it changes the physical answer, an
80×80/1,000-trial average of 40.75% open at percolation against 59.21% for 4-directional,
matching the commonly cited literature constants for each model (≈40.73%/≈59.27%).
Folded into Choosing a Union-Find
Variant as a sixth application (new paragraph, "five more"/"all five" → "six more"/"all
six", "the tenth, Partition Refinement" → "the eleventh"). Zero new CSS — reuses
.bfs-grid/.bfs-cell (blocked/open/full via the existing
wall/w3/w0 classes) and .kruskal-stats
verbatim.
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.
LRU Cache's near neighbor, betting on total popularity instead of recency: evict whoever's been touched the fewest times overall, breaking ties by recency only among whoever shares that minimum. Needs one doubly linked list per frequency value instead of LRU's single chain, plus a plain integer tracking the current lowest frequency in use. The interactive demo renders every frequency bucket directly and highlights the real next-eviction candidate; a measured race shows the naive "scan everything for the minimum" approach falling further behind the real O(1) structure as capacity grows — 8.5x at 200, 208.5x at 5,000.
Perfect Hashing's own forward reference, closed: same fixed-key-set, O(1)-worst-case-get guarantee, but packing keys into close to n slots instead of 3-5x by processing buckets largest-first and giving each one its own displacement value into one shared table. Verified against the identical 3,000-trial protocol Perfect Hashing's own page uses: 1.26x average space (never worse than 1.40x) versus that page's 3.27x/4.67x. Two pitfalls found and measured: processing buckets in any order but largest-first isn't just slower (3.1x more displacement draws on average) but risks the build never converging at all (0.5% of trials); skipping the check for two keys in the same bucket landing on the same slot doesn't fail the build, it silently drops one of them (3.82% of keys across 2,000 trials), smallest example a two-key table where one key vanishes without any error.
Consistent Hashing's own forward reference, closed: hash each server onto many ring positions
instead of one, so the law of large numbers averages away the load imbalance a single random
position can cause. Found a real pitfall in the obvious way to generate those extra positions —
hashing name + "#" + i through this site's simple fold hash produces two tight
clusters of ten consecutive positions instead of twenty spread-out ones, leaving one node owning
half the ring even at K=20. An iterative rehash (feed the whole previous hash back in, not just a
trailing digit) fixes it, verified against 300 randomized trials. A second checked pitfall:
removing a node has to delete all K of its positions, not just one — deleting one leaves 90.6% of
that node's former keys still routed to a node that's supposed to be gone.
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.
A different idea from the same family as the binary
heap, Fenwick tree, and segment tree's implicit-array trick: instead of
placing a complete binary tree's nodes by the free 2i+1/2i+2
arithmetic, recursively group each subtree's nodes into contiguous memory blocks, so a search
touches only O(log_B n) blocks for any block size B —
without the algorithm ever being told what B is. Named after, but structurally
unrelated to, this site's own Van Emde Boas
Tree. Measured the textbook claim directly instead of asserting it: built both layouts
(plus plain sorted-array binary search) as flat Int32Arrays and benchmarked real
search time from 16,383 up to 67,108,863 nodes, self-tested against an exhaustive scan first
(0 mismatches). The plain heap layout won at every single size tested, by a widening
1.2×-2.4× margin that never closes — the opposite of the theoretical result,
most likely because this layout's explicit child pointers, at 4× the memory per node,
cost more in extra memory traffic than the construction saves in distinct blocks touched, at
least in a garbage-collected, JIT-compiled runtime. Reported the reversal honestly rather than
only the measurement that would have confirmed the textbook story.
Closes Wavelet Tree's own deferred forward
reference: the piece that gets rank-on-a-bit-array down from that page's own
O(n)-extra-ints-per-level reference implementation to true o(n) extra
bits, without giving up O(1) query. The trick, the same shape as ±1 RMQ's own per-shape table: a block of size
b has only 2^b possible bit patterns, so one precomputed
popcount-prefix table per pattern answers every within-block rank in O(1), shared
across every block with that pattern; two levels of prefix sums (absolute per superblock,
relative per block) turn "which block" into array indexing instead of accumulation.
select1 reuses the same tables but has to binary-search for its answer instead of
computing it directly, landing at O(log n) — a real, known asymmetry with
rank1, not a gap in this implementation. Verified two ways: the exact shipped
reference snippet against an independent naive scan across 532,405 randomized rank/select
trials (0 mismatches), and the real demo's own script, driven through every valid rank1 and
select1 query on its 32-bit example via a Node vm harness, matching a naive scan
on all 50 (0 mismatches). Two measured pitfalls: answering a block's rank from
superRank alone, skipping the within-superblock term, wrong 62.5% of the time
(37,525 of 60,000 trials); and a strict-vs-non-strict off-by-one in select1's
binary search, wrong 22.1% of the time (83,289 of 376,029 trials) whenever a query lands
exactly on a superblock boundary's cumulative count.
Closes Cartesian Tree's own deferred forward
reference: the piece that gets an Euler-tour-of-depths array — one that steps by exactly
±1 between consecutive values — down from Sparse Table's O(n log n) build to a
true O(n), without giving up the O(1) query. The trick: a block of size
b has only 2^(b−1) possible up/down shapes, so one precomputed argmin
table per shape answers every within-block query, shared across every block with that shape;
across-block queries reduce to Sparse Table's own class, unmodified, run over the blocks'
minimums instead of the raw array. Verified two ways: the exact shipped reference snippet against
an independent naive scan across 2.65 million randomized queries (0 mismatches), and the real
demo's own script, driven through all 105 possible ranges of its 14-element example via a Node
vm harness, matching a naive scan on every one. One measured pitfall: answering a
query that lands entirely inside one block with that block's overall minimum, ignoring the
query's own start/end offsets, is wrong 44.8% of the time (8,456 of 18,870 trials) — the
same-block case has to route through the shape lookup like every other case, there's no
shortcut just because the query stays inside one block.
The natural next question after Mo's Algorithm:
what if the array can change through point updates interleaved among the queries, as long as
the whole batch is still known up front? Add a third sort key — time, how many updates preceded
each query — and the same one-element-at-a-time window discipline now also fast-forwards or
rewinds through updates. Two verified pitfalls: the block width has to be n^(2/3),
not plain Mo's Algorithm's √n (1.60-1.83× more pointer/time movement measured at
1,000-2,000 elements otherwise, still correct either way); and an update's write to the array
must happen unconditionally, not only when its position sits inside the current window — 22.7%
of 20,000 randomized trials wrong when that write is skipped, smallest hand-checkable case a
6-element array with one update and two queries.
Adds one layer of indirection on top of X-Fast Trie: split the stored values into small sorted buckets, and build the trie over only each bucket's own maximum (its "representative") instead of every value directly — shrinking space from X-Fast Trie's O(n log U) down to O(n) while keeping the identical O(log log U) expected query time. Needed a capability X-Fast Trie's own page never built — delete — since a bucket's representative has to be removed and replaced whenever its maximum changes; verified on its own first (96,000-1,152,000 point-checks across three universe sizes, 0 mismatches) before wiring it into the bucket layer, then the whole structure re-verified the same way (0 mismatches across 1,632,000 more point-checks) and again against the actual shipped demo via a fake-DOM harness (28,000 checks, 0 real mismatches). Measured, not just argued: at n=2,000 over a 16-bit universe, a plain X-Fast Trie needs 13,472 hash-table node entries against this structure's 3,014 — a 4.47× reduction. Two checked pitfalls: letting a bucket's representative go stale when its maximum changes, wrong 49.1%-49.6% of the time; and routing a query to the representative at or below x instead of at or above it, wrong 72.7%-85.8% of the time.
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.
Thirteenth Probabilistic entry, and the first that isn't a stream summarizer, a balanced-tree
alternative, or a similarity estimator: given a whole, already-known, in-memory array, produce
one uniformly random permutation of it in a single O(n) pass. Durstenfeld's 1964 in-place
reformulation of Fisher and Yates's 1938 method. Verified in Node before any prose was written
(exact shipped demo trace reproduced standalone; a 600,000-trial sweep at n=3 landed every
permutation within 0.001 of the true 1/6). Pitfalls demo lets a visitor run the comparison live:
the widely-copied "draw from the full range every step" bug is skewed by an exact, provable
amount at n=3 (4/27 and 5/27 against the true 1/6 — since 3^3=27 isn't a multiple of 3!=6, no
implementation can ever fix it), and array.sort(() => Math.random() - 0.5) is far
worse still, measured at 37.5% for the identity permutation alone against a correct 16.7% in this
site's own V8/Node environment. Added alongside Alias Method in Choosing a Probabilistic Structure
(twelve entries → thirteen) as the second of two one-shot questions over a whole known
collection, rather than a new standalone outlier.
Twelfth Probabilistic entry, and a head-to-head pair with Locality-Sensitive Hashing rather
than a new standalone question: both estimate similarity between items instead of asking about
one item alone, but LSH signs sets for Jaccard similarity while SimHash signs
weighted vectors for cosine similarity. Charikar's 2002 random-hyperplane trick:
hash each present feature to b pseudo-random sign bits, scale by its own weight, accumulate,
and take the sign of each of the b slots as the fingerprint — Hamming distance between two
fingerprints estimates the angle, and therefore the cosine, between the original vectors, with
no need to ever compare the vectors themselves. Verified against a from-scratch cosine-similarity
oracle on the same eight documents LSH's own page uses (reused as weighted word-count vectors):
fingerprint estimates land within a few hundredths of true cosine on the near-duplicate pairs,
and a 300-seed sweep confirms error tracks the expected 1/√b curve (0.350 at b=8 down to
0.050 at b=512). Two measured pitfalls: dropping per-feature weights (collapsing to plain
set-membership) costs roughly 1.8x the estimate error specifically on the pairs where weight
differences are the whole signal (0.048 vs. 0.086 mean absolute error, averaged over 300 seeds);
too few fingerprint bits is a real, unavoidable accuracy trade, not a rounding error. Also found
and fixed a real pre-existing bug while building this: LSH's own pairwise signature table added
a found class to matching slots with no CSS rule anywhere to style it, so matches
never actually highlighted — fixed by reusing the already-WCAG-verified .cell.found
green. Restructured Choosing a
Probabilistic Structure to pair LSH and SimHash as a third head-to-head family (eleven
entries → twelve) instead of leaving LSH as a standalone entry.
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.
Where B-tree commits to one fixed, in-place location per key, this structure refuses to ever write in place: writes (and deletes) land in an in-memory memtable, which flushes as one sequential sorted run once full, stacked above every older run. Two measured pitfalls, both against the exact shipped class: read cost grows unboundedly with every unmerged run — 2,000 keys at a 50-write flush threshold produce 40 runs, costing an absent-key lookup all 41 stops every time and a present-key lookup 21.4 on average, both collapsing to exactly 2 after one full compaction (10.7×/20.5× fewer stops); and a tombstone dropped by anything less than a full compaction can let a deleted key resurface from an older, un-merged run — reproduced deterministically in two writes, then fuzzed against a ground-truth oracle across 20,000 random trials (9.3% wrong under an always-drop policy, 0% under a depth-aware fix that only drops when the merge reaches every existing run).
Rope's own Pitfalls section measured a real problem (one-character-at-a-time edits degrade a
1,000-character rope from depth 9 to depth 1,000) and named its fix without building it: a
Fibonacci-sequence-based height bound from the original Boehm/Atkinson/Plass 1995 paper. This page
builds it — collect every leaf in order, then carry-merge them through an array of Fibonacci-sized
buckets, the same "merge anything sharing a bucket" trick this site's own Fibonacci Heap page uses
in its consolidate() step, just keyed by length instead of degree. Verified against a
plain-string oracle two ways: 2,000 pathologically-built random strings rebalanced back to their
original text (0 mismatches), and 2,000 more put through 5-24 interleaved insert/delete operations
with a rebalance fired after roughly 30% of them (0 mismatches, ~29,000 operations total). Depth
reduction measured across ten sizes from 50 to 10,000 characters: rebalanced depth averages
1.27× the tight theoretical bound (range 1.11×-1.52×), against a pathological
depth that's always exactly equal to the character count. Two pitfalls, both concrete: swapping the
carry-merge's concatenation order (a one-argument-order slip) corrupts text in 500/500 trials
(100%) — never crashes, always silently wrong, e.g. "the quick brown fox" rebalances
to " nworb kciuq ehtofx"; and calling rebalance unconditionally after every edit
instead of gating it behind the cheap isBalanced check throws away the parent page's
own measured near-total structural sharing (a targeted insert into a 1,023-node tree creates 3 new
nodes normally, 513 with unconditional rebalancing). Verified the real shipped demo via a Node
vm fake-DOM harness driving Degenerate-build/Rebalance clicks across 300 random
strings (0 mismatches). Zero new CSS — reuses .bst-wrap/.bst-canvas/
.bst-node.rope-leaf/.rope-internal/.created verbatim from
Rope's own demo.
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 303rd page and 12th Linear entry: the first built around a moving cursor
rather than indexed access, the two ends, or a caller-held reference. One array split into a
before-cursor segment, an unused gap, and an after-cursor segment — typing writes into the gap
at O(1), moving the cursor slides the gap one cell at a time at O(1) per step, O(distance)
total. Verified against a plain string-splice model over 1,000,000 randomized operations (0
mismatches), then re-verified the shipped demo's real script the same way via a fake-DOM
harness (3,000 simulated clicks, 0 mismatches). Two pitfalls with concrete, hand-traced
examples: porting Dynamic Array's amortized-doubling grow() verbatim (extend
capacity at the end, one segment) instead of relocating the after-cursor segment to the new
array's tail drops it silently on every growth event where the cursor isn't at the very end
(100% of 7,218 such events across 3,000 stress trials, "abcd" → move left twice →
insert → "abX" instead of "abXcd"); skipping the
moveLeft/moveRight bounds check at either edge sends the gap's index
negative or past capacity, silently swallowing exactly one keystroke into a stray non-array
property before the structure "self-heals" (100% and 99.8% of 2,478 and 7,288 unguarded calls
across the same trials). Added a fifth exception to Choosing a Linear Data Structure.
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 thirteenth Spatial entry, and Quadtree's
direct 3D generalization: split a cube into eight equal octants instead of a square into four
quadrants, same fixed-center, decide-before-looking-at-the-data trade. The build + range-query demo
renders nested wireframe cubes in an isometric projection rather than flat rectangles. The same
max-depth-guard bug Quadtree's own Pitfalls measures carries over unchanged: 500 inserts of one exact
duplicate coordinate, capacity 3, no depth guard — insert() reports 3 successes, box
width underflows past 64-bit float precision at depth 55, and the finished tree
actually holds zero of those points. With the guard back (depth 8): all 500 succeed
and all 500 are stored, just piled into one leaf instead of spread across eight. Range-query pruning
checked against a brute-force oracle over 5,000 random trials in 3D: zero mismatches.
The site's twelfth Spatial entry, and the fix Hilbert Curve's own Pitfalls section named and deliberately left unbuilt: instead of scanning one naive corner-to-corner index window (measured there to miss 84.6% of tested rectangles' real matches), recursively decompose the query rectangle into exact quadrant-aligned curve-index ranges — every axis-aligned, power-of-two-sized square sub-region of a Hilbert curve is always a contiguous block of indices, the same fact Z-order Curve leans on for its own (narrower) trick. Verified against a brute-force oracle over 20,000 random rectangles on a 32×32 domain (0 mismatches) plus an exhaustive sweep of all 1,296 rectangles on an 8×8 grid (also 0 mismatches). On this page's own 16×16 demo — the identical points and rectangle as its parent page — it finds all three real matches, including the point the naive trick missed, while scanning fewer indices than that broken trick did (48 vs. 117) with zero false positives, merging 9 raw quadrant ranges down to 5. Two verified pitfalls: an inclusive/exclusive off-by-one that never misses a real match but quietly reintroduces false positives (63 indices instead of 48 on this page's own demo, wrong 99.4% of 20,000 random trials); and a bounding-box shortcut that assumes an edge vector is always axis-pure, which drops the exact same point the naive trick missed, for a completely different reason (wrong 97.0% of 20,000 random trials, missing 382,699 real matches in total).
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 fourteen 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 thirteen Shortest Paths entries, organized by the questions that decide between them — edge weights restricted to 0/1? small bounded integers? negative edges? one source, all pairs, K paths, a disjoint pair, or a vertex-disjoint pair? a heuristic available, and are there coordinates to build one from? is A*'s own memory the constraint? — 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 twelve Comparison Sorts entries, 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, and a live in-browser race across all twelve, timed on the same array.
A cross-cutting comparison across ten of the site's sixteen Exact Match entries — KMP, Aho-Corasick, Rabin-Karp, Boyer-Moore, Boyer-Moore-Horspool, Z-Algorithm, Suffix Array, Suffix Tree, Suffix Automaton, and FM-Index — 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, with Manacher's Algorithm and Burrows-Wheeler Transform set aside as answering different questions entirely and Galil's Rule, Suffix Array Construction (Prefix Doubling), and Suffix Array Induced Sorting (SA-IS) each covered as a refinement rather than an eleventh, twelfth, and thirteenth path, plus a side-by-side table of complexity and failure modes.
A cross-cutting comparison across all twelve 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 and Golden-Section Search, Quickselect, and Binary Search on Answer, which answer different questions (a unimodal peak, answered two different ways; 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 twelve Non-Comparison Sorts entries, organized by key type (string, continuous, or integer) and range rather than by algorithm name — including LSD vs. MSD string sort's fixed-width-or-not fork, MSD vs. three-way radix quicksort's alphabet-size fork, 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 twelve Minimum Spanning Trees entries, splitting first on whether seven of them (Kruskal's, Prim's, Borůvka's, Reverse-Delete, Euclidean MST, Manhattan MST, and Randomized MST) are even competing for the same job — they build the identical tree by seven different mechanisms, two only for points in the plane (each under its own distance metric) and one trading a logarithm for randomness — before the other five turn out to answer a different question (bottleneck instead of total, next-cheapest instead of cheapest, verifying a candidate instead of building one, connecting only some of the nodes, or dropping the assumption that edges work both ways) entirely, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across all thirteen Network Flow entries, splitting first on whether five of them (Ford-Fulkerson, Edmonds-Karp, Dinic's, Push-Relabel, Capacity Scaling) are even competing for the same job — they compute the identical max flow, the last four by four different path-choice rules 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 twelve 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, across eight real answers to "what should I play" (including Null Move Pruning, the newest) — 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 ninth, tenth, and eleventh way to pick a move, and Proof-Number Search apart again as a twelfth entry answering a different question entirely — can this position be proven, not what move is best — plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across six of the site's twelve 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 six are set aside up front as six genuinely different questions instead of a seventh through twelfth way to answer this one.
A cross-cutting comparison across six of the site's twenty Array-Backed Trees entries (Binary Heap, Mo's Algorithm, Mo's Algorithm with Updates, Van Emde Boas Tree, X-Fast Trie, Y-Fast Trie, Wavelet Tree, and others 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 site's twelve 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, Offline Dynamic Connectivity, Randomized Kruskal's Maze Generation, Percolation, and Union-Find for Next Available Slot set aside as applications built on Union-Find rather than alternatives to it, and Partition Refinement set aside as an eighth 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 seven of the site's twenty-five Node-Linked Trees entries — Binary Search Tree, AVL Tree, Red-Black Tree, Splay Tree, Scapegoat Tree, B-Tree, and B+ Tree — with the other eighteen (Trie and its own prefix-search family among them) set aside as answering a different question entirely, 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 four of the site's fourteen Hash-Based entries — Hash Table (chaining), Cuckoo Hashing, Robin Hood Hashing, and Hopscotch Hashing — the only four that answer the same collision-resolution question, with Consistent Hashing, Virtual Nodes, Bloom Filter, LRU Cache, LFU Cache, Extendible Hashing, Perfect Hashing, Minimal 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 seven of the site's twelve Linear entries — Dynamic Array, Linked List, Doubly Linked List, Stack, Queue, Circular Buffer, and Deque — organized as a four-question funnel rather than a flat table, since Stack/Queue/Circular Buffer/Deque 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, with Monotonic Stack and Monotonic Deque set aside as techniques layered on top rather than competing storage shapes, XOR Linked List set aside for needing a real address to XOR, Sparse Set set aside as answering a membership question, not a sequence-storage one, and Gap Buffer set aside as built around a moving cursor rather than any of the funnel's four questions, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting guide across twelve of the site's fifteen Number Theory entries — Karatsuba Multiplication, Toom-Cook Multiplication, and Fast Fourier Transform sit a layer below the rest, speeding up the multiplications the other twelve treat as a cheap step, and are set aside — organized by what you actually have in hand (two numbers, one primality candidate, a known composite, a bound, an exponentiation, a square root to recover, an exponent to recover, a binomial coefficient mod a prime, or a system of congruences) rather than by algorithm name, tracing the reuse chains underneath — Extended Euclidean feeds Chinese Remainder Theorem, Modular Exponentiation feeds Miller–Rabin, the Fermat inverse shortcut, Tonelli–Shanks, Baby-Step Giant-Step, and Lucas' Theorem — plus a side-by-side table.
A cross-cutting guide across the site's thirteen Probabilistic entries, split by three independent questions rather than one flat table: a randomized alternative to a rotation-based balanced tree (Skip List vs. Treap), a fixed-memory summary of an unbounded stream (Bloom Filter, Cuckoo Filter, XOR Filter, Count-Min Sketch, Count Sketch, HyperLogLog, Reservoir Sampling, and Morris Counter), or estimating similarity between items (Locality-Sensitive Hashing's MinHash for sets vs. SimHash for weighted vectors) — plus the Alias Method standing alone, answering a fourth, unrelated question: repeated weighted sampling from a fixed distribution.
A cross-cutting comparison across twelve of the site's thirteen Dynamic Programming entries, organized as a ten-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 (and whether the shared run must stay contiguous), one contiguous range split at a point, a shared depleting capacity or a positional/temporal compatibility, single-use vs. reusable items, 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. The thirteenth, Divide and Conquer DP Optimization, is set aside as a speedup technique rather than a new subproblem shape.
A cross-cutting comparison across all thirteen Graph Traversal entries — BFS, Bidirectional Search, Iterative Deepening DFS, DFS, Topological Sort, Strongly Connected Components (Tarjan's and Kosaraju's algorithms), Articulation Points and Bridges, Biconnected Components, Eulerian Path, 2-SAT, Floyd's Cycle Detection, and Brent's Cycle Detection — organized around what each layers on top of plain DFS, with Eulerian Path, 2-SAT, and the two cycle-detection entries set apart as the four that aren't a DFS extension at all: Eulerian Path covers edges instead of vertices, 2-SAT doesn't start from a graph, and neither cycle-detection entry uses a stack, queue, or visited set of any kind, plus a side-by-side table of complexity and when to reach for each.
A cross-cutting comparison across eight of the site's thirteen 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 and its own Range Decomposition entry aren't folded into the comparison either.
A cross-cutting comparison across all twelve Geometry entries — one that had gone without a guide the longest — organized by four genuinely different questions (is a point inside a polygon, do segments cross, what structure describes a whole point set or polygon interior, what's the smallest shape that fits around everything at once) 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 twelve Greedy entries — unlike every other guide, these twelve 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, plus Interval Partitioning's lower-bound/upper-bound match, Stable Matching's no-wasted-proposal argument, Minimizing Maximum Lateness's adjacent-swap argument, and Boyer–Moore Majority Vote's cancellation-pair argument — nine entries total, each a genuinely different proof shape), 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 twelve problem-solving Backtracking entries — like Greedy, these twelve 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 three entries that don't share that shape at all: Dancing Links (changes the undo mechanism itself), Branch and Bound (searches for the best answer, not any valid one), and DPLL (can assign a variable with no trial at all, via unit propagation and pure-literal elimination).
Not a per-category comparison like the other guides — a standalone reference tool
translating Big-O notation into real numbers. Drag n from ten to a billion and
watch a live log-scale bar chart and wall-clock-time readout for seven classes from
O(1) through O(n³), then a second widget showing why
O(2ⁿ) and O(n!) hit a wall by n = 50-100 rather than just slowing
down, plus a static reference table and one hand-verified example of each class already live
on this site.
Another standalone reference tool, not a per-category comparison: the three ways to prove a bound about a whole sequence of operations rather than any single one, verified against a live push simulator (a running credit balance that dips at every dynamic-array resize and never goes negative) and a real worked example of Splay Tree's own potential-function argument — the exact proof that page names and defers, reproduced here with actual computed potential values, not just asserted.
The first guide that cuts across categories instead of within one: Quicksort, Quickselect, and Welzl's Smallest Enclosing Circle always return the correct answer and gamble only on running time (Las Vegas), while Karger's Algorithm and Miller–Rabin always finish fast and gamble on correctness instead (Monte Carlo) — a live calculator shows the two Monte Carlo bounds shrinking at wildly different rates under repetition, using each source page's own already-proven formula.
A third standalone reference tool: the theorem that turns a divide-and-conquer recurrence
T(n) = aT(n/b) + f(n) into a closed-form bound, with a live calculator and six
recurrences already proven elsewhere on this site — Binary Search through Toom-Cook
Multiplication, landing on bounds from a trivial Θ(log n) up through an
irrational Θ(nlog₃5) exponent — plus the real gaps the basic theorem
can't cover (T(n) = 2T(n/2) + n/log n fits none of its three cases).
A fourth standalone reference tool: a live probe binary-searches, in your own browser, for
the exact recursion depth that throws RangeError: Maximum call stack size exceeded —
then the same measurement applied live to three real reference implementations already on this
site. Merge Sort's O(log n) split stays safe at any size; Quicksort's own last-element-pivot
worst case doesn't just run slowly on sorted input, it exhausts the real call stack; N-Queens'
identical-looking O(N) bound never gets the chance, because the exponential search time runs
out first. Also measures, repeatedly, that V8 does not eliminate proper tail calls despite the
spec permitting it.
A third cross-cutting lens (after Las Vegas vs. Monte Carlo and the Master Theorem): three pairs already on this site answer the identical question once online (answer each request the instant it arrives) and once offline (see the whole batch first). Offline LCA vs. Binary Lifting, where offline wins on every axis; Mo's Algorithm vs. Segment Tree, where offline's real win is unlocking a non-mergeable query, not raw speed; Offline Dynamic Connectivity vs. Link-Cut Tree, where online needs a genuinely heavier structure. A live calculator shows the LCA pair's online/offline cost ratio growing from 1× to 7.5× as the tree scales from 16 to a billion nodes, with no ceiling.
A fourth cross-cutting lens: nine NP-hard/NP-complete entries on this site answer the same wall four different ways. 2-SAT and Fractional Knapsack restrict the problem until it lands in P (narrowing structure vs. relaxing integrality — two different knobs for the same escape); 0/1 Knapsack stays exact but pays in a pseudo-polynomial currency; Set Cover and Steiner Tree trade exactness for a proven worst-case ratio; Graph Coloring, Hamiltonian Path, DPLL, and Dancing Links accept the exponential and win only on the constant factor. A live calculator races all four real growth curves — O(n), O(n³), O(1000n), O(2ⁿ) — against the same n.
A fifth standalone reference tool: thirty terms this site's own pages use constantly without stopping to define — asymptotic notation, amortized cost, invariant, load factor, exchange argument, tail call, and more — each tied to the specific sentence, demo, or measurement on this site that earns the definition, not a generic textbook restatement. A live filter box narrows all thirty by name or definition text.
A cross-cutting look at the two ways to turn a DP recurrence into code, using Longest Common Subsequence's and Edit Distance's own already-measured cell counts to show memoization's savings are real but input-dependent, plus a live in-browser probe and Node measurements showing the one cost tabulation never pays at all — a real call-stack depth that hits a hard memory ceiling before it threatens the stack on a two-dimensional table, but can threaten it directly on a one-dimensional one.
A sixth cross-cutting lens: what "has a bad worst case" actually hides. Sorts every such claim on this site into four buckets — a permanent cliff from one specific, repeatable input (fixed-pivot Quicksort; a Binary Search Tree built from sorted data, measured live here for the first time — height exactly n), a cliff only bad luck can trigger and re-running erases (Skip List, Treap, random-pivot Quicksort), a spike that amortizes away over any real sequence (Dynamic Array's resize, Splay Tree's single worst access), or no cliff at all regardless of input or luck (AVL Tree's hard height bound).
A seventh cross-cutting lens: what Big-O doesn't count — memory layout. Binary Search and AVL Tree lookup are both O(log n), and measuring their own reference implementations confirms near-identical step counts at every size — yet the tree runs 2.5×–2.9× slower than the array at a million keys in Node v20.20.2, purely from scattered heap-allocated nodes defeating the CPU's cache versus one contiguous block that doesn't. A live in-browser race lets a visitor reproduce the crossover themselves.
An eighth cross-cutting lens: how much extra memory a real structure on this site actually spends to buy speed, measured rather than estimated. Sparse Table stores 4.5×–11.5× more values than Segment Tree (growing with n) to turn an O(log n) query into O(1). Bit Vector Rank/Select's block/ superblock tables — instrumented directly, not estimated — cost real, shrinking overhead (88% of n at a thousand bits, down to 26% by ten million) to replace an O(n) scan with 3 fixed array reads. A live calculator reproduces the second structure's exact word count at any size.
A ninth cross-cutting lens: does an operation mutate what's already there, or allocate a
fresh copy to do its job, and what does that copy actually cost? Cites
Quicksort vs.
Merge Sort's own measured 2.3×–2.7× gap
and Min-Max Heap vs.
Binary Heap's 2×–9× gap, both already
driven by exactly this, plus a fresh minimal-case measurement (a plain mutating loop vs.
Array.prototype.map) isolating the allocation tax alone: 1.3×–1.5× at
n=1,000–10,000, widening to 2.7×–3.2× by a million. A live race lets a visitor
reproduce it.
A cross-cutting comparison spanning two of the site's categories — Binary Heap and Min-Max Heap (Array-Backed Trees), plus Binomial, Leftist, Skew, Pairing, and Fibonacci Heap (Node-Linked Trees) — organized by whether both ends of the set matter, whether two whole heaps ever need to merge, and whether decrease-key needs a worst-case, amortized, or no bound at all, reusing seven already-measured results scattered across those pages rather than new benchmarks, plus a side-by-side table.
A tenth cross-cutting lens, and a direct sequel to LRU Cache and LFU Cache's own shared closing line that picking between them is "a bet about the real workload, not something either page's own complexity bound can settle." Runs both pages' own shipped classes against two synthetic workloads: a periodic-flood workload where LFU protects a small hot core (99.50% vs. LRU's 90.00% hot-core hit rate) and a popularity-reversal workload where LFU can get permanently stuck at a literal 0.00% hit rate on a newly-popular set while LRU adapts to 96.67% — not a slow convergence, a measured 0.00% at 30, 100, 1,000, and even 10,000 rounds.
An eleventh cross-cutting lens: four pairs of entries that turn out to be the literal same computation under different names — Bipartite Matching built as a tiny flow network, 2-SAT handed off to Strongly Connected Components, range-minimum query folded through Cartesian Tree into Lowest Common Ancestor, and Aho-Corasick collapsing into byte-identical KMP at exactly one pattern — plus a card-matching game and a Pitfalls section on where "correct reduction" stops meaning "best implementation."
A twelfth cross-cutting lens, this time proving the matching lower bound for upper bounds
already shipped elsewhere on the site: the decision-tree argument gives
Merge Sort's comparison-sort floor of
Ω(n log n) (derived, not just asserted, with a worked six-permutation tree at
n = 3) and Binary Search's matching
Ω(log n); a separate adversary/elimination argument gives the
n - 1 comparisons any max-finding scan needs, tying directly to
Selection Sort's own measured
n(n-1)/2. A live calculator checks all three against real worst-case comparison
counts for any n: Merge Sort matches the proven minimum exactly at n = 3, lands 7.7% over it at
n = 7, and 5.1% over at n = 1,024 — against the quadratic sorts' own ~60x gap at that same
size, a gap that keeps widening with n instead of staying small.
A seventh standalone-reference-tool guide: every one of the site's 313 algorithms and data structures in one sortable, filterable table, with the complexity each page states about itself — sourced verbatim from each page's own header line, not re-derived or rounded here. Click a column to sort by name, type, category, or complexity; type to filter across all of them at once.
A comparison across the site's three Concurrency entries — Dekker's, Peterson's, and Lamport's bakery algorithm — organized by whether the process count is fixed at two or not, reusing each page's own exhaustive-search numbers and measured compare-and-swap gap rather than new measurements. Includes a real historical wrinkle: Lamport's N-process solution (1974) was published seven years before Peterson's two-process algorithm (1981), the opposite order from how each page's own prose frames the generalization.
A comparison across the site's six competing compression entries — Run-Length Encoding, LZW, LZ77, DEFLATE, Huffman Coding, and Arithmetic Coding — organized by what shape of redundancy each one exploits (adjacent runs, repeated substrings anywhere or within a window, plain frequency skew, or — DEFLATE alone — both a window search and frequency skew stacked in one format), reusing each page's own measured numbers. A seventh entry, Move-to-Front, is deliberately excluded from that "which do I reach for" framing — it never compresses alone — and given its own section instead, showing what it adds when stacked ahead of Huffman. New verified finding: running the site's own shipped Huffman and Arithmetic Coding implementations against twelve scrambled versions of four messages confirms both depend only on symbol frequency, never on order — a real structural split from RLE, LZW, LZ77, and DEFLATE, which are all extremely order-sensitive, not just an impression from how each is described.
A thirteenth cross-cutting lens, synthesized entirely from the site's five Concurrency entries' own already-measured numbers: Peterson's, Dekker's, and Lamport's bakery algorithm each prove, independently, that a safety violation and a liveness failure (deadlock or starvation) never come from the same broken piece — remove a turn-taking variable and only liveness breaks, remove a flag's self-trust and only safety does. Liveness itself splits once the resource shape changes: Dining Philosophers' resource-hierarchy fix buys deadlock-freedom only (its own Complexity section says so directly), and Readers-Writers' fair ticket-order policy buys starvation-freedom only — two unrelated cures for two unrelated diseases on pages that otherwise look like the same kind of fix.
A cross-cutting lens on the site's eleven Concurrency entries, which split into two families by how a process waits: ten (Peterson's, Dekker's, Lamport's bakery, Dining Philosophers, Readers-Writers, and the CAS-retrying Treiber Stack, Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List) busy-wait or busy-retry, never blocking; one (Producer-Consumer) blocks on a semaphore. A real worker-thread benchmark measures the gap directly rather than asserting it: a spinning waiter's CPU cost tracks its wall-clock wait almost exactly 1:1, while a blocked waiter's cost stays a near-constant fraction of a millisecond regardless of wait length — so the ratio between them widens with duration, from roughly 300x at a 70ms wait to about 8,000x at 3 seconds, rather than holding at some fixed multiple.
A comparison across the site's two safe-memory-reclamation entries — Hazard Pointers and Epoch-Based Reclamation — both built to close the same forward reference the Treiber Stack's own page left open, both measured to 0 corrupt states on its exact scenarios. Reusing each page's own numbers rather than new measurements: Epoch-Based Reclamation's bookkeeping sits closer to the unprotected baseline (+36%/+74% reachable states vs. Hazard Pointers' +81%/+97%), but a single stalled thread holds every node retired since it stalled hostage, unboundedly (measured 1,000 cycles to 1,000 stuck nodes), where Hazard Pointers can only ever block the one id it last published, at the cost of a scan on every single retire.
A comparison across the site's five Cryptography entries — Diffie–Hellman Key Exchange, RSA Encryption, SHA-256, HMAC, and RSA Digital Signature — organized by which question each one actually answers (agree on a secret, keep a message private, fingerprint data with no key at all, prove a shared secret, prove a private key) rather than by which is "best." Two threads verified across pages rather than within one: the identical multiplicative shortcut that breaks RSA Encryption's secrecy and RSA Digital Signature's authenticity, same algebra either way; and the same toy-modulus pitfall — a deliberately small number cracked live on the page — recurring on three of the five entries, with no equivalent axis at all on the two (SHA-256, HMAC) that rest on no number-theoretic hard problem in the first place.
A cross-cutting lens tying Bit Manipulation, Number Theory, Cryptography, and Sorting
together: whether an algorithm's own step count varies with the specific value of an input of
fixed size, not just its size. Brian Kernighan's Algorithm and Binary GCD do; SWAR Popcount and
Bitonic Sort don't. Harmless either way for a popcount or a sort — but the identical
square-and-multiply modPow reused across eight of this site's Number Theory and
Cryptography pages, and the naive tag comparison HMAC's own Pitfalls section names, show the
same data-dependence become a real timing leak once one of the inputs is secret. Two live
widgets measure both sides by counting operations, not milliseconds.
The Bit Manipulation category's first guide, organized by mechanism rather than by problem: a fixed full-width scan, a data-dependent one-bit-at-a-time loop, a fixed-step arithmetic fold, and a precomputed-table lookup. Brian Kernighan's Algorithm's naive scan and the de Bruijn CTZ page's own naive loop independently found the same surprising cost — branch prediction, not average iteration count, decides a tight bit-manipulation loop's real speed. SWAR Popcount and the de Bruijn lookup buy a fixed cost in two different currencies, and generalize to 64 bits in opposite directions.
Compression and Cryptography pull the same quantity — entropy — in opposite directions: Huffman Coding's own Shannon-entropy bound measures redundancy left to remove, while SHA-256's own avalanche effect measures redundancy destroyed on purpose. Reusing DEFLATE's own LZSS tokenizer and AES's own CTR keystream unmodified, a live widget shows compress-then-encrypt banks a real win while encrypt-then-compress costs 112-125% of its own fixed width, never less, across 120 random trials — then a second widget reproduces the real CRIME/BREACH mechanism in miniature: compressed length drops a steady 7 bits per correctly-guessed character of a secret shared a buffer with an attacker's guess.