Insert Delete GetRandom O(1)

Med

#0367Time: `insert`: O(N) `remove`: O(N) `getRandom`: O(1) The `insert` and `remove` operations do not meet the problem's requirements for average O(1) time complexity.Space: O(N), where N is the number of elements stored in the set, as we need to store each element in the `ArrayList`.40 companies

Patterns

Math Design Randomized

Data structures

Array Hash Table

Companies

Agoda ByteDance Cisco Docusign

Prompt

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:

-2³¹ <= val <= 2³¹ - 1
At most 2 * 10⁵ calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a single ArrayList (or a dynamic array) to store the elements of the set. While this makes the getRandom operation trivial and efficient, the insert and remove operations suffer from poor performance because they require searching through the list.

Algorithm

Initialize an ArrayList list to store the elements.
For insert(val):
1. Check if list already contains val by iterating through it. This is an O(N) operation.
2. If it does, return false.
3. Otherwise, add val to the end of list (amortized O(1)) and return true.
For remove(val):
1. Find the element val in the list, which takes O(N) time.
2. If found, remove it. This also takes O(N) time as subsequent elements need to be shifted.
3. Return true if the element was found and removed, false otherwise.
For getRandom():
1. Generate a random integer randomIndex from 0 to list.size() - 1.
2. Return the element at list.get(randomIndex), which is an O(1) operation.

Walkthrough

In this straightforward but inefficient method, we rely solely on an ArrayList to hold the set's elements.

insert(val): To insert a value, we must first ensure it's not already present to maintain the uniqueness property of a set. This involves a linear scan through the ArrayList using list.contains(val), which takes O(N) time, where N is the number of elements. If the element isn't found, we append it to the end of the list, an operation that is amortized O(1). However, the overall complexity is dominated by the search, making it O(N).
remove(val): To remove a value, we again need to find its location in the list. The list.remove(Object) method conveniently does this, but it performs a linear search (O(N)) and, upon finding the element, may need to shift up to N-1 elements to fill the gap, resulting in an overall O(N) time complexity.
getRandom(): This is the one efficient operation in this approach. We can get the current size of the list, generate a random index between 0 and size - 1, and return the element at that index. This is a constant time, O(1), operation.

