Insert Delete GetRandom O(1)
Last Updated: April 4, 2026
Understanding the Problem
We need to design a data structure that supports three operations, all in average O(1) time: inserting an element, removing an element, and returning a uniformly random element.
The tricky part is that no single standard data structure handles all three well. A hash set gives O(1) insert and remove, but there's no way to pick a random element in O(1) because you can't index into a hash set. An array gives O(1) random access (just pick a random index), but removing an arbitrary element is O(n) because you'd need to shift everything.
The key observation is that we can combine both: use an array for O(1) random access and a hash map for O(1) lookups. The clever trick that makes removal O(1) is swapping the element to delete with the last element in the array, then popping the last element.
Key Constraints:
At most 2 * 10^5 calls→ Each operation must be O(1) on average. Linear scans per call would give O(n) per call and TLE with this many operations.-2^31 <= val <= 2^31 - 1→ Values span the full integer range, so we can't use a fixed-size boolean array. We need a hash map for membership checks.At least one element when getRandom is called→ No need to handle the empty-set case for getRandom.
Approach 1: Hash Set with Linear Scan for Random
Intuition
The most straightforward approach is to use a hash set for O(1) insert and remove, then convert it to a list whenever we need a random element. A hash set handles membership checks, insertion, and deletion in O(1). For getRandom, we can copy all elements into a list and pick a random index.
This works correctly, but converting the entire set to a list on every getRandom call is O(n), which violates the O(1) requirement. It's a useful starting point, though, because it makes the bottleneck obvious.
Algorithm
- Maintain a hash set to store all current elements.
- For
insert(val): check if val is in the set. If not, add it and return true. Otherwise return false. - For
remove(val): check if val is in the set. If so, remove it and return true. Otherwise return false. - For
getRandom(): convert the set to a list (or array), generate a random index, and return the element at that index.
Example Walkthrough
Input:
For each operation, we simply add/remove from a hash set. When getRandom is called, we convert the set to an array and pick a random index. With set = {1, 2}, getRandom converts to [1, 2] and picks randomly:
Code
- Time Complexity: O(1) for insert and remove, O(n) for getRandom. Insert and remove are O(1) because hash set operations are constant time on average. But getRandom requires converting the set to an array, which copies all n elements.
- Space Complexity: O(n). We store n elements in the hash set, plus an O(n) temporary array on each getRandom call.
The bottleneck is getRandom: we rebuild the entire array from scratch every time. What if we maintained an array alongside the hash map so random access by index is always available in O(1)?
Approach 2: Array + Hash Map (Optimal)
Intuition
The insight is to use two data structures together, each covering the other's weakness. An array gives us O(1) random access: just generate a random index and return the element there. A hash map gives us O(1) lookups: given a value, we can instantly find where it sits in the array.
Insert is straightforward: append the new element to the end of the array and record its index in the hash map. getRandom is also easy: pick a random index from 0 to size-1 and return the array element there.
The clever part is removal. Removing from the middle of an array is normally O(n) because you need to shift elements. But here's the trick: we don't care about the order of elements. So instead of shifting, we swap the element we want to remove with the last element in the array, update the hash map for the swapped element's new position, and then pop the last element. Both the swap and the pop are O(1).
The combination works because each data structure compensates for the other's weakness. The array provides O(1) random access by index, which the hash map cannot do. The hash map provides O(1) value-to-index lookup, which the array cannot do without a linear scan.
The swap-with-last trick is the critical insight. In a normal array, removing an element from the middle requires shifting all subsequent elements, which is O(n). But since we don't need to maintain any particular order, we can just move the last element into the gap. This is a single assignment plus a map update, both O(1).
Algorithm
- Maintain an array
listthat stores all current elements, and a hash mapvalToIndexthat maps each value to its index in the array. - For
insert(val): if val is already in the map, return false. Otherwise, append val to the end of the array, record its index in the map, and return true. - For
remove(val): if val is not in the map, return false. Otherwise, get val's index from the map. Swap the element at that index with the last element in the array. Update the map for the swapped element's new index. Remove the last element from the array and remove val from the map. Return true. - For
getRandom(): generate a random index between 0 and size-1 (inclusive) and return the array element at that index.
Example Walkthrough
Code
- Time Complexity: O(1) average for all three operations. Insert is O(1) amortized (one hash map lookup + one array append). Remove is O(1) (one lookup + one swap + one pop + map updates). getRandom is O(1) (one random number + one array access).
- Space Complexity: O(n). We store each element once in the array and once in the hash map, so total space is O(n) where n is the number of elements currently in the set.