381. Insert Delete GetRandom O(1) - Duplicates allowed

HardDesignArrayHash TableMathRandomized

Problem Description

The RandomizedCollection problem requires creating a data structure that can handle multiple occurrences of the same number (a multiset). The key operations that need to be supported are:

Inserting an element: it should insert any integer, even if that integer is already present in the collection. After insertion, it should return true if the element was not already in the collection, and false if it was.
Removing an element: it should remove a specified integer from the collection if it is present, but only one instance of it (in case there are duplicates). Upon removal, it should return true if the element was present and removed, and false if the element was not found.
Getting a random element: it should return a random element from the collection, with the constraint that each element's likelihood of being chosen is proportional to its frequency in the collection. In other words, if a number appears twice in the collection, it's twice as likely to be chosen.

The challenge is that all these operations need to be implemented in such a way that on average, they have an O(1) time complexity, meaning they should be very efficient and not depend on the size of the collection.

Intuition

For all the operations to be efficient, especially insertions and removals, it's crucial to have instant access to the elements and their indices. A list (or an array) allows for constant-time access by index, which is perfect for getRandom. However, removals from arrays can be costly—O(n) in the worst case—as elements have to be shifted.

To achieve O(1) complexity for removals and insertions, the solution uses an additional hash table (a dictionary in Python) to keep track of the indices of values in the array. Python's built-in set is used in the hash table to handle the indices due to two reasons:

Each element can appear more than once, and their indices need to be tracked.
Sets allow for constant-time addition and removal of indices.

Therefore, the solution combines a list (to store elements) with a dictionary of sets (to map elements to their indices in the list):

Insertion: Add the new element to the end of the list and record its index in the corresponding set in the dictionary. If the element is not in the dictionary, add it and create a new set. The bool return value is given by checking the size of this set before the insertion.
Removal: Find an index of the element to remove by checking the dictionary. Swap the element to remove with the last element in the list to maintain a contiguous block of elements and avoid O(n) shifting. Update the sets in the dictionary to reflect the swapped and removed indices. If there are no more instances of the element to remove in the list, remove the element from the dictionary.
Get Random: Since the elements in the list are in a contiguous block, you can use random choice to select an element from the list efficiently.

This combination of a list and a dictionary of sets allows the RandomizedCollection to support the required operations efficiently, achieving the average O(1) time complexity for each operation.

Learn more about Math patterns.

Solution Approach

The implementation of the RandomizedCollection class leverages two primary data structures: a Python list (self.l) to store the elements of the collection and a Python dictionary (self.m) to map values to sets of indices where these values occur in the list. Here's how each method in the solution corresponds to the required operation and the algorithms or patterns used:

__init__(self): The constructor initializes an empty dictionary (self.m) and an empty list (self.l). The list is used for storing all the elements of the RandomizedCollection including duplicates. The dictionary will hold sets of indices that indicate where in the list each element can be found.
insert(self, val: int) -> bool: When inserting a new value:
- The method first retrieves or initializes the set of indices for val in the dictionary.
- It then adds the index of the new list entry (which is len(self.l)) to the index set and updates the dictionary.
- The value is appended to the list.
- The method returns True if it's the first occurrence of val (by checking if the length of the index set is 1) or False otherwise.
remove(self, val: int) -> bool: When removing a value:
- The method checks if val is in the dictionary; if not, it returns False.
- Take one of the indices of val from its index set (idx) and retrieve the last element's index in the list (last_idx).
- Swap the element at idx with the last element in the list, so now the element to be removed is at the end of the list.
- Update the index sets for both the element being removed and the last element that was swapped.
- Pop the last element off the list (self.l.pop()), effectively removing val.
- If the index set is empty (no more occurrences of val), remove val from the dictionary.
- Return True since the element was successfully removed.
getRandom(self) -> int: To get a random element:
- The method simply uses Python's random.choice to return a random element from the list. Since the elements are stored continuously, and random.choice has an O(1) complexity for lists, this achieves the required constant time complexity.
- The guarantee from the problem statement that getRandom will only be called when there is at least one element in the collection allows for the list to be directly used without checking for emptiness.

The core idea of this solution approach is to manage the trade-offs in the fundamental operations of different data structures to achieve the desired average constant time complexity (O(1)) for all operations requested. The use of a dictionary of sets allows us to remove elements efficiently while maintaining the ability to access elements randomly, and the list allows for constant-time random access and easy retrieval of elements.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the following sequence of operations to illustrate the solution approach:

