Insert Delete Getrandom O1 Duplicates Allowed - Leetcode Solution

Problem Statement: Design a data structure that supports all following operations in average O(1) time. Note: Duplicate elements are allowed.

insert(val): Inserts an item val to the collection. remove(val): Removes an item val from the collection if present. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection. RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3. collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2]. collection.remove(1);

// getRandom should return 1 and 2 both equally likely. collection.getRandom();

Approach to Solve:

We can use a map and an array to implement it. The array will store the actual elements, and the map will store the indices of the elements in the array.

insert(val): To insert an element val in the array, we first check if it is already present in the map. If it is present, we simply insert the val into the array and update its index in the map. If it is not present, we insert the element and its index inside the map and push the index of the element in the array. Here we are storing the indices in a list to handle duplicates.

remove(val): To remove an element val from the array, we first check if it is present in the map. If it is not present, we return false as we cannot remove an element that is not present in the array. If it is present, we get the last element from the array and copy it to the position of the element to be removed. Then we update its index in the map to be the position from which the element was copied. We remove the removed element's index from its list and update the index of the last element.

getRandom: To get a random element from the array, we generate a random number between 0 and the size of the array and return the element at that index.

Code:

Here is the python 3 code to implement the solution.

class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.index = {}
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        if val in self.index:
            self.nums.append(val)
            self.index[val].append(len(self.nums)-1)
            return False
        else:
            self.index[val] = [len(self.nums)]
            self.nums.append(val)
            return True
        

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        
        """
        if val in self.index:
            i = self.index[val].pop()
            if not self.index[val]:
                del self.index[val]
            if i != len(self.nums)-1:
                self.nums[i] = self.nums[-1]
                self.index[self.nums[-1]].remove(len(self.nums)-1)
                self.index[self.nums[-1]].append(i)
            self.nums.pop()
            return True
        else:
            return False
        

    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        
        """
        return self.nums[random.randint(0,len(self.nums)-1)]

Complexity Analysis:

Time Complexity:

The insert, remove, and getRandom operations take O(1) average time complexity.

Space Complexity:

The space complexity of the algorithm is O(N), where N is the number of elements in the data structure.

1