Category: Hashmaps

Today, we will be discussing one of my favorite problems because it’s open ended and design oriented. We have to design a data structure that can perform insert, delete and get random operations with an average of O(1) time complexity.

• insert(val): Inserts an item val to the set if not already present.
• remove(val): Removes an item val from the set if present.
• getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Let’s take a look at our toolbox to see what data structures we can use in solving this problem. The table below lists the average time complexity for some of the operations.

The above table shows that most of the data structures except arrays have an average time complexity of O(1) to perform insert and delete operations but remember that inserting and deleting from the end of an array is still O(1). The catch here is to get the getRandom function perform at O(1) time. We cannot get a random index from Hashmaps and accessing indexes takes O(N) time with other data structures except for arrays. In this case, we can leverage the benefits of hashmaps and arrays by doing the following.

Insertion O(1)

• Insert an element at the end of an array
• Store the insertion indexes of elements in a hashmap

Remove O(1)

• Find the index of the element to be removed, from the hashmap
• Copy the last element of the array into this index
• Pop the last element of the array O(1)
• Delete the entry for this element from the hashmap

Get Random O(1)

• Use a random function to get an index between 0 and len(array) – 1
• Return the element at that index from the array

Time Complexity: All operations happen in O(1)

Space Complexity: O(N) for the array and O(N) for the hashmap, so the overall space complexity is O(N)

Code:

class RandomizedSet:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.mapping = {}
        
    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val not in self.mapping:
            # Insert the element at the end of nums
            self.nums.append(val)
            index = len(self.nums) - 1
            self.mapping[val] = index
            return True
        return False
    
        
    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val not in self.mapping:
            return False
        
        removeIndex = self.mapping[val]
        lastValue = self.nums[-1]
        # store the last element in the removed val index
        self.nums[removeIndex] = lastValue
        # Update the index value of last element
        self.mapping[lastValue] = removeIndex
        # clean up
        self.nums.pop()
        del self.mapping[val]
        return True
        
    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        randIndex = random.randint(0, len(self.nums) - 1)
        
        return self.nums[randIndex]
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

Hope you enjoyed learning how to design a data structure that can perform insert, delete and get random operations in O(1) time. Have a great day!