Insert 10
Insert 10
Insert 20
Remove 10
GetRandom

Step 1: Insert 10

self.l = [10]
self.m = {10: {0}}
Return True since 10 was not already in the collection.

Step 2: Insert 10 Again

self.l = [10, 10]
self.m = {10: {0, 1}}
Return False because 10 is already in the collection.

Step 3: Insert 20

self.l = [10, 10, 20]
self.m = {10: {0, 1}, 20: {2}}
Return True since 20 was not already in the collection.

Step 4: Remove 10

The element 10 appears twice, so any index can be used. Let's use the last index for 10, which is 1.
Swap the element at index 1 (second 10) with the last element (20).
Updated list: self.l = [10, 20]
Updated indices in self.m: {10: {0}, 20: {1}}
There is still one occurrence of 10 in the list, so no need to remove it from the dictionary.
Return True since 10 was present and removed.

Step 5: GetRandom

The list (self.l) is now [10, 20]. Both elements have an equal chance of being chosen.
A call to random.choice could return either 10 or 20 with equal probability.

Through this example, each step executed maintains an average O(1) time complexity, illustrating the efficiency of the RandomizedCollection data structure as designed. The key here is the combination of the list for random access and element storage, and the dictionary of sets for managing indices, all facilitating efficient inserts, removals, and random element retrieval.

Solution Implementation

1import random
2
3class RandomizedCollection:
4    def __init__(self):
5        """
6        Initialize your data structure here.
7        """
8        self.value_to_indices = {}  # Maps a value to a set containing indices of where the value appears in the list
9        self.values_list = []  # List to store all values (including duplicates)
10
11    def insert(self, val: int) -> bool:
12        """
13        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
14        """
15        is_new_value = val not in self.value_to_indices  # Checks if the value is new to the collection
16        # Get the set of indices for the current value, or an empty set if the value is being inserted for the first time
17        indices = self.value_to_indices.get(val, set())
18        indices.add(len(self.values_list))  # Add the index of the new value to the indices set
19        self.value_to_indices[val] = indices  # Update the mapping
20        self.values_list.append(val)  # Add the value to the list
21        return is_new_value  # Return true if it was a new value
22
23    def remove(self, val: int) -> bool:
24        """
25        Removes a value from the collection. Returns true if the collection contained the specified element.
26        """
27        if val not in self.value_to_indices:
28            return False  # The value is not present in the collection
29
30        # Get one of the indices of the value to be removed
31        idx_to_remove = next(iter(self.value_to_indices[val]))
32        last_index = len(self.values_list) - 1
33        # Move the last element to the place of the element to remove
34        self.values_list[idx_to_remove] = self.values_list[last_index]
35      
36        # Update the indices set of the last element
37        self.value_to_indices[self.values_list[last_index]].add(idx_to_remove)
38        self.value_to_indices[self.values_list[last_index]].discard(last_index)
39      
40        # Remove the index of the removed element from its indices set
41        self.value_to_indices[val].discard(idx_to_remove)
42        if not self.value_to_indices[val]:
43            # If the set is empty, remove the value from the mapping
44            del self.value_to_indices[val]
45      
46        self.values_list.pop()  # Remove the last element from the list
47        return True
48
49    def getRandom(self) -> int:
50        """
51        Get a random element from the collection.
52        """
53        # Return a random value from the list if it's not empty, otherwise return -1
54        return random.choice(self.values_list) if self.values_list else -1
55
56# Usage example
57# randomized_collection = RandomizedCollection()
58# insert_result = randomized_collection.insert(val)
59# remove_result = randomized_collection.remove(val)
60# random_element = randomized_collection.getRandom()
61

