381. Insert Delete GetRandom O(1) - Duplicates allowed
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, andfalse
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, andfalse
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 theRandomizedCollection
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 ofval
(by checking if the length of the index set is 1) orFalse
otherwise.
- The method first retrieves or initializes the set of indices for
-
remove(self, val: int) -> bool
: When removing a value:- The method checks if
val
is in the dictionary; if not, it returnsFalse
. - 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 removingval
. - If the index set is empty (no more occurrences of
val
), removeval
from the dictionary. - Return
True
since the element was successfully removed.
- The method checks if
-
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, andrandom.choice
has anO(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 method simply uses Python's
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 EvaluatorExample 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 anO(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, theinsert
operation has an average time complexity ofO(1)
.
- Accessing or creating a set in the dictionary, which is
-
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, theremove
operation also has an average time complexity ofO(1)
.
- Checking if the value is in the dictionary, which is
-
getRandom
: Simply returns a random element from the list usingrandom.choice(self.l)
, which isO(1)
as the choice function has a time complexity ofO(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 isO(n)
, wheren
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.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!