Insert Delete GetRandom O(1)
Design a set of integers supporting insert(x), remove(x) and getRandom(), where getRandom returns a uniformly random element among those currently stored. All three operations must run in average constant time.
- -2^31 ≤ x ≤ 2^31 - 1
- At most 2 · 10^5 operations
- getRandom is only called on a non-empty set
- Uniform random access needs an array with indices
- O(1) membership and deletion needs a hash map
- Combine two structures: map value → position
Whenever a brute force re-scans earlier elements to check membership, count, or a complement, a hash table answers the same question in expected O(1) and turns O(n^2) into O(n). Grouping problems reduce to choosing a canonical key (a sorted string, a character-count tuple) and bucketing by it.
Keep a dynamic array of values and a hash map from value to its index in the array. Insert appends and records the index. To remove x, look up its index, move the last array element into that slot, update its index in the map, then pop the last slot and delete x from the map — a swap-with-last trick that keeps the array dense. getRandom picks a uniform random index into the array.
- A hash set alone cannot give uniform random selection without O(n) iteration; a balanced BST with subtree sizes gives O(log n) for all three but is heavier.