Insert Delete GetRandom O(1)
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.
No single standard data structure handles all three operations well. A hash set gives O(1) insert and remove, but it offers no way to pick a random element in O(1) because you cannot index into it. An array gives O(1) random access (pick a random index), but removing an arbitrary element is O(n) because you would need to shift the elements after it.
Combining both data structures solves this: an array for O(1) random access and a hash map for O(1) value-to-position lookups. To make removal O(1), swap the element being deleted with the last element of the array, then pop the last element. Both steps are constant time, and order does not matter for a set.
Key Constraints:
At most 2 * 10^5 calls→ Each operation must be O(1) on average. A linear scan per call would be O(n) per call and time out at this volume.-2^31 <= val <= 2^31 - 1→ Values span the full signed 32-bit range, so a fixed-size boolean array indexed by value is not viable. Membership has to go through a hash map.At least one element when getRandom is called→ getRandom never has to handle an empty set.
Approach 1: Hash Set with Linear Scan for Random
Intuition
A hash set handles membership checks, insertion, and deletion in O(1), so it covers insert and remove directly. The problem is getRandom: a hash set has no notion of position, so the only way to pick a random element is to copy all elements into a list and index into it.
That copy costs O(n) on every getRandom call, which breaks the O(1) requirement. The approach is correct but slow, and it isolates the exact bottleneck the optimal solution has to remove.
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:
Tracing the operations against a hash set: insert(1) adds 1, set becomes {1}, returns true. remove(2) finds nothing, returns false. insert(2) adds 2, set becomes {1, 2}, returns true. The first getRandom() copies {1, 2} into [1, 2] and returns 1 or 2. remove(1) removes 1, set becomes {2}, returns true. insert(2) finds 2 already present, returns false. The last getRandom() copies {2} into [2] and returns 2. Every getRandom rebuilds the array from scratch, which is the O(n) cost we want to eliminate.
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 rebuilding the array on every call. The next approach keeps a persistent array alongside the hash map, so random access by index is always available in O(1) without any copying.
Approach 2: Array + Hash Map (Optimal)
Intuition
Use the two data structures together, each covering the other's weakness. The array provides O(1) random access: generate a random index and return the element there. The hash map provides O(1) value-to-index lookup: given a value, find where it sits in the array without scanning.
Insert appends the new element to the end of the array and records its index in the hash map. getRandom picks a random index from 0 to size-1 and returns the array element there.
Removal is the operation that needs care. Deleting from the middle of an array normally costs O(n) because every later element shifts down by one. A set has no required order, so instead of shifting, move the last array element into the slot being vacated, update its index in the hash map, then pop the last element. The swap is one assignment, the pop is O(1), and the map sees one update and one deletion.
The invariant is that for every value in the array, valToIndex[value] equals its current array index. Insert preserves it by recording the new index before any other change. Remove preserves it by updating the moved element's index to the now-vacated slot before popping, so no stale index survives the operation.
When the value being removed is itself the last element, the swap assigns the slot to its own value and the index update is a no-op, then the pop discards it. The result is still correct, so no special case is needed.
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.
Handling duplicates
A common variant allows the same value to be stored more than once and still requires uniform random selection across all stored copies. The array stays the same, but a single value → index map cannot track several positions for one value. Replace it with value → set of indices. Insert appends and adds the new index to that value's set; remove pulls any one index from the set (and the swapped-in element updates its own set: remove the old last index, add the new one); getRandom still picks a uniform array index. Each operation stays O(1) on average because set insertion, removal, and membership are all O(1).