leetcode-study

380. Insert Delete GetRandom O(1)

import random

class RandomizedSet:
    def __init__(self):
        """
        Initialize the RandomizedSet object.
        
        Data Structures:
        - self.nums: A list to store the elements for O(1) random access.
        - self.indices: A dictionary mapping each element to its index in 'nums' for O(1) lookup.
        """
        self.nums = []         # List to store elements.
        self.indices = {}      # Dictionary for element-to-index mapping.
    
    def insert(self, val: int) -> bool:
        """
        Inserts an item 'val' into the set if not present.
        
        Parameters:
            val (int): The integer value to insert.
            
        Returns:
            bool: True if the element was inserted, False if it was already present.
        """
        # Check if the value is already in the set.
        if val in self.indices:
            return False  # Value already exists; do not insert.
        
        # Insert the element by appending to the list and recording its index.
        self.indices[val] = len(self.nums)  # Map the value to its index in the list.
        self.nums.append(val)               # Append the value to the list.
        return True

    def remove(self, val: int) -> bool:
        """
        Removes an item 'val' from the set if present.
        
        Parameters:
            val (int): The integer value to remove.
            
        Returns:
            bool: True if the element was removed, False if it was not present.
        """
        # Check if the value exists in the set.
        if val not in self.indices:
            return False  # Value does not exist; nothing to remove.
        
        # Get the index of the element to remove.
        index_to_remove = self.indices[val]
        # Get the last element in the list.
        last_element = self.nums[-1]
        
        # Move the last element into the position of the element to remove.
        self.nums[index_to_remove] = last_element
        self.indices[last_element] = index_to_remove
        
        # Remove the last element from the list.
        self.nums.pop()
        # Delete the element from the dictionary.
        del self.indices[val]
        
        return True

    def getRandom(self) -> int:
        """
        Returns a random element from the current set of elements.
        
        Returns:
            int: A random element from the set with equal probability.
        """
        # Use random.choice to select a random element from the list.
        return random.choice(self.nums)

Summary of Techniques and Approaches:

• Two Data Structures for O(1) Operations:
  The solution leverages a list for fast random access and a dictionary for quick lookup, insertion, and deletion. This combination ensures that all operations (insert, remove, getRandom) are performed in average O(1) time.

• Efficient Element Removal:
  To remove an element in O(1) time from the list, the algorithm swaps the element to remove with the last element, then pops the list’s last element. This avoids shifting elements and maintains constant time complexity.

• Maintaining Consistency Between Data Structures:
  It’s crucial to update both the list and the dictionary simultaneously during insertions and removals to ensure data integrity, an approach that can be applied in many problems requiring synchronized data structures.

• General Problem-Solving Tips:

  • When constant time operations are required, consider combining data structures that complement each other (e.g., arrays with hash maps).
  • For in-place modifications where order is not important, swapping and popping can be efficient alternatives to expensive operations like shifting elements.
  • Always ensure that operations remain synchronized across multiple data structures to maintain consistency.

These techniques are broadly applicable to similar problems that require balancing quick access, dynamic modification, and randomized operations.