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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Insert Delete GetRandom O(1) - Duplicates allowed

Number: 381

Difficulty: Hard

Paid? No

Companies: LinkedIn, Amazon, Affirm, Bloomberg, Meta, Google, TikTok, Peloton, DE Shaw, Yelp

Problem Description

Implement a data structure that supports inserting elements (including duplicates), removing a single occurrence of an element, and getting a random element. Each operation should work on average in O(1) time, and the probability of returning an element should be linearly proportional to its frequency in the structure.

Key Insights

  • Maintain an array (or list) to store the elements to allow for O(1) random access.
  • Use a hash table that maps each value to a set (or list) of indices where the value is stored in the array.
  • When removing an element, swap it with the last element in the array and update the hash map accordingly to maintain O(1) deletion.
  • Handle duplicates by managing a collection of indices for each value.

Space and Time Complexity

Time Complexity: O(1) average for insert, remove, and getRandom.
Space Complexity: O(n) where n is the number of elements stored.

Solution

We use a dynamic array to store the numbers, which allows us to efficiently pick a random element using a random index. To support O(1) removals even for duplicates, we use a hash table where each key is a number and the value is a set (or similar container) of indices in the array where that number appears.
For insertion, we add the new value at the end of the array and record its index in the hash table.
For removal, we locate any index from the hash table corresponding to the value, swap the element at that index with the last element in the array, update indices in the hash table for the swapped element, and finally remove the last element from the array.
The getRandom operation simply picks a random index from the array and returns the element.

Code Solutions

import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        # Dynamic array to store values.
        self.nums = []
        # Hash table mapping value to a set of indices in self.nums.
        self.idx_map = defaultdict(set)
    
    def insert(self, val: int) -> bool:
        # Check if value does not exist already.
        is_new = len(self.idx_map[val]) == 0
        # Append the value to the list.
        self.nums.append(val)
        # Add the index to the set for this value.
        self.idx_map[val].add(len(self.nums) - 1)
        return is_new

    def remove(self, val: int) -> bool:
        # Only remove if val exists.
        if not self.idx_map[val]:
            return False
        # Get an arbitrary index of the element to remove.
        remove_idx = self.idx_map[val].pop()
        # Move the last element in the list to the remove index.
        last_val = self.nums[-1]
        last_idx = len(self.nums) - 1
        self.nums[remove_idx] = last_val
        # Update the indices for the last value if not removing itself.
        self.idx_map[last_val].add(remove_idx)
        self.idx_map[last_val].discard(last_idx)
        # Remove the last element.
        self.nums.pop()
        return True

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