We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Insert Delete GetRandom O(1) - Duplicates allowed

Difficulty: Hard

Problem Description

RandomizedCollection is a data structure that contains a collection of numbers, possibly duplicates (i.e., a multiset). It should support inserting and removing specific elements and also reporting a random element.

Implement the RandomizedCollection class:

  • RandomizedCollection() Initializes the empty RandomizedCollection object.
  • bool insert(int val) Inserts an item val into the multiset, even if the item is already present. Returns true if the item is not present, false otherwise.
  • bool remove(int val) Removes an item val from the multiset if present. Returns true if the item is present, false otherwise. Note that if val has multiple occurrences in the multiset, we only remove one of them.
  • int getRandom() Returns a random element from the current multiset of elements. The probability of each element being returned is linearly related to the number of the same values the multiset contains.

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

Key Insights

  • To handle duplicates, we need a way to efficiently keep track of the count of each element.
  • We can use a list to store the values for random access and a dictionary to map each value to its indices in the list.
  • The getRandom function will randomly select an index from the list, ensuring the probability of selecting an element is proportional to its occurrences.

Space and Time Complexity

Time Complexity: O(1) for insert, remove, and getRandom operations on average.
Space Complexity: O(n) where n is the number of elements in the collection, for storing the list and the index mapping.

Solution

To achieve the desired functionality, we use:

  • A list to store the elements, which allows for O(1) access to any element.
  • A dictionary (hash map) to track the indices of each element within the list. Each key in the dictionary maps to a set of indices where the value appears in the list.
  • For insertion, we append the value to the list and update the dictionary.
  • For removal, we find an index in the dictionary, swap it with the last element in the list to maintain order, and then remove the last element. We also update the dictionary accordingly.
  • The getRandom function simply selects a random index from the list.

Code Solutions

import random
from collections import defaultdict

class RandomizedCollection:

    def __init__(self):
        self.list = []
        self.index_map = defaultdict(set)

    def insert(self, val: int) -> bool:
        self.list.append(val)
        self.index_map[val].add(len(self.list) - 1)
        return len(self.index_map[val]) == 1

    def remove(self, val: int) -> bool:
        if val not in self.index_map or not self.index_map[val]:
            return False

        # Get an arbitrary index of the element to remove
        remove_index = self.index_map[val].pop()
        last_element = self.list[-1]

        # Move the last element to the place of the element to remove
        self.list[remove_index] = last_element
        if self.index_map[last_element]:
            self.index_map[last_element].remove(len(self.list) - 1)
            self.index_map[last_element].add(remove_index)

        self.list.pop()
        if not self.index_map[val]:
            del self.index_map[val]

        return True

    def getRandom(self) -> int:
        return random.choice(self.list)
← Back to All Questions