Insert Delete GetRandom O(1) - Duplicates allowed

Hard

#0368Time: `insert`: O(N) `remove`: O(N) `getRandom`: O(1) Where N is the number of elements in the collection.Space: O(N), where N is the number of elements in the collection, to store the elements in the list.6 companies

Patterns

Math Design Randomized

Data structures

Array Hash Table

Companies

LinkedIn Yelp Zeta Citadel

Prompt

RandomizedCollection is a data structure that contains a collection of numbers, possibly duplicates (i.e., a multiset). It should support inserting and removing specific elements and also reporting a random element.

Implement the RandomizedCollection class:

RandomizedCollection() Initializes the empty RandomizedCollection object.
bool insert(int val) Inserts an item val into the multiset, even if the item is already present. Returns true if the item is not present, false otherwise.
bool remove(int val) Removes an item val from the multiset if present. Returns true if the item is present, false otherwise. Note that if val has multiple occurrences in the multiset, we only remove one of them.
int getRandom() Returns a random element from the current multiset of elements. The probability of each element being returned is linearly related to the number of the same values the multiset contains.

You must implement the functions of the class such that each function works on average O(1) time complexity.

Note: The test cases are generated such that getRandom will only be called if there is at least one item in the RandomizedCollection.

Example 1:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

Explanation
RandomizedCollection randomizedCollection = new RandomizedCollection();
randomizedCollection.insert(1);   // return true since the collection does not contain 1.
                                  // Inserts 1 into the collection.
randomizedCollection.insert(1);   // return false since the collection contains 1.
                                  // Inserts another 1 into the collection. Collection now contains [1,1].
randomizedCollection.insert(2);   // return true since the collection does not contain 2.
                                  // Inserts 2 into the collection. Collection now contains [1,1,2].
randomizedCollection.getRandom(); // getRandom should:
                                  // - return 1 with probability 2/3, or
                                  // - return 2 with probability 1/3.
randomizedCollection.remove(1);   // return true since the collection contains 1.
                                  // Removes 1 from the collection. Collection now contains [1,2].
randomizedCollection.getRandom(); // getRandom should return 1 or 2, both equally likely.

Constraints:

-2³¹ <= val <= 2³¹ - 1
At most 2 * 10⁵ calls in total 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 simple ArrayList to store the elements of the collection. While this makes getRandom very efficient, the insert and remove operations suffer from linear time complexity because they require searching through the list.

Algorithm

Initialize an ArrayList list and a Random object.
For insert(val):
1. Check if val is in list using list.contains(val). This is an O(N) operation.
2. Add val to list.
3. Return the result of the check from step 1.
For remove(val):
1. Call list.remove(Integer.valueOf(val)) which finds and removes the first occurrence of val. This involves a search (O(N)) and a potential shift of elements (O(N)).
2. Return the boolean result from the remove call.
For getRandom():
1. Generate a random index from 0 to list.size() - 1.
2. Return the element at that index.

Walkthrough

We use a java.util.ArrayList<Integer> to store all the numbers in the collection, including duplicates.

insert(val): To check if the element was already present (as required for the return value), we must scan the list using list.contains(val), which takes O(N) time. Then, adding the element to the end of the list is an amortized O(1) operation. The overall complexity is dominated by the search, making it O(N).
remove(val): To remove an element, we use the ArrayList.remove(Object o) method. This method first needs to find the element, which takes O(N) time. After finding it, it removes the element and shifts all subsequent elements one position to the left to fill the gap, which also takes O(N) time in the worst case. Thus, the total time complexity is O(N).
getRandom(): This is the strong point of this approach. We can generate a random integer between 0 and the list's size minus one. Accessing an element at a random index in an ArrayList is an O(1) operation.

