This site's twelfth Disjoint Set entry, picked by category
balance — Disjoint Set was the sole category sitting at eleven while everything else had reached
twelve. Every other entry in this category eventually answers some version of "are these two things
in the same group?" This one doesn't ask that question at all: given a fixed row of slots that get
permanently marked taken one at a time — seats filling up, parking spaces claimed, time slots
booked — answer, over and over, "what's the smallest still-available slot at or after position
i?" Union-Find's own two-line
find — walk parent pointers to a root, then compress every node on that path to point
straight at it — turns out to be exactly the right machinery for this, once "parent" is redefined to
mean "look further right" instead of "belongs to the same group."
Eight slots, 0 through 7, all start available. The dashed box on the far
right (∅) is a permanent sentinel — always "available," but not a real slot, so a query
that lands there means nothing is free from here on. Click a slot to select it, then press
Occupy to take it (this runs a search for the next free slot starting one position to
the right, then points the newly-taken slot straight at whatever that search found) or
Next Available to ask the question directly. Press Step or
Run to watch the walk happen one hop at a time, and watch the arcs below the row
collapse as compression rewires them. Try occupying 2, 3, then
4 in order, then ask Next Available on 2: the query walks
all three hops to reach 5 and compresses every one of them to point straight there —
asking again on 3 right after costs a single hop, because that search already did the
work.
The pointer direction is forced, not chosen. Plain Union-Find's union(x, y)
can attach either root under the other — that choice is exactly what union-by-rank decides, picking
whichever keeps trees shorter. Here there's no such choice: occupy(i) always points slot
i toward larger indices, because "next available" only ever means "look forward," never
back. That forced direction is also why this structure needs no rank (or size) bookkeeping at all —
there's nothing to balance a decision between.
Occupying is a search, not just a write. Marking slot i taken isn't
enough on its own; something has to decide where i's pointer should now lead. That
something is a real find(i + 1) call — the exact same walk-and-compress find
plain Union-Find uses for "what's the root of x's group?" — repurposed to mean "what's
currently the next available slot from here?" So every occupy already pays for (and
benefits from) one full compression pass, not just a pointer write.
The sentinel isn't decoration. Without a permanently-available (N)th
slot beyond the real ones, "nothing is free from here on" has no valid place to point — the last real
slot, once taken, would have nowhere correct to redirect to. See the Pitfalls
section for exactly what a plausible-looking fix without it does instead.
Measured: no growth trend, from a thousand slots to a million. Plain Union-Find
needs both union-by-rank and path compression together to reach O(α(n)) amortized
— path compression alone, on an arbitrary sequence of unions, is only proven down to
O(log n) amortized, because an adversary can still merge two already-large trees together
in the worst possible order. That specific adversarial move is structurally impossible here:
occupy(i) only ever attaches one brand-new, single slot onto whatever tree
find(i + 1) already resolved to — never two populated trees merging into each other. Two
stress tests confirm the difference shows up in practice, not just in the argument: occupying every
slot from n = 1,000 up to n = 1,000,000, in a random order, costs on average
0.993 to 1.000 hops per occupy at every scale tested — flat, no
upward trend at all. A specifically adversarial order designed to defeat compression — occupy
n − 1, then n − 2, ..., down to 0, so every new slot is prepended
to the front of a chain that's never had a chance to compress — costs exactly 1.000 hop
per occupy at every one of those same sizes, because each new slot's search immediately
lands on a target that the previous occupy's own search already flattened to the root. Neither
test shows the log₂ n growth (from 9.97 at n = 1,000 to
19.93 at n = 1,000,000) that the general path-compression-alone bound would
predict if this were an ordinary arbitrary-union sequence.
Matches the demo above: slot n is the sentinel, permanently its own parent, never
occupied. find is the standard two-pass walk-then-compress:
class NextAvailableSlots {
#parent;
#occupied;
constructor(n) {
this.#parent = Array.from({ length: n + 1 }, (_, i) => i); // n is the sentinel
this.#occupied = new Array(n).fill(false);
}
#find(x) {
let root = x;
while (this.#parent[root] !== root) root = this.#parent[root];
while (this.#parent[x] !== root) {
const next = this.#parent[x];
this.#parent[x] = root; // path compression
x = next;
}
return root;
}
occupy(i) {
this.#occupied[i] = true;
this.#parent[i] = this.#find(i + 1); // point straight at the next free slot, right now
}
// smallest available slot at or after i, or -1 if none remain
nextAvailable(i) {
const root = this.#find(i);
return root === this.#parent.length - 1 ? -1 : root;
}
}Pointing the union the other way looks almost identical and is completely broken.
Swap the direction — attach slot i + 1's current root onto i instead of the
other way around — and every query still returns some slot number, never crashes, never
throws. It's just wrong: on 30,000 random occupy/query sequences (3-12 slots, 20 operations each)
checked against an independent linear-scan oracle, the reversed version answered incorrectly on
29,990 of them (99.97%). A small hand-traced example shows why: occupy
2, then occupy 3, then ask for the next available slot at or after
2 — the correct answer is 4, but the reversed version returns
2 itself, a slot that's already taken, as if it were free.
Skip the sentinel and the last slot lies forever. Without a dedicated always-free
node beyond the real slots, a plausible fallback for "occupy the very last slot" is to just leave its
pointer alone, since there's nothing valid to redirect it to. That's wrong in exactly the cases where it
matters: across 30,000 random-sized runs that occupy the final slot and then immediately query it, that
fallback answers incorrectly 100% of the time — the occupied last slot still looks like its
own root, so it gets reported as available. Concretely, with 4 slots: occupy 3, then ask
for the next available slot at or after 3 — correct answer is -1 (nothing
free), but the no-sentinel version answers 3.
Dropping path compression survives correctness and quietly loses the entire point.
Every query still returns the right slot without compression — the walk to the root is still valid, it's
just never shortened afterward. The cost shows up only in how much repeated work gets redone: occupy
every slot left to right, then ask for the next available slot at position 0 fifty times in
a row (the first query has nowhere fully-compressed to land — everything after it depends on how many of
those slots are still taken up ahead). With compression, only the first of the fifty pays the full walk;
the other forty-nine cost one hop each. Without it, every single one of the fifty re-walks the entire
remaining chain:
| n | with compression | without | ratio |
|---|---|---|---|
| 100 | 149 | 5,000 | 33.6× |
| 1,000 | 1,049 | 50,000 | 47.7× |
| 10,000 | 10,049 | 500,000 | 49.8× |
| 100,000 | 100,049 | 5,000,000 | 50.0× |
The ratio climbs toward exactly 50× — not a coincidence, that's the query count in the
test. Without compression every one of the 50 queries pays the same full price; with it, only the first
does, so the gap between them is bounded by how many repeat queries get to ride for nearly free.
Time: empirically flat at ~1 hop per occupy or
nextAvailable call from n = 1,000 through n = 1,000,000, under
both a random occupation order and an order specifically constructed to defeat compression — see
Why it works for both stress tests and why the usual
O(log n) path-compression-alone bound doesn't apply to this specific access pattern.
Space: O(n) — one parent slot per real slot plus the one sentinel, no
rank array needed since there's no union-by-rank decision to store.
This site's guide, Choosing a Union-Find Variant, sets this entry (and six siblings like it) aside up front as applications built on top of Union-Find rather than alternatives to it — each answering a genuinely different question, not competing for the same job as the four core variants it actually compares.