380. Insert Delete GetRandom O(1)
Asked at Apple, Uber, LinkedIn
Difficulty
Medium
Time
O(1) average per operation
Space
O(n)
Pattern
Array
Companies
3
Problem
Design a class RandomizedSet that stores a set of integers and supports three operations, each in average O(1) time.
insert(val) adds val to the set. It returns true if val was not there before, and false if it was already present.
remove(val) deletes val from the set. It returns true if val was there, and false if it was not.
getRandom() returns one element from the current set, picked uniformly at random. Every element must have the same chance of being returned. It is guaranteed the set is not empty when this method is called.
The hard part is getRandom. A plain hash set gives O(1) insert and remove, but it cannot pick a random element quickly. A plain array gives O(1) random access, but removing from the middle is slow. You need both structures together.
Two structures, two jobs
Constraints
- ●
-2^31 <= val <= 2^31 - 1 - ●
At most 2 * 10^5 calls in total to insert, remove and getRandom - ●
getRandom is only called when the set has at least one element
Examples
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []][null, true, false, true, 2, true, false, 2]Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
| Medium | View all LinkedIn questions → |
How to Think About It
Key insight: use an array for O(1) random access and a hash map for O(1) lookups. The hash map stores each value's index in the array. The array stores the actual values.
Insert: append the value to the array. Store its index in the hash map. Both are O(1).
Delete: this is the tricky part. You cannot leave a gap in the array. Swap the element to delete with the last element, then remove the last element. Update the hash map for the swapped element. This avoids shifting and keeps it O(1).
Why the swap trick works: instead of deleting from the middle (which leaves a gap), you move the last element into the gap and delete the last element. The hash map for the moved element is updated to its new index.
Optimal Approach
Use an array vals and a hash map index_map mapping each value to its index in the array.
Insert(val): append val to vals, store its index in index_map. O(1).
Remove(val): get the index from index_map. Swap vals[index] with vals[-1]. Update index_map for the swapped element. Pop the last element. Remove val from index_map. O(1).
GetRandom(): return vals[random(0, len(vals)-1)]. O(1).
Walkthrough with insert(1), insert(2), remove(1), getRandom:
- insert(1): vals=[1], index_map={1:0}
- insert(2): vals=[1,2], index_map={1:0, 2:1}
- remove(1): index=0. Swap vals[0] with vals[1]: vals=[2,1]. Pop: vals=[2]. Update index_map: {2:0}. Remove 1: {2:0}
- getRandom: vals=[2], return 2.
Time: all O(1) average. Space: O(n) for array and hash map.
Remove by swapping with the last element
What Trips People Up in Real Interviews
Forgetting to update the hash map after the swap. When you move the last element into the deleted position, you must update its index in the hash map. Otherwise, future deletes will use a stale index.
Deleting from the wrong position. Always swap with the LAST element, not an arbitrary element. Swapping with a middle element does not avoid the gap problem.
Using a HashSet instead of a HashMap. You need the index mapping for O(1) delete. A HashSet cannot tell you where the element is in the array.
Not handling the case where the element to delete IS the last element. In that case, no swap is needed, just pop and remove from the map. The swap logic should check for this.
getRandom must be truly uniform. Each element in the array should have equal probability. Since you always maintain a contiguous array, random_index = random(0, len-1) gives uniform distribution.
Solution Code
O(1) average per operation timeimport random
class RandomizedSet:
def __init__(self):
self.vals = []
self.index_map = {}
def insert(self, val):
if val in self.index_map:
return False
self.index_map[val] = len(self.vals)
self.vals.append(val)
return True
def remove(self, val):
if val not in self.index_map:
return False
idx = self.index_map[val]
last = self.vals[-1]
self.vals[idx] = last
self.index_map[last] = idx
self.vals.pop()
del self.index_map[val]
return True
def getRandom(self):
return random.choice(self.vals)Frequently Asked Questions
What is the Insert Delete GetRandom O(1) problem?
Design a data structure that supports insert, delete, and getRandom operations, all in `O(1)` average time. This problem tests your ability to combine a hash map with an array to achieve constant-time operations.
How do you solve Insert Delete GetRandom O(1)?
The optimal approach runs in O(1) average per operation time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Insert Delete GetRandom O(1)?
Insert Delete GetRandom O(1) is asked at Apple, Uber, LinkedIn. It is a medium difficulty problem.
What are common mistakes on Insert Delete GetRandom O(1)?
- Forgetting to update the hash map after the swap. When you move the last element into the deleted position, you must update its index in the hash map. Otherwise, future deletes will use a stale index.
- Deleting from the wrong position. Always swap with the LAST element, not an arbitrary element. Swapping with a middle element does not avoid the gap problem.
- Using a `HashSet` instead of a `HashMap`. You need the index mapping for `O(1)` delete. A `HashSet` cannot tell you where the element is in the array.
- Not handling the case where the element to delete IS the last element. In that case, no swap is needed, just pop and remove from the map. The swap logic should check for this.
- getRandom must be truly uniform. Each element in the array should have equal probability. Since you always maintain a contiguous array, `random_index = random(0, len-1)` gives uniform distribution.