1class RandomizedCollection {2    List<Integer> list;3    Random rand;4 5    public RandomizedCollection() {6        list = new ArrayList<>();7        rand = new Random();8    }9 10    public boolean insert(int val) {11        boolean notPresent = !list.contains(val);12        list.add(val);13        return notPresent;14    }15 16    public boolean remove(int val) {17        // Note: This removes the first occurrence of val.18        return list.remove(Integer.valueOf(val));19    }20 21    public int getRandom() {22        return list.get(rand.nextInt(list.size()));23    }24}

Complexity

Time

`insert`: O(N) `remove`: O(N) `getRandom`: O(1) Where N is the number of elements in the collection.

Space

O(N), where N is the number of elements in the collection, to store the elements in the list.

Trade-offs

Pros

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

Cons

insert and remove operations have a time complexity of O(N), which fails to meet the problem's requirement of average O(1) time complexity for all functions.

This optimal approach combines the strengths of a HashMap for fast lookups and an ArrayList for O(1) random access. This allows all three operations (insert, remove, getRandom) to be performed in average O(1) time, even with duplicate elements.

Algorithm

Initialize an ArrayList list, a HashMap<Integer, Set<Integer>> map, and a Random object.
For insert(val):
1. Check if map contains val to determine the return value.
2. Add val to the end of list. The new index is list.size() - 1.
3. Add the new index to the Set associated with val in the map.
For remove(val):
1. If val is not in map, return false.
2. Get an index idxToRemove from the Set of indices for val.
3. Get the last element lastElement and its index lastIdx from list.
4. Replace the element at idxToRemove in list with lastElement.
5. Remove idxToRemove from the index set for val.
6. If idxToRemove is not the last index, update the index set for lastElement: remove lastIdx and add idxToRemove.
7. If the index set for val is now empty, remove val from the map.
8. Remove the last element from list.
9. Return true.
For getRandom():
1. Generate a random index from 0 to list.size() - 1.
2. Return the element at that index from list.

Walkthrough

The core idea is to use two data structures:

An ArrayList (list) to store all the elements. This allows for O(1) getRandom by picking a random index.
A HashMap<Integer, Set<Integer>> (map) where keys are the element values and values are Sets of indices where that element appears in the list. This allows for O(1) lookup of an element's locations. We use a LinkedHashSet for the set to ensure we can get an element (the first one) from it in O(1) time.

insert(val): We check if val is a key in our map to determine the return value. We then add val to the end of the list and add its new index (list.size() - 1) to the set of indices associated with val in the map. All these steps are average O(1).
remove(val): This is the most intricate part. A naive removal from the list would be O(N). To achieve O(1), we use a swap-and-pop strategy:
1. Get an index of val to remove, idxToRemove, from its corresponding set in the map.
2. Get the last element in the list, lastElement, and its index, lastIdx.
3. Move lastElement to the position idxToRemove in the list.
4. Remove the last element from the list (which is now a duplicate of the element at idxToRemove). This is an O(1) operation.
5. Update the map to reflect these changes: remove idxToRemove from val's index set, and for lastElement, remove lastIdx and add idxToRemove to its index set. This logic correctly handles all cases, including when the element to be removed is the last element or when it's the same as the last element.
getRandom(): We generate a random index and return the element from the list at that index. This is O(1).

1class RandomizedCollection {2    private List<Integer> list;3    private Map<Integer, Set<Integer>> map;4    private Random rand = new Random();5 6    public RandomizedCollection() {7        list = new ArrayList<>();8        map = new HashMap<>();9    }10 11    public boolean insert(int val) {12        boolean notPresent = !map.containsKey(val);13        map.computeIfAbsent(val, k -> new LinkedHashSet<>()).add(list.size());14        list.add(val);15        return notPresent;16    }17 18    public boolean remove(int val) {19        if (!map.containsKey(val)) {20            return false;21        }22 23        Set<Integer> valIndices = map.get(val);24        int idxToRemove = valIndices.iterator().next();25 26        int lastIdx = list.size() - 1;27        int lastElement = list.get(lastIdx);28 29        list.set(idxToRemove, lastElement);30        valIndices.remove(idxToRemove);31 32        Set<Integer> lastElementIndices = map.get(lastElement);33        if (idxToRemove != lastIdx) {34            lastElementIndices.remove(lastIdx);35            lastElementIndices.add(idxToRemove);36        }37 38        if (valIndices.isEmpty()) {39            map.remove(val);40        }41 42        list.remove(lastIdx);43 44        return true;45    }46 47    public int getRandom() {48        return list.get(rand.nextInt(list.size()));49    }50}

Complexity

Time

`insert`: O(1) `remove`: O(1) `getRandom`: O(1) All complexities are on average, due to hash map operations and amortized time for ArrayList additions.

Space

O(N), where N is the total number of elements. The `list` stores N elements, and the `map` stores U unique elements as keys, with a total of N indices stored across all the sets.

Trade-offs

Pros

Achieves the required average O(1) time complexity for all operations.
Efficiently handles duplicate elements.

Cons

More complex to implement and debug compared to a simpler approach.
Uses more memory due to the overhead of the HashMap and Set objects.

Solutions

Solution

1class RandomizedCollection { private Map < Integer , Set < Integer >> m ; private List < Integer > l ; private Random rnd ; /** Initialize your data structure here. */ public RandomizedCollection () { m = new HashMap <>(); l = new ArrayList <>(); rnd = new Random (); } /** * Inserts a value to the collection. Returns true if the collection did not already contain * the specified element. */ public boolean insert ( int val ) { m . computeIfAbsent ( val , k -> new HashSet <>()). add ( l . size ()); l . add ( val ); return m . get ( val ). size () == 1 ; } /** * Removes a value from the collection. Returns true if the collection contained the specified * element. */ public boolean remove ( int val ) { if (! m . containsKey ( val )) { return false ; } Set < Integer > idxSet = m . get ( val ); int idx = idxSet . iterator (). next (); int lastIdx = l . size () - 1 ; l . set ( idx , l . get ( lastIdx )); idxSet . remove ( idx ); Set < Integer > lastIdxSet = m . get ( l . get ( lastIdx )); lastIdxSet . remove ( lastIdx ); if ( idx < lastIdx ) { lastIdxSet . add ( idx ); } if ( idxSet . isEmpty ()) { m . remove ( val ); } l . remove ( lastIdx ); return true ; } /** Get a random element from the collection. */ public int getRandom () { int size = l . size (); return size == 0 ? - 1 : l . get ( rnd . nextInt ( size )); } } /** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection obj = new RandomizedCollection(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */

1from collections import defaultdict from random import choice class RandomizedCollection : # official solution def __init__ ( self ): """ Initialize your data structure here. """ self . lst = [] self . dict = defaultdict ( set ) # change from 381 (with no duplicates) def insert ( self , val : int ) -> bool : """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. """ self . dict [ val ]. add ( len ( self . lst )) self . lst . append ( val ) return len ( self . dict [ val ]) == 1 ''' >>> a = set([1,1,2,3]) >>> a {1, 2, 3} >>> a.pop() 1 >>> a {2, 3} ''' def remove ( self , val : int ) -> bool : """ Removes a value from the collection. Returns true if the collection contained the specified element. """ if not self . dict [ val ]: return False remove_index , last_val = self . dict [ val ]. pop (), self . lst [ - 1 ] # pop() on a set self . lst [ remove_index ] = last_val self . dict [ last_val ]. add ( remove_index ) self . dict [ last_val ]. discard ( len ( self . lst ) - 1 ) self . lst . pop () return True def getRandom ( self ) -> int : """ Get a random element from the collection. """ return choice ( self . lst ) # Your RandomizedCollection object will be instantiated and called as such: # obj = RandomizedCollection() # 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