Implement a set with insert(val), remove(val) and getRandom(). insert and remove return whether they changed the set. getRandom returns each element with equal probability. All three should run in O(1) time on average.
Before you code
A hash set gives O(1) insert and remove, but no way to pick a random element without walking it. An array gives an O(1) random pick, by choosing a random index, but O(n) removal. You need both, kept in sync.
Hints
- Store the values in an array, and a hash map from each value to its index in the array.
- To remove a value, look up its index, move the last element of the array into that index, update the moved element's entry in the map, then pop the last slot. No shifting.
- Handle the case where the value being removed is itself the last element.
Production & complexity notes
When solving Insert delete getrandom O(1) on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Inserting and deleting in the middle to reinforce the underlying pattern.
What it practices
The swap-with-last delete, from Inserting and deleting in the middle, combined with a hash map.