Watch 10 video solutions for Insert Delete GetRandom O(1), a medium level problem involving Array, Hash Table, Math. This walkthrough by NeetCode has 61,093 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.You must implement the functions of the class such that each function works in average O(1) time complexity.
Example 1:
Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Output [null, true, false, true, 2, true, false, 2] Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
Constraints:
-231 <= val <= 231 - 12 * 105 calls will be made to insert, remove, and getRandom.getRandom is called.Problem Overview: Design a data structure that supports insert(val), remove(val), and getRandom() in average O(1) time. The random operation must return each stored element with equal probability.
Approach 1: Divide and Conquer Approach (Array + Hash Map) (Time: O(1), Space: O(n))
The key idea is combining a dynamic array with a hash map. The array stores elements so you can pick a random value in constant time using a random index. The hash map stores value → index so you can locate elements instantly during deletion. When removing a value, swap it with the last element in the array, update the hash map for the swapped value, and then pop the last element. This avoids expensive shifting operations and keeps deletion O(1). Hash lookups and updates provide constant time access, which makes all three operations efficient. This design heavily relies on concepts from Hash Table and Array data structures.
Approach 2: Iterative Approach using Heap Sort (Time: O(log n), Space: O(n))
A less optimal design stores values inside a heap-like structure where insertions and deletions follow heap operations. Insert pushes the element and rebalances the heap in O(log n). Removal searches and restructures the heap afterward. Random selection can be simulated by choosing a random index from the heap array representation, but heap adjustments during updates increase the complexity. While workable, this structure sacrifices the constant-time requirement and mainly demonstrates how iterative heap-based structures manage dynamic collections. Concepts overlap with Design and randomized data structures.
Recommended for interviews: Interviewers expect the array + hash map design. It demonstrates understanding of constant-time hash lookups and how swapping with the last array element avoids costly deletions. Discussing the heap-based or naive structures first shows awareness of tradeoffs, but the hash map + array combination is the standard optimal solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer (Array + Hash Map) | O(1) average for insert, delete, getRandom | O(n) | General case when constant-time operations are required |
| Iterative using Heap Sort | O(log n) insert/delete, O(1) random access | O(n) | When using heap-based structures or learning alternative dynamic storage approaches |