data structures · dense + sparse array pair · O(1) insert, contains, delete, and clear

Sparse Set

Every other Linear entry on this site answers some version of "how should a sequence be stored." A sparse set answers a different question entirely: given a fixed universe of small integers [0, U), is a given value currently a member of some set, and can that set be built up, torn down, and emptied without ever paying for the universe's full size on any single operation? A plain boolean array over [0, U) already gives O(1) insert, contains, and delete — the one thing it can't give is O(1) clear, since resetting every slot back to false is an O(U) scan no matter how few elements were actually in the set. A sparse set gets all four operations to O(1), clear included, by keeping two arrays instead of one and never actually resetting the second one at all.

The two arrays are dense, which packs the set's actual members at indices [0, n) in no particular order, and sparse, sized to the full universe U, where sparse[v] is supposed to hold the index in dense where v lives. The trick is what "supposed to" is allowed to mean: sparse is never zeroed, cleared, or reset, ever, for the lifetime of the structure. A membership check doesn't trust sparse[v] on its own — it uses sparse[v] as a pointer back into dense and then checks whether dense points right back: v is a member exactly when sparse[v] < n and dense[sparse[v]] === v. That second half is doing all the work. A raw, uninitialized sparse array is full of garbage the very first time it's used — every value in [0, U) reads as "a member" under the first check alone unless the second check catches it, which it reliably does, because a value that was never actually inserted has essentially no chance of a stale number in sparse[v] happening to point at a dense slot that echoes v back. clear() exploits exactly this: setting n = 0 makes every sparse[v] < n check fail immediately, without touching a single byte of either array.

Try it

Universe is fixed at [0, 16) for this demo. Insert and delete values and watch both arrays update — dense stays packed at the front, sparse keeps whatever number was last written into each slot, live or not. Cells highlighted in the accent color are currently valid members; everything else is either untouched or stale garbage left over from an earlier delete. Click Clear and watch sparse stay completely untouched while every value instantly stops being a member.

value (0–15)

dense[0..n) — the packed members, n = 0

sparse[0..16) — one slot per universe value, never reset

Empty set. Insert a few values, delete one, then Clear and watch the sparse row keep its old numbers while every value stops being a member.

Core operations

insert(v) — O(1). If contains(v) is already true, do nothing. Otherwise append v to the end of dense at index n, point sparse[v] = n, then n++.
contains(v) — O(1), and the one place the whole structure's correctness lives: sparse[v] < n && dense[sparse[v]] === v. Skipping the second half and trusting sparse[v] < n alone is a real, reproducible bug — see Pitfalls.
delete(v) — O(1), via swap-with-last: if v isn't a member, do nothing. Otherwise let i = sparse[v] (v's slot in dense) and last = dense[n - 1] (the current final element). Overwrite dense[i] = last, fix up sparse[last] = i so the moved element still points at its new home, then n--. sparse[v] itself is not touched — it's simply left stale, which is exactly what contains's reverse-validation check is built to tolerate. If v happens to already be the last element, i === n - 1 and last === v, so the "swap" writes dense[i] = v right back where it was — a no-op in effect, needing no special case.
clear() — O(1). Set n = 0. Nothing else. Every sparse[v] < n check now fails for every v, regardless of what garbage still sits in sparse.

Reference implementation

class SparseSet {
  #dense;    // packed members at [0, n)
  #sparse;   // sparse[v] = index into #dense, meaningless unless validated
  #n = 0;

  constructor(universe) {
    this.#dense = new Array(universe);
    this.#sparse = new Array(universe); // deliberately never initialized
  }