1import java.util.*;
2
3class RandomizedCollection {
4    private Map<Integer, Set<Integer>> valueToIndicesMap;
5    private List<Integer> valuesList;
6    private Random randomGenerator;
7
8    // Constructor to initialize the data structures
9    public RandomizedCollection() {
10        valueToIndicesMap = new HashMap<>();
11        valuesList = new ArrayList<>();
12        randomGenerator = new Random();
13    }
14
15    /**
16     * Inserts a value to the collection. Returns true if the collection did not already 
17     * contain the specified element.
18     *
19     * @param val The value to be inserted.
20     * @return true if the value was not already present in the collection.
21     */
22    public boolean insert(int val) {
23        // Compute if absent: put the value in the map with a new HashSet, if not already present.
24        valueToIndicesMap.computeIfAbsent(val, k -> new HashSet<>()).add(valuesList.size());
25        // Add value to the list
26        valuesList.add(val);
27        // Return true if this was the first occurrence of the val
28        return valueToIndicesMap.get(val).size() == 1;
29    }
30
31    /**
32     * Removes a value from the collection. Returns true if the collection contained the specified element.
33     *
34     * @param val The value to be removed.
35     * @return true if the value was present in the collection.
36     */
37    public boolean remove(int val) {
38        if (!valueToIndicesMap.containsKey(val)) {
39            return false;
40        }
41        // Get indices set for the value
42        Set<Integer> idxSet = valueToIndicesMap.get(val);
43        // Get an iterator’s next value to get a specific index where our value is found
44        int removeIndex = idxSet.iterator().next();
45        // Get the index of the last value in the list
46        int lastValueIndex = valuesList.size() - 1;
47        // Replace the removeIndex's value with the last value in the list in both list and map
48        valuesList.set(removeIndex, valuesList.get(lastValueIndex));
49        idxSet.remove(removeIndex);
50
51        // Get indices set for the last value in the list
52        Set<Integer> lastValueIndices = valueToIndicesMap.get(valuesList.get(lastValueIndex));
53        lastValueIndices.remove(lastValueIndex);
54        if (removeIndex < lastValueIndex) {
55            lastValueIndices.add(removeIndex);
56        }
57        // Remove the entry from the map if no more indices are present for this value
58        if (idxSet.isEmpty()) {
59            valueToIndicesMap.remove(val);
60        }
61        // Remove the last value from the list
62        valuesList.remove(lastValueIndex);
63        return true;
64    }
65
66    /**
67     * Get a random element from the collection.
68     *
69     * @return A random element from the collection.
70     */
71    public int getRandom() {
72        // Get the size of the list
73        int size = valuesList.size();
74        // Return -1 if the list is empty, otherwise return a random element
75        return size == 0 ? -1 : valuesList.get(randomGenerator.nextInt(size));
76    }
77}
78
79/* Example usage:
80RandomizedCollection obj = new RandomizedCollection();
81boolean param_1 = obj.insert(val);
82boolean param_2 = obj.remove(val);
83int param_3 = obj.getRandom();
84*/
85

1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <random>
5
6class RandomizedCollection {
7private:
8    std::unordered_map<int, std::unordered_set<int>> valueToIndicesMap; // Maps values to indices at which they occur.
9    std::vector<int> valuesList; // Stores all values for easy access.
10    std::default_random_engine randomGenerator; // RNG for the getRandom method.
11
12public:
13    // Constructor to initialize the data structures
14    RandomizedCollection() : randomGenerator(std::random_device{}()) {}
15
16    /**
17     * Inserts a value to the collection. Returns true if the collection did not already 
18     * contain the specified element.
19     *
20     * @param val The value to be inserted.
21     * @return true if the value was not already present in the collection.
22     */
23    bool insert(int val) {
24        bool isFirstOccurrence = valueToIndicesMap[val].empty();
25        valueToIndicesMap[val].insert(valuesList.size());
26        valuesList.push_back(val);
27        return isFirstOccurrence;
28    }
29
30    /**
31     * Removes a value from the collection. Returns true if the collection contained the specified element.
32     *
33     * @param val The value to be removed.
34     * @return true if the value was present in the collection.
35     */
36    bool remove(int val) {
37        auto it = valueToIndicesMap.find(val);
38        if (it == valueToIndicesMap.end()) {
39            return false;
40        }
41        auto removeIndex = *(it->second.begin());
42        it->second.erase(removeIndex);
43        int lastValueIndex = valuesList.size() - 1;
44        if (removeIndex < lastValueIndex) {
45            int lastValue = valuesList[lastValueIndex];
46            valuesList[removeIndex] = lastValue;
47            valueToIndicesMap[lastValue].erase(lastValueIndex);
48            valueToIndicesMap[lastValue].insert(removeIndex);
49        }
50        valuesList.pop_back(); // Remove the last element from the vector
51        if (it->second.empty()) {
52            valueToIndicesMap.erase(it); // Remove key from map if no indices are left
53        }
54        return true;
55    }
56
57    /**
58     * Get a random element from the collection.
59     *
60     * @return A random element from the collection.
61     */
62    int getRandom() {
63        if (valuesList.empty()) {
64            return -1;
65        }
66        std::uniform_int_distribution<int> distribution(0, valuesList.size() - 1);
67        return valuesList[distribution(randomGenerator)];
68    }
69};
70
71/* Example usage:
72RandomizedCollection obj;
73bool param_1 = obj.insert(val);
74bool param_2 = obj.remove(val);
75int param_3 = obj.getRandom();
76*/
77

