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:
-2^31 <= val <= 2^31 - 12 * 10^5 calls will be made to insert, remove, and getRandom.getRandom is called.
The problem description was taken from https://leetcode.com/problems/insert-delete-getrandom-o1/.
from random import choice
class RandomizedSet: def __init__(self):
self.items = {}
self.indices = []
def insert(self, val: int) -> bool:
if val in self.items:
return False
self.indices.append(val)
self.items[val] = len(self.indices) - 1
return True
def remove(self, val: int) -> bool:
if val not in self.items:
return False
curr_index = self.items[val]
last_index = len(self.indices) - 1
last_item = self.indices[last_index]
self.indices[curr_index] = last_item
self.items[last_item] = curr_index
self.indices.pop()
del self.items[val]
return True
def getRandom(self) -> int:
return random.choice(self.indices)If we were given a problem that only required us to insert or delete in constant time, that would be simple enough because we could just use a HashMap or HashSet.
However, if we were wanting to return a random item then we would have to generate a random number to retrieve an item from the HashMap. That would, however, require us to hash the items based on indices instead of values so the lookup time would drop to linear because we would have to traverse all of the values to find the one we want. If we wanted to convert the HashMap to a list, that would also require linear time.
What we could do instead is place the items in the HashMap and also in a list, so that we can look them up in constant time through the HashMap and also have them available for a random retrieval within the list. However, that gives us a problem with deletions.
Removing an item from a list could take linear time because each other index after it has to shift unless that item was at the end of the list.
Here's how we can solve this. We will create a HashMap for our items. Each key will be an item and each value will be an item's index within an array we will create. When we remove an item, we will look at the index of the item we are wanting to delete, overwrite the index with the item at the last index of the list, pop the last item from the end and delete the removed item from the HashMap.
Everything else will be straightforward.
Let's start by importing the random library.
We could either import the choice function or random integer. The choice function will allow us to grab a random element and the random integer function would allow us to grab a random index, both are valid.
from random import choice
Next, we will initialize our items dictionary and indices array.
def __init__(self):
self.items = {}
self.indices = []
Afterward, we will create our insert function.
def insert(self, val: int) -> bool:
If the value that we're wanting to insert is already in the dictionary, we will return false as the problem description states.
if val in self.items:
return False
Otherwise, we will append it to the list, place it in the dictionary, and reference the item's index within the list by taking the length of the list and subtracting one since arrays begin at index zero.
self.indices.append(val)
self.items[val] = len(self.indices) - 1
Many don't know this, but the len() function is constant time because it is calling an attribute and isn't doing a calculation. People will mistake this and compare this to the sum() function.
Once we have inserted the item, we will return true.
return True
Next up is the remove function, this is the challenge of this problem.
def remove(self, val: int) -> bool:
If the value isn't in our dictionary, we will return false as the problem states.
if val not in self.items:
return False
Otherwise, we will get the current index of the item we are wanting to delete, get the last index of the list, and then the last item from that index.
curr_index = self.items[val]
last_index = len(self.indices) - 1
last_item = self.indices[last_index]
We will then overwrite the removal item's index with the last item, update the last item's index within our dictionary and then pop the last item's duplicate from the end of the list.
self.indices[curr_index] = last_item
self.items[last_item] = curr_index
self.indices.pop()
Once we have done that, we will delete the item from our dictionary and return true.
del self.items[val]
return True
Lastly, we have our get random function.
def getRandom(self) -> int:
Here, we will just need to return a random item from our indices list.
return random.choice(self.indices)