The problem
Design a set with insert(val), remove(val), and getRandom() — each element equally likely — all in average O(1).
Stuck? Reveal hints one at a time
How to approach it
- 1Keep values in an array and a map value → its index.
- 2insert: reject if present; else append and record the index.
- 3remove: look up the index; move the last element into that slot (updating its map entry); pop the array; delete the map entry.
- 4getRandom: return the array element at a uniform random index.
Key insight
Swap-with-last converts "delete anywhere" into "delete at the end" — the one array operation that is O(1).
The solution
Watch out for
- Update the moved element’s map entry BEFORE deleting the victim’s — removing the last element itself is the edge case that breaks naive orderings.
- getRandom must be uniform over CURRENT elements; random map iteration is not uniform.