Insert Delete GetRandom O(1)
Problem Statement
Design a RandomizedSet data structure that supports insert, remove, and getRandom in average O(1) time. insert(val) adds val if it is not present. remove(val) deletes val if it is present. getRandom() returns a random element from the current set, where every stored element must have the same probability of being chosen.
Input
A sequence of calls to RandomizedSet, insert(val), remove(val), and getRandom().
Output
For the constructor output null. For insert and remove, output whether the operation changed the set. For getRandom, output one uniformly random value currently stored.
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
Examples
Example 1
operations = [RandomizedSet, insert, insert, getRandom, remove, getRandom], arguments = [[], [1], [2], [], [1], []]
One valid output is [null, true, true, 2, true, 2]Example 2
operations = [RandomizedSet, insert, insert, remove, remove, insert], arguments = [[], [5], [5], [7], [5], [5]]
[null, true, false, false, true, true]Learning Objectives
- Combine an array and a hash map so each operation receives the guarantee it needs.
- Explain why uniform random choice requires direct index-based access.
- Use swap-with-last deletion to remove an arbitrary array element in O(1).
- Maintain the invariant that every stored value maps to its current array index.
Intuition
Pattern Recognition
The required operations pull in different directions. getRandom wants an array because a random index gives uniform access in O(1). insert and remove want a hash map because membership and location lookup must also be O(1). The design signal is that no single basic structure gives all three guarantees.
The tempting approach is a hash set alone, but a hash set cannot choose the kth stored element uniformly without walking through elements. An array alone gives random access but cannot find a value to remove quickly. The pattern is hash-backed indexing: store values in a dense array and store each value's index in a map.
Common mistakes
- ×Removing from the middle of an array by shifting elements, which makes remove O(n).
- ×Forgetting to update the moved last element's index after swapping.
- ×Using a hash set alone and then iterating to implement getRandom.
- ×Producing a random value from the value range instead of from the stored array indices.
Algorithm Explanation
Key idea
Keep values, a dense array list of the elements, and indexByValue, a hash map from each value to its current index in values. Insert appends to the end. Remove swaps the target with the last element, pops the last slot, and fixes the moved value's index. Random selection chooses an index from 0 through values.size() - 1.
Walkthrough
Start empty. After insert(10), values = [10] and the map is 10 -> 0. After insert(20), values = [10,20] and the map is 10 -> 0, 20 -> 1. To remove(10), find index 0, move the last value 20 into index 0, update 20 -> 0, pop the old last slot, and delete 10 from the map. Now values = [20], so getRandom must return 20.
Algorithm
- For insert(val), if val is already in the map, return false.
- Otherwise map val to values.size(), append it to the array list, and return true.
- For remove(val), if val is absent, return false.
- Read the target index and the last value in the array list.
- Write the last value into the target index, update its map entry, remove the final array slot, then delete val from the map.
- For getRandom(), choose a random array index and return the value stored there.
Solutions
Solution: Array list plus value-to-index map
The array list stores a dense collection for uniform random index selection. The hash map stores where each value currently lives, so arbitrary removal can be converted into a constant-time swap with the last slot.
Step-by-step
- Store every inserted value at the end of the array list and remember its index in the map.
- When removing a value, look up its index directly from the map.
- Move the last array value into that index so the array remains dense.
- Update the moved value's index in the map, pop the last slot, and remove the deleted value's map entry.
- Generate a random integer bounded by the current list size and return the value at that index.
Average O(1) per operation
O(n)
The array list and map each store one entry per active value.
Java implementation
Dry Run
Sample input
Operations: insert(10), insert(20), remove(10), getRandom(). Track the dense array and map after each call.
| operation | argument | structure state | result |
|---|---|---|---|
| insert | 10 | values = [10], map = {10 -> 0} | true |
| insert | 20 | values = [10,20], map = {10 -> 0, 20 -> 1} | true |
| remove | 10 | move 20 to index 0, values = [20], map = {20 -> 0} | true |
| getRandom | none | only index 0 is available | 20 |
The remove operation never shifts a range of elements. It only overwrites one slot, pops the last slot, and fixes one map entry.
Interview Tips
Lead with the reason two structures are necessary: the array provides uniform random indexing, while the map provides O(1) membership and index lookup. The critical invariant is that the array is dense and the map always points to current positions. When explaining remove, explicitly handle the case where the removed value is already the last value; the same swap code still works.
Likely follow-ups
- How would you support duplicate values while preserving random probability by occurrence?
- How would you make getRandom reproducible for tests without changing asymptotic complexity?
- How would you support getRandomWeighted where each value has a weight?
- How would you make the structure thread-safe?
Similar Problems
Key Takeaways
- Use an array list when random access by index is part of the requirement.
- Use a hash map to turn value lookup and arbitrary deletion into O(1) expected time.
- Swap-with-last deletion keeps the array dense without shifting.
- After every mutation, the map must match the array's current indices.