1class RandomizedSet {2    List<Integer> list;3    Random rand;4 5    public RandomizedSet() {6        list = new ArrayList<>();7        rand = new Random();8    }9 10    public boolean insert(int val) {11        if (list.contains(val)) {12            return false;13        }14        list.add(val);15        return true;16    }17 18    public boolean remove(int val) {19        // list.remove(Integer.valueOf(val)) searches for the element (O(N))20        // and then removes it (O(N)), for a total of O(N).21        return list.remove(Integer.valueOf(val));22    }23 24    public int getRandom() {25        int randomIndex = rand.nextInt(list.size());26        return list.get(randomIndex);27    }28}

Complexity

Time

`insert`: O(N) `remove`: O(N) `getRandom`: O(1) The `insert` and `remove` operations do not meet the problem's requirements for average O(1) time complexity.

Space

O(N), where N is the number of elements stored in the set, as we need to store each element in the `ArrayList`.

Trade-offs

Pros

Simple to understand and implement.
The getRandom operation is highly efficient with O(1) time complexity.

Cons

The insert operation is O(N) due to the linear scan required to check for duplicates.
The remove operation is O(N) due to the linear scan to find the element and the subsequent shifting of elements upon removal.
Fails to meet the problem's requirement of average O(1) time complexity for all functions.

This optimal approach cleverly combines a HashMap and an ArrayList to leverage the strengths of both data structures. The ArrayList stores the elements, providing O(1) time for random access (getRandom). The HashMap maps each element to its index in the ArrayList, enabling O(1) average time for lookups, insertions, and deletions.

Algorithm

Initialize an ArrayList list, a HashMap map, and a Random object.
For insert(val):
1. If val is already a key in map, return false.
2. Add val to the end of list. The new index is list.size() - 1.
3. Put the key-value pair (val, new_index) into map.
4. Return true.
For remove(val):
1. If val is not in map, return false.
2. Get indexToRemove of val from map.
3. Get lastElement from the end of list.
4. Copy lastElement to list at indexToRemove.
5. Update the index of lastElement in map to indexToRemove.
6. Remove the last element from list (an O(1) operation).
7. Remove val from map.
8. Return true.
For getRandom():
1. Generate a random integer randomIndex from 0 to list.size() - 1.
2. Return the element at list.get(randomIndex).

Walkthrough

To achieve O(1) average time for all operations, we use two data structures in tandem:

ArrayList<Integer> list: Stores the actual elements. This allows for O(1) time complexity for getRandom() by picking a random index.
Map<Integer, Integer> map: Maps each element's value to its index in the list. This provides O(1) average time complexity for checking existence, which is crucial for insert and remove.

Operation Details:

insert(val): We first check if val exists by looking it up in the map (O(1)). If it's absent, we append val to the list and store its new index (list.size() - 1) in the map. Both steps are O(1) on average.
remove(val): This is the key part of the algorithm. A standard removal from an ArrayList index is O(N). To make it O(1), we perform a swap:
1. Find the index of the element to remove, indexToRemove, from the map (O(1)).
2. Take the last element in the list.
3. Place this last element at indexToRemove.
4. Update the map with the new index for the moved element.
5. Now, remove the last element from the list. This is an O(1) operation.
6. Finally, remove the original val from the map. This sequence of O(1) operations results in an overall O(1) average time for removal.
getRandom(): This is straightforward. We get a random index within the bounds of the current list size and return the element at that index, which is an O(1) operation.

1class RandomizedSet {2    private List<Integer> list;3    private Map<Integer, Integer> map;4    private Random rand;5 6    public RandomizedSet() {7        list = new ArrayList<>();8        map = new HashMap<>();9        rand = new Random();10    }11 12    public boolean insert(int val) {13        if (map.containsKey(val)) {14            return false;15        }16        map.put(val, list.size());17        list.add(val);18        return true;19    }20 21    public boolean remove(int val) {22        if (!map.containsKey(val)) {23            return false;24        }25 26        int indexToRemove = map.get(val);27        int lastElement = list.get(list.size() - 1);28 29        // Move the last element to the place of the element to delete30        list.set(indexToRemove, lastElement);31        map.put(lastElement, indexToRemove);32 33        // Remove the last element from list and map34        list.remove(list.size() - 1);35        map.remove(val);36 37        return true;38    }39 40    public int getRandom() {41        return list.get(rand.nextInt(list.size()));42    }43}

Complexity

Time

`insert`: O(1) average `remove`: O(1) average `getRandom`: O(1) All operations meet the problem's time complexity requirements. `ArrayList.add` is amortized O(1), and `HashMap` operations are O(1) on average.

Space

O(N), where N is the number of elements in the set. We need space to store N elements in the `ArrayList` and N key-value pairs in the `HashMap`.

Trade-offs

Pros

Achieves the required average O(1) time complexity for insert, remove, and getRandom operations.
Highly efficient and scalable for a large number of calls.

Cons

Requires more space than a single data structure, as elements are stored in both the list and the map.
The implementation is more complex, particularly the logic for the remove operation.

Solutions

Solution

1public class RandomizedSet { private Dictionary < int , int > d = new Dictionary < int , int >(); private List < int > q = new List < int >(); public RandomizedSet () { } public bool Insert ( int val ) { if ( d . ContainsKey ( val )) { return false ; } d . Add ( val , q . Count ); q . Add ( val ); return true ; } public bool Remove ( int val ) { if (! d . ContainsKey ( val )) { return false ; } int i = d [ val ]; d [ q [ q . Count - 1 ]] = i ; q [ i ] = q [ q . Count - 1 ]; q . RemoveAt ( q . Count - 1 ); d . Remove ( val ); return true ; } public int GetRandom () { return q [ new Random (). Next ( 0 , q . Count )]; } } /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * bool param_1 = obj.Insert(val); * bool param_2 = obj.Remove(val); * int param_3 = obj.GetRandom(); */

1class RandomizedSet { private Map < Integer , Integer > d = new HashMap <>(); private List < Integer > q = new ArrayList <>(); private Random rnd = new Random (); public RandomizedSet () { } public boolean insert ( int val ) { if ( d . containsKey ( val )) { return false ; } d . put ( val , q . size ()); q . add ( val ); return true ; } public boolean remove ( int val ) { if (! d . containsKey ( val )) { return false ; } int i = d . get ( val ); d . put ( q . get ( q . size () - 1 ), i ); q . set ( i , q . get ( q . size () - 1 )); q . remove ( q . size () - 1 ); d . remove ( val ); return true ; } public int getRandom () { return q . get ( rnd . nextInt ( q . size ())); } } /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */ ///////// public class Insert_Delete_GetRandom_O_1 { public static void main ( String [] args ) { Insert_Delete_GetRandom_O_1 out = new Insert_Delete_GetRandom_O_1 (); // Init an empty set. RandomizedSet randomSet = out . new RandomizedSet (); System . out . println ( randomSet . remove ( 0 )); System . out . println ( randomSet . remove ( 0 )); System . out . println ( randomSet . insert ( 0 )); System . out . println ( randomSet . insert ( 0 )); System . out . println ( randomSet . insert ( 0 )); System . out . println ( randomSet . getRandom ()); System . out . println ( randomSet . remove ( 0 )); System . out . println ( randomSet . insert ( 0 )); } class RandomizedSet { List < Integer > list ; Map < Integer , Integer > map ; // val => its index in list Random random ; /** Initialize your data structure here. */ public RandomizedSet () { list = new ArrayList <>(); map = new HashMap <>(); random = new Random (); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ public boolean insert ( int val ) { if ( map . containsKey ( val )) { return false ; } int pos = list . size (); list . add ( val ); map . put ( val , pos ); return true ; } /** Removes a value from the set. Returns true if the set contained the specified element. */ public boolean remove ( int val ) { if (! map . containsKey ( val )) { return false ; } // swap val to end of list, then remove it int pos = map . get ( val ); int lastVal = list . get ( list . size () - 1 ); list . set ( pos , lastVal ); list . remove ( list . size () - 1 ); map . put ( lastVal , pos ); // @note: missed this line map . remove ( val ); return true ; } /** Get a random element from the set. */ public int getRandom () { int randIndex = random . nextInt ( list . size ()); return list . get ( randIndex ); } } /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */ }

1class RandomizedSet { public: RandomizedSet () { } bool insert ( int val ) { if ( d . count ( val )) { return false ; } d [ val ] = q . size (); q . push_back ( val ); return true ; } bool remove ( int val ) { if ( ! d . count ( val )) { return false ; } int i = d [ val ]; d [ q . back ()] = i ; q [ i ] = q . back (); q . pop_back (); d . erase ( val ); return true ; } int getRandom () { return q [ rand () % q . size ()]; } private: unordered_map < int , int > d ; vector < int > q ; }; /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet* obj = new RandomizedSet(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */

1''' my_dict.pop('b') # vs del d[k] my_dict = {'a': 1, 'b': 2, 'c': 3} val = my_dict.pop('b') print(my_dict) # {'a': 1, 'c': 3} print(val) # 2 >>> item = my_dict.pop() Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: pop expected at least 1 argument, got 0 >>> my_dict = {'a': 1, 'b': 2, 'c': 3} >>> del my_dict['b'] >>> my_dict {'a': 1, 'c': 3} ''' from collections import defaultdict from random import choice class RandomizedSet ( object ): def __init__ ( self ): """ Initialize your data structure here. """ # value (map) -> its index -> value (list) self . d = {} self . a = [] # introduce it purely for random def insert ( self , val ): """ Inserts a value to the set. Returns true if the set did not already contain the specified element. :type val: int :rtype: bool """ if val in self . d : return False self . a . append ( val ) self . d [ val ] = len ( self . a ) - 1 return True def remove ( self , val ): """ Removes a value from the set. Returns true if the set contained the specified element. :type val: int :rtype: bool """ if val not in self . d : return False index = self . d [ val ] # process last index/val self . a [ index ] = self . a [ - 1 ] self . d [ self . a [ - 1 ]] = index # process to be deleted index/val self . a . pop () # delete in list del self . d [ val ] # delete in dict # or, self.d.pop(val) return True def getRandom ( self ): """ Get a random element from the set. :rtype: int """ return self . a [ random . randrange ( 0 , len ( self . a ))] # return random.choice(self.a) ############ # Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom() ''' >>> import random >>> random.choice([1,2,3,4,5]) 3 >>> random.choice([1,2,3,4,5]) 4 >>> random.choice([1,2,3,4,5]) 4 ''' class RandomizedSet : def __init__ ( self ): self . m = {} self . l = [] def insert ( self , val : int ) -> bool : if val in self . m : return False self . m [ val ] = len ( self . l ) self . l . append ( val ) return True def remove ( self , val : int ) -> bool : if val not in self . m : return False idx = self . m [ val ] self . l [ idx ] = self . l [ - 1 ] self . m [ self . l [ - 1 ]] = idx self . l . pop () self . m . pop ( val ) return True def getRandom ( self ) -> int : return random . choice ( self . l ) # Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem