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)

Difficulty: Medium

Problem Description

Implement the RandomizedSet class with methods to insert, remove, and get a random element, all in average O(1) time complexity.

Key Insights

  • The structure allows for dynamic insertion and deletion of elements.
  • Random access is required for the getRandom method to ensure uniform probability.
  • Efficiently managing the elements requires a combination of a hash table and a dynamic array.

Space and Time Complexity

Time Complexity:

  • insert: O(1)
  • remove: O(1)
  • getRandom: O(1)

Space Complexity: O(n), where n is the number of elements in the set.

Solution

To solve the problem, we use a hash table (dictionary in Python, map in Java) to store the elements and their indices for quick access and a dynamic array (list in Python, array in Java) to maintain the elements for random access.

  1. Insertion: Check if the element exists using the hash table. If it doesn't, add it to the dynamic array and store its index in the hash table.
  2. Removal: Check if the element exists. If it does, remove it from the dynamic array and update the hash table accordingly to maintain the correct indices.
  3. Get Random: Simply select a random index from the dynamic array, ensuring uniform probability.

Code Solutions

import random

class RandomizedSet:
    def __init__(self):
        self.data = []
        self.index_map = {}

    def insert(self, val: int) -> bool:
        if val in self.index_map:
            return False
        self.index_map[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_map:
            return False
        index = self.index_map[val]
        last_element = self.data[-1]
        
        # Move the last element to the place of the element to be removed
        self.data[index] = last_element
        self.index_map[last_element] = index
        
        # Remove last element from the list
        self.data.pop()
        del self.index_map[val]
        return True

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