  get size() { return this.#n; }

  contains(v) {
    const i = this.#sparse[v];
    return i !== undefined && i < this.#n && this.#dense[i] === v;
  }

  insert(v) {
    if (this.contains(v)) return false;
    this.#dense[this.#n] = v;
    this.#sparse[v] = this.#n;
    this.#n++;
    return true;
  }

  delete(v) {
    if (!this.contains(v)) return false;
    const i = this.#sparse[v];
    const last = this.#dense[this.#n - 1];
    this.#dense[i] = last;
    this.#sparse[last] = i;
    this.#n--;
    return true;
  }

  clear() {
    this.#n = 0; // sparse and dense are left untouched, on purpose
  }
}

JavaScript arrays don't hand back true uninitialized garbage the way a C array does — unset indices read undefined, which is exactly what the i !== undefined guard in contains exists to handle on this page's very first access to any given slot. A real C or C++ implementation skips that guard entirely and just reads whatever bit pattern happens to already be sitting in sparse[v]'s memory, relying purely on dense[sparse[v]] === v to reject it — a subtlety worth naming since the classic form of this structure (Briggs & Torczon, 1993) is usually described for exactly that environment. Verified against a plain Set model over 200,000 randomized insert, delete, contains, and clear operations across a 20-value universe, with a full-structure check (comparing every live member, not just the last operation's return value) every 1,000 operations — 0 mismatches. See /tmp/sparse_test/verify.js, not committed, it's scratch.

Pitfalls

Trusting sparse[v] < n alone. This is the one bug this structure is actually built around avoiding, and it's easy to write by accident since sparse[v] < n alone genuinely does look like a complete bounds/membership check. Concretely: insert 3, then insert 5. dense = [3, 5], sparse[3] = 0, sparse[5] = 1, n = 2. Now delete 3: swap-with-last moves 5 into slot 0, so dense = [5], sparse[5] = 0, n = 1 — and sparse[3] is left exactly as it was, still 0, never touched. A naive contains(3) that only checks sparse[3] < n computes 0 < 1, true — a confirmed false positive, reproduced exactly on this page's own numbers. The real check catches it: dense[sparse[3]] = dense[0] = 5, which is not 3, so contains(3) correctly returns false. The fix isn't a special case for this scenario — it's that contains always needs both halves of the check, on every call, not just after a delete.

Delete doesn't preserve order. Swap-with-last is what makes delete O(1) instead of O(n), but it means the member that used to be last in dense can end up anywhere a deleted element used to be. A caller that inserts values in a specific order and later iterates dense expecting to see that same order back — the way a Queue or a plain array would guarantee — gets silently reordered results instead, with no error of any kind. This structure answers "is v a member" and "what are the current members," never "in what order were they added."

The universe has to be known and small. sparse costs O(U) space the moment the structure is created, regardless of how many elements ever actually get inserted — a sparse set over 32-bit integers isn't viable at all, and even a million-entry universe costs a million-slot array before a single insert call. This is the direct trade against a hash-based set: a Cuckoo Filter or a plain hash table pay per-element cost and accept arbitrary, unbounded keys; a sparse set pays per-universe cost up front and gets true O(1) worst case (no hashing, no probing, no resizing) plus the free O(1) clear in exchange. Neither is strictly better — it depends entirely on whether the universe is bounded and small enough to allocate for.

Where sparse sets show up

Entity-component-system game engines. Entity IDs are small dense integers handed out by the engine itself, not arbitrary keys — exactly the shape a sparse set wants. Which entities currently have a given component is a classic sparse-set use, and the free O(1) clear matters because that membership set can be rebuilt from scratch every single frame.
A per-query "visited" set reused across many graph traversals. A BFS or DFS run thousands of times against the same fixed vertex set (a competitive-programming judge running many queries against one graph, for instance) needs its visited-tracking reset before every run. A boolean array forces an O(V) reset each time; a sparse set's clear() makes that reset free, turning what would be O(queries × V) total reset cost into O(queries) plus one O(V) allocation at the very start.
Compiler register allocation. Live-variable sets during liveness analysis are built and rebuilt at every instruction over a small, fixed universe (the compiler's own virtual register IDs) — the same "build it, tear it down, build a new one" access pattern the structure is shaped for.

Complexity

Time: insert, contains, and delete are all O(1) worst case — not amortized, no hashing, no probing chain to walk. clear() is O(1) regardless of how many elements were in the set, the structure's headline feature: no other exact set on this site (or a plain boolean array) offers that. Space: O(U) for the sparse array plus O(n) for dense, where U is the fixed universe size and n is the current member count — the U term is paid up front regardless of how many elements are ever actually inserted, the direct cost of the O(1) guarantees above.

This site's guide, Choosing a Linear Data Structure, sets this entry aside for yet another reason than Monotonic Stack, Monotonic Deque, and XOR Linked List already are: it isn't a sequence storage option or a technique layered on one at all, but an unordered membership set over a bounded integer range — a different question than "how should this sequence be stored," not a competing answer to it.