1// Importing necessary functionalities from 'typescript' module
2import { Set } from "typescript-collections";
3
4// Define a mapping between values and their locations (indices in the array)
5const valueToIndicesMap: Map<number, Set<number>> = new Map();
6// Define an array to store the values
7const valuesList: number[] = [];
8// Define a random generator
9const randomGenerator: () => number = Math.random;
10
11/**
12 * Inserts a value to the collection. Returns true if the collection did not already 
13 * contain the specified element.
14 *
15 * @param val The value to be inserted.
16 * @return boolean indicating if the value was not already present in the collection.
17 */
18const insert = (val: number): boolean => {
19    // If set for the given 'val' does not exist in the map, create and add it
20    if (!valueToIndicesMap.has(val)) {
21        valueToIndicesMap.set(val, new Set());
22    }
23  
24    const indicesSet = valueToIndicesMap.get(val);
25    // Add the index to the current 'val' set
26    indicesSet.add(valuesList.length);
27    // Add the 'val' to the list
28    valuesList.push(val);
29    // Return true if this was the first occurrence of 'val'
30    return indicesSet.size === 1;
31}
32
33/**
34 * Removes a value from the collection. Returns true if the collection contained the specified element.
35 *
36 * @param val The value to be removed.
37 * @return boolean indicating if the value was present in the collection.
38 */
39const remove = (val: number): boolean => {
40    if (!valueToIndicesMap.has(val)) {
41        return false;
42    }
43  
44    const indicesSet = valueToIndicesMap.get(val);
45    // Obtain one of the indices of the 'val'
46    const removeIndex = indicesSet.values().next().value;
47
48    const lastValueIndex = valuesList.length - 1;
49    const lastValue = valuesList[lastValueIndex];
50  
51    // If 'val' is not at the last position, swap it with the last element
52    if (removeIndex !== lastValueIndex) {
53        valuesList[removeIndex] = lastValue;
54        const lastValueIndicesSet = valueToIndicesMap.get(lastValue);
55        lastValueIndicesSet.delete(lastValueIndex);
56        lastValueIndicesSet.add(removeIndex);
57    }
58
59    // Remove the 'val' from the list and indices set
60    valuesList.pop();
61    indicesSet.delete(removeIndex);
62
63    // If this was the last occurrence, remove the entry from the map
64    if (indicesSet.size === 0) {
65        valueToIndicesMap.delete(val);
66    }
67  
68    return true;
69}
70
71/**
72 * Get a random element from the collection.
73 *
74 * @return A random element from the collection or -1 if empty.
75 */
76const getRandom = (): number => {
77    const size = valuesList.length;
78    // Generate a random index and return the value at that index
79    return size === 0 ? -1 : valuesList[Math.floor(randomGenerator() * size)];
80}
81
82/* Example usage:
83const insertResult: boolean = insert(val);
84const removeResult: boolean = remove(val);
85const randomValue: number = getRandom();
86*/
87

Time and Space Complexity

Time Complexity

__init__: The constructor simply initializes an empty dictionary and a list, which is an O(1) operation.
insert(val): Inserting a value involves:
- Accessing or creating a set in the dictionary, which is O(1) on average.
- Adding the index to the set, which is O(1).
- Appending the value to the list, which is also O(1). Overall, the insert operation has an average time complexity of O(1).
remove(val): Removing a value involves several steps:
- Checking if the value is in the dictionary, which is O(1) on average.
- Removing an index from the set, which is O(1).
- If necessary, updating a different index in another set, which is O(1).
- Popping the last element from the list, which is O(1). Therefore, the remove operation also has an average time complexity of O(1).
getRandom: Simply returns a random element from the list using random.choice(self.l), which is O(1) as the choice function has a time complexity of O(1) on Python lists.

Note: The average time complexity assumes that the hash function used for the dictionary and sets is providing a good distribution, which allows O(1) operations on average. In the worst-case scenario, where hash collisions are frequent, these operations could degrade to O(n) where n is the number of elements in the collection.

Space Complexity

The overall space complexity of the RandomizedCollection class is O(n), where n is the number of elements in the collection. This is because the collection maintains a dictionary and a list to store all elements, with the dictionary potentially contains a set for each unique element, and the list contains all the elements (including duplicates).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don't know