Implement LeetCode 1206's Skiplist class: search(target) reports whether the value exists, add(num) inserts it — duplicates allowed — and erase(num) removes one instance and reports whether it found one. All three average O(log n), and no built-in collections beyond linked nodes are allowed. Heights come from a fair coin per level: a node starts at height 1 and grows one level for each head, capped at 16.
Before you code
Settle two decisions first: how a height is sampled (and what caps it), and how the walk records the predecessor of the new or removed node on every lane it touches. Both add and erase need that predecessor array, so one top-down walk should serve all three operations.
Hints
- Walk with strict
<comparisons; equal keys end up adjacent, which is what lets duplicates coexist and letseraseremove exactly one of them. - Splice like the lesson's insert: record
update[lvl]while walking, then write two pointers per lane the node owns. - For
erase, walk the same way, check the node after the stopping point for equality, unlink it from every lane it occupies, and shrink the top lane count while the head's highest lane is empty. - Measure your result: run 100,000 sorted inserts, then search for existing and missing keys while counting forward steps. The average lands near 16, against log2(100,000) = 16.6 — the geometric thinning the lesson describes.
What it practices
Probabilistic balance without rotations, from Skip lists.