Intuition

First thought was to use a dictionary(hashmap) to keep track of the items, however the random is an issue, since we need to convert the dictionary into a list to get a random item.

Approach

In order to achieve time complexity near O(1) we need to use two structures. One dictionary for fast deletion, and a list for fast randomization.

The trick that makes the possible is to remove an element from a list in O(1), and this is achieved by u

Complexity

  • Time complexity: O(1)

  • Space complexity: O(n*2)

Code

class RandomizedSet(object):

    def __init__(self):
        self.dict = {}
        self.list = []

    def insert(self, val):
        """
        :type val: int
        :rtype: bool
        """

        if val in self.dict:
            return False
        
        self.dict[val] = len(self.list)
        self.list.append(val)

        return True

    def remove(self, val):
        """
        :type val: int
        :rtype: bool
        """
        if val not in self.dict:
            return False
        
        elem_idx = self.dict[val]

        last_elem = self.list[len(self.list)-1]
        self.dict[last_elem] = elem_idx
        self.list[elem_idx] = last_elem

        self.list.pop()
        del self.dict[val]
        return True

    def getRandom(self):
        """
        :rtype: int
        """
        return random.choice(self.list)