380. Insert Delete GetRandom O(1)

Leetcode #: 380
Name: Insert Delete GetRandom O(1)
Difficulty: Medium
Url: https://leetcode.com/problems/insert-delete-getrandom-o1/

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

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

Approach

For this problem, it would be instinctive to initially think to use a Hash Set as the problem statement repeatedly mentions in order to satisfy the constraint of implementing each of the class methods such that each function works in average O(1) time complexity. This is because the operations of search, insert, and delete for a Hash Set takes expected O(1) time. Thus, if we were asked to implement only the first 2 methods of insert & remove, we can sufficiently satisfy the constraint by implementing a Hash Set but unfortunately this is not the case.

The getRandom method serves as the challenge of this problem as we aren’t able to index into a Hash Set like how we can conveniently do for a dynamic array. We’re only able to generate a random element from a set of values by using an ordered data structure (i.e. a Dynamic Array), not an unordered data structure (i.e. a Hash Set)

For our ordered data structure, we can utilize a dynamic array so at a high level, we’ll want to be maintaining both an unordered and ordered data structure simultaneously for this problem. Now an issue arises where what if an element we select within the Hash Set in which we want to remove happens to be located in the middle of our dynamic array? Removing an element from the middle of our dynamic array will take O(n) time, not O(1) time.

insert and remove

We can ultimately solve this issue by using a Hash Map — we can create k:v pairs where the key would be the element that we want to insert and its corresponding value as its index located within our dynamic array. Doing this allows us to keep track of where that element we want to remove exists in terms of its specific index or position within our ordered data structure or dynamic array. We know that popping from a dynamic array can be generalized as an O(1) operation so we can first locate the element we want to remove within our dynamic array and overwrite it with the last element of the dynamic array. Then, we’ll need to update our Hash Map as well by overwriting the k:v pair where the key is the last element in the dynamic array and its corresponding value was its initial position or index in the dynamic array but now we’re going to overwrite this value of the k:v pair with the index or position of the element that we want to remove within the dynamic array because that’s ultimately where we want to migrate the last element of the array to in terms of its position. Finally, we’ll want to delete the k:v pair with the key as the element that we want to remove from our Hash Map as it shouldn’t exist in the Hash Map anymore.

getRandom

Thus, for our getRandom method, we can simply use our random module and use the choice method from the module which accepts a list. We’ll pass it our dynamic array and it’ll generate a random element of equal probability (roughly).

Code

Python | Time: O(1) | Space: O(n)

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub