grid47 Exploring patterns and algorithms
Sep 30, 2024
7 min read
Solution to LeetCode 380: Insert Delete GetRandom O(1) Problem
Design a data structure that supports three operations: insert, remove, and getRandom. The insert operation adds an element to the set if it is not already present. The remove operation removes an element from the set if it exists. The getRandom operation returns a random element from the set, with each element having an equal probability of being selected.
Problem
Approach
Steps
Complexity
Input: The input consists of multiple function calls, starting with the creation of the RandomizedSet object. The operations 'insert(val)', 'remove(val)', and 'getRandom()' are called sequentially.
Goal: Use a combination of a list and a hash map to efficiently perform insertions, removals, and random selections in constant time on average.
Steps:
• Use a list to store elements and a hash map to store their indices for fast access.
• In the insert operation, check if the element already exists. If not, add it to the list and map the value to its index.
• In the remove operation, replace the element to be removed with the last element in the list, update its index in the map, and then pop the last element.
• In the getRandom operation, simply pick a random index from the list.
Goal: Ensure the insert, remove, and getRandom functions work in O(1) time on average.
Steps:
• -2^31 <= val <= 2^31 - 1
• At most 2 * 10^5 calls to insert, remove, and getRandom.
Assumptions:
• The elements are stored uniquely in the set.
• The set will always have at least one element when getRandom() is called.
• Explanation: We track elements in the set, and after each operation, we provide the result for that operation. For example, 'insert(1)' returns true because 1 is inserted, while 'remove(2)' returns false because 2 was not in the set.
• Input: Example 2: [[], [5], [], [10], [5], []]
• Explanation: After each operation, the result is either true, false, or a random element from the set.
Approach: We use a list to store elements and a hash map to store indices, allowing for O(1) average time complexity for all operations.
Observations:
• We need to maintain efficient O(1) time for insert, remove, and getRandom operations.
• A list allows for O(1) time access, while the hash map helps with O(1) element removal and index tracking.
• The key challenge is efficiently handling the removal operation while maintaining the ability to return a random element.
Steps:
• Store elements in a list and their indices in a hash map.
• For insert, check if the element is present. If not, append it to the list and update the map.
• For remove, swap the element with the last element in the list to maintain O(1) time complexity and update the map accordingly.
• For getRandom, pick a random index from the list.
Empty Inputs:
• No empty operations will be allowed as the problem guarantees at least one element when getRandom() is called.
Large Inputs:
• Ensure the solution works efficiently with up to 2 * 10^5 operations.
Special Values:
• Handle edge cases where the value is at the boundary of the allowed range (-2^31 or 2^31 - 1).
Constraints:
• Ensure O(1) time complexity for each of the operations.
This line initializes a vector `a` to store the values inserted into the set.
2 : Variable Initialization
unordered_map<int,int> m;
This line initializes an unordered map `m` to store each value and its corresponding index in the vector `a`.
3 : Constructor
public:
This marks the beginning of the public section where functions are defined.
4 : Constructor Definition
RandomizedSet() {
This is the constructor for the RandomizedSet class, initializing the data structures.
5 : Insert Function
boolinsert(int val) {
This function attempts to insert a value `val` into the set. It returns false if the value already exists, otherwise it inserts the value and returns true.
6 : Conditionals
if(m.find(val)!=m.end())
This checks if the value already exists in the set by looking it up in the unordered map.
7 : Return Statement
returnfalse;
If the value already exists, the function returns `false` to indicate the insertion was unsuccessful.
8 : Insert Action
else{
This marks the beginning of the block of code to execute if the value does not already exist.
9 : Insert Action
a.push_back(val);
The value is pushed onto the vector `a` to store it.
10 : Insert Action
m[val]=a.size()-1;
The value is mapped to its index in the vector `a` in the unordered map `m`.
11 : Return Statement
returntrue;
If the insertion is successful, the function returns `true`.
12 : Remove Function
boolremove(int val) {
This function attempts to remove a value `val` from the set. It returns false if the value does not exist, otherwise it removes the value and returns true.
13 : Conditionals
if(m.find(val)==m.end())
This checks if the value exists in the unordered map `m`. If it doesn't exist, the function will return false.
14 : Return Statement
returnfalse;
If the value does not exist, the function returns `false` to indicate the removal was unsuccessful.
15 : Remove Action
else{
This marks the beginning of the block of code to execute if the value exists.
16 : Remove Action
int last=a.back();
The last value from the vector `a` is stored in the variable `last`.
17 : Remove Action
a[m[val]]=a.back();
The last value is moved to the position of the value being removed in the vector.
18 : Remove Action
a.pop_back();
The last value is removed from the vector `a` after it is moved to the position of the removed value.
19 : Remove Action
m[last]=m[val];
The index of the last value is updated in the unordered map `m`.
20 : Remove Action
m.erase(val);
The value is removed from the unordered map `m`.
21 : Return Statement
returntrue;
If the removal is successful, the function returns `true`.
22 : Get Random Function
intgetRandom() {
This function returns a random value from the set by selecting a random index from the vector `a`.
23 : Get Random Action
return a[rand()%a.size()];
A random index is selected from the vector `a`, and the corresponding value is returned.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: All operations (insert, remove, getRandom) have an average time complexity of O(1) due to the use of a list and a hash map.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) as we need to store the elements in a list and a hash map, where n is the number of elements in the set.
