Leetcode 380. Insert Delete GetRandom O(1)
Asked at:
Udemy
DocuSign
Bloomberg
DESCRIPTION
Design a data structure that supports insert, remove, and getRandom operations, all in average O(1) time. The insert(val) adds an element if not present, remove(val) deletes an element if present, and getRandom() returns a uniformly random element from the current set. For example, after inserting 1, 2, 3 and removing 2, calling getRandom() should return 1 or 3 with equal probability.
Input:
insert(1) → true insert(2) → true insert(2) → false getRandom() → 1 or 2 remove(1) → true getRandom() → 2
Output:
Operations return: true, true, false, (1 or 2), true, 2
Explanation: First two inserts succeed, third fails (duplicate). Random returns existing element. After removing 1, only 2 remains.
Constraints:
- Values are integers within standard 32-bit range
- At most 2×10⁵ operations will be called
- getRandom() is only called when at least one element exists
- Each operation must run in average O(1) time
Understanding the Problem
The core challenge is achieving O(1) random access while maintaining O(1) insert/remove. Hash tables provide O(1) lookup but can't access arbitrary elements by index. Arrays support O(1) random indexing but require O(n) search for removal. We need a hybrid approach that combines both data structures, using a dynamic array for indexed access and a hash map for position tracking.
Building Intuition
A naive approach using only a hash set achieves O(1) insert/remove but requires O(n) for getRandom() (iterate to random position). The key insight is to maintain elements in an array for O(1) random indexing while using a hash map to store each element's array index for O(1) removal. When removing, swap the target with the last element, update the swapped element's index in the map, then pop the array—avoiding expensive shifts.
This pattern appears in caching systems (evict random entries), load balancers (select random server), and sampling algorithms (uniform selection from dynamic sets). Understanding the array-hashmap duality enables building efficient randomized data structures used in distributed systems and probabilistic algorithms.
Common Pitfalls
Implementation
Core Data Structure Setup
Initialize the dual storage system: a dynamic array (nums) to store elements for O(1) random access, and a hash map (valToIndex) mapping each value to its array index for O(1) existence checks. This foundation enables all three operations to work efficiently. For example, after inserting 5 and 10, nums = [5, 10] and valToIndex = {5: 0, 10: 1}.
import randomclass RandomizedSet:def __init__(self):self.nums = []self.valToIndex = {}
Insert Operation
Check if the value exists using the hash map in O(1). If absent, append to the array and record its index in the map, then return true. If present, return false without modification. For example, inserting 7 into nums = [5, 10] results in nums = [5, 10, 7] and valToIndex = {5: 0, 10: 1, 7: 2}.
def insert(self, val: int) -> bool:if val in self.valToIndex:return Falseself.valToIndex[val] = len(self.nums)self.nums.append(val)return True
Remove Operation
Check existence via the hash map. If present, retrieve its index, swap it with the last array element, update the swapped element's index in the map, then pop the array and delete the map entry. This avoids O(n) shifting. For example, removing 5 from nums = [5, 10, 7] swaps to [7, 10, 5], updates valToIndex[7] = 0, then pops to [7, 10].
def remove(self, val: int) -> bool:if val not in self.valToIndex:return Falseidx = self.valToIndex[val]lastVal = self.nums[-1]self.nums[idx] = lastValself.valToIndex[lastVal] = idxself.nums.pop()del self.valToIndex[val]return True
Get Random Operation
Generate a random index between 0 and len(nums) - 1, then return nums[randomIndex] in O(1). Since all elements are contiguous in the array, each has equal probability 1/n. For example, with nums = [7, 10], generate index 0 or 1 with 50% probability each.
def getRandom(self) -> int:randomIndex = random.randint(0, len(self.nums) - 1)return self.nums[randomIndex]
What We've Learned
- Pattern: Combine array (O(1) indexing) + hash map (O(1) lookup) for dual-access data structures
- Technique: Swap-with-last-and-pop enables O(1) removal without maintaining order
- Use Case: Randomized algorithms requiring uniform sampling from dynamic sets (caches, load balancers)
Problems to Practice
medium
This is another data structure design problem requiring implementation of multiple methods with specific time complexity requirements. Like Insert Delete GetRandom, it tests the ability to combine multiple data structures (arrays/hashmaps) to achieve efficient operations.
medium
This problem involves maintaining a collection with efficient access to specific elements, similar to getRandom(). It requires understanding how to use appropriate data structures (heap) to achieve O(1) or O(log n) operations for insertion and retrieval.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late April, 2026
Bloomberg
Senior
Mid April, 2026
DocuSign
Senior
It was not the full problem, a very brief description without constraints, "implement insert, delete, and get random". The expected solution is O(1). Follow-ups: multithreading, make it generic, deep dive into data structures, and DS Java implementations.
Late March, 2026
Staff
Was asked the hard variation of this question
Hello Interview Premium
Your account is free and you can post anonymously if you choose.