LeetCode Solutions Blog

Insert Delete GetRandom O(1)

Number: 380

Difficulty: Medium

Paid? No

Problem Description

Design a data structure that supports all the following operations in average O(1) time, including insert, remove, and getRandom. getRandom should return a random element from the current set of elements, with each element having the same probability of being returned.

Key Insights

Use a dynamic array (or list) to store the elements to allow O(1) access by index.
Use a hash table (or dictionary/map) to store the mapping from value to its index in the array.
For removal, swap the element to be removed with the last element in the array, then delete the last element. This avoids expensive shifting of elements.
getRandom can be implemented by generating a random index into the array.

Space and Time Complexity

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

Solution

The solution involves maintaining a list to store the values and a hash map to quickly check for the presence of a value and to know its index in the list. When an element is removed, swap it with the last element of the list and update the map accordingly; then, remove the last element in O(1) time. This approach ensures that insert, remove, and getRandom can all be achieved in constant time on average.

Code Solutions

import random

class RandomizedSet:
    def __init__(self):
        # List to store the values
        self.values = []
        # Dictionary to map a value to its index in the list
        self.val_to_index = {}
    
    def insert(self, val: int) -> bool:
        # If the value is already present, do not insert.
        if val in self.val_to_index:
            return False
        # Append the value and store its index.
        self.val_to_index[val] = len(self.values)
        self.values.append(val)
        return True
    
    def remove(self, val: int) -> bool:
        # If the value is not present, return False.
        if val not in self.val_to_index:
            return False
        # Index of element to remove.
        index = self.val_to_index[val]
        # Get the last element.
        last_element = self.values[-1]
        # Place the last element at the index of the element to remove.
        self.values[index] = last_element
        self.val_to_index[last_element] = index
        # Remove the last element from the list.
        self.values.pop()
        # Delete the mapping for the removed element.
        del self.val_to_index[val]
        return True

    def getRandom(self) -> int:
        # Return a random element from the list.
        return random.choice(self.values)