The problem
Implement a skiplist supporting search, add, and erase in O(log n) expected time, without using built-in ordered structures.
Stuck? Reveal hints one at a time
How to approach it
- 1Node = value + array of forward pointers (one per level it lives on).
- 2search: descend levels, at each level advancing while forward.value < target; after level 0, check the next node.
- 3add: record the "predecessor at each level" during descent; flip coins for the new node’s height; splice into every level up to that height.
- 4erase: same descent; unlink the node at every level where the predecessor points at it. Return whether it existed.
Key insight
The predecessors array captured during descent is the entire update plan — insert and delete are just pointer swaps against it, level by level.
The solution
Watch out for
- Duplicates are allowed — erase must remove exactly one occurrence.
- Strictly-less in the descent (not ≤) is what lands the cursor immediately BEFORE the target.