Insert, delete, and get-random in O(1)

Question

Design a data structure (think: a live universe of tradable symbols you must sometimes sample uniformly at random) supporting:

insert(val), add val, return True if it was not already present;
remove(val), delete val, return True if it was present;
get_random(), return a uniformly random current element.

All three must run in $O(1)$ average time.

Accepted Answer

A hash set gives O(1) insert and delete but has no efficient "pick a random element", since its internal order is unspecified and you cannot index into it. An array gives O(1) random indexing but O(n) deletion from the middle. Combine them: a dynamic array vals holds the elements, and a dictionary pos maps each value to its index in that array. The trick for O(1) removal is the swap-with-last move: overwrite the slot of the departing value with the array's last element, fix that element's recorded index, then pop the tail. This avoids shifting. Tracing: insert(1) and insert(2) give vals = [1,…

Insert, delete, and get-random in O(1)

Your answer

More Coding questions