DSA problem
Insert Delete GetRandom O(1)
Implement a RandomizedSet that supports three operations, all in O(1) average time: insert(val) adds val to the set if not present and returns true; remove(val) removes val from the set if present and returns true; getRandom() returns a uniformly random element currently in the set. The catch is the strict O(1) requirement on every operation — including the random pick — which rules out most off-the-shelf structures.
A plain hash set handles insert and remove in O(1) but cannot give O(1) random access because its internal layout is not contiguous. A plain array gives O(1) random access (pick a uniform index) but remove is O(n) because shifting elements to fill the gap. The classic trick is to use both: a dynamic array for the values and a hash map from value to its index in the array. Together they enable a constant-time remove via the swap-with-last technique.
insert appends to the array and records the new index in the map. remove looks up the value's index, overwrites that slot with the last array element, updates the moved element's index in the map, and pops the array tail. After the swap the array is still gap-free and the map still points each value to its true index, so future getRandom calls remain unbiased.
getRandom picks a random index in [0, array.length) and returns the array element there. Because the array is always contiguous and contains every member exactly once, the pick is uniform. The whole design depends on the swap-pop trick — it is the canonical way to delete from an unordered array in O(1) without leaving a hole.
Examples
insert(1); remove(2); insert(2); getRandom(); remove(1); insert(2); getRandom()[true, false, true, 1 or 2, true, false, 2]insert(0); insert(1); remove(0); insert(2); remove(1); getRandom()[true, true, true, true, true, 2]insert(5); insert(5)[true, false]Constraints
- -2^31 <= val <= 2^31 - 1
- At most 2 * 10^5 calls will be made to insert, remove, and getRandom.
- There will be at least one element in the data structure when getRandom is called.
- All operations must run in O(1) average time.
- The random element returned by getRandom must be uniformly distributed.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.