Problem 380

(Last updated: )

Question statement:

Implement the RandomizedSet class. You must implement the functions of the class such that each function works in average O(1) time complexity.

  • 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.

Solution

Main idea:

The first obvious approach had a small subtlety that I wasn’t accounting for: Having a set() track the values in the randomised set, we accomplish adding and removing in O(1) time since all look ups are O(1). However, we run into a roadblock with the getRandom() function, where we would have to convert the set into a list, and then use the random.choice() function from the random library. While random.choice() runs in O(1) time, turning a set to a list runs in O(n) time, and so we break the rules of the prompt. It is noteworthy however that leetcode did accept this solution, and it passed the test cases reasonably well.

So my non-cheating approach was inspired out of some hints in the discussion tab. The only issue we faced previously was the conversion from set to a list. So instead, we start with a list from the get-go, and this solves the getRandom() problem. But now, membership checking in a list is an O(n) operation. To overcome this hurdle, we take advantage of the fact that the list only contains unique elements. In particular, we maintain a second feature of this class, namely a dictionary that maps each value to it’s index in the list of values. Now, membership checking can be done with the dictionary, which is an O(1) lookup. Whenever we want to add val into our list, we do that and also build our dictionary by assigning val it’s index = len(list) -1.

When removing a value val from the list, we take dicionary[val] which stores index of val, then let list[val] = list[-1]. So val is no longer in the list, then we pop the last element from the list, and delete val from our dictionary.

Code for approach 1 (cheating approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class RandomizedSet:
    def __init__(self):
        self.randomset = set()

    def insert(self, val: int) -> bool:
        if(val in self.randomset):
            return False
        else:
            self.randomset.add(val)
            return True

    def remove(self, val: int) -> bool:
        if(val in self.randomset):
            self.randomset.remove(val)        
        else:
            return False

    def getRandom(self) -> int:
        return random.choice(list(self.randomset))

Code for approach 2 (non-cheating approach):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class RandomizedSet:
    def __init__(self):
        self.randomset = []
        self.value_to_index = {}

    def insert(self, val: int) -> bool:
        if(val in self.value_to_index):
            return False
        else:
            self.randomset.append(val)
            self.value_to_index[val] = len(self.randomset)-1
            return True

    def remove(self, val: int) -> bool:
        if(val in self.value_to_index):
            index = self.value_to_index[val]
            self.randomset[index] = self.randomset[-1]
            self.value_to_index[self.randomset[-1]] = index
            self.randomset.pop(-1)
            del self.value_to_index[val]
            return True
        else:
            return False

    def getRandom(self) -> int:
        return random.choice(self.randomset)

Comments:

Time complexity for approach 1: O(1) for insert() and remove(), O(n) for getRandom()

Time complexity for approach 2: O(1) for all functions.

At the time of submission, approach 1 passes leetcode submission cases in 446ms, beating 36.59% of users. It uses 64.49MB of memory, beating 34.05% of users; while approach 2 passes leetcode submission cases in 235ms, beating 99.48% of users. It uses 64.70MB of memory, beating 20.46% of users