Problem Description

You need to design a data structure called RandomizedSet that supports inserting values, removing values, and getting a random element from the set - all in average O(1) time complexity.

The RandomizedSet class should support the following operations:

• RandomizedSet(): Creates and initializes an empty RandomizedSet object.

• insert(val): Adds the integer val to the set if it's not already present. Returns true if the value was successfully added (wasn't in the set before), and false if the value was already in the set.

• remove(val): Removes the integer val from the set if it exists. Returns true if the value was successfully removed (was in the set), and false if the value wasn't in the set.

• getRandom(): Returns a random element from the current set. Each element in the set must have equal probability of being selected. This method will only be called when there is at least one element in the set.

The key challenge is implementing all three operations with average O(1) time complexity. The solution uses a combination of a hash table (dictionary) and a dynamic array (list) to achieve this:

• The hash table d maps each value to its index in the array
• The array q stores all the values in the set

For insertion, we append the new value to the end of the array and record its index in the hash table. For removal, we swap the element to be removed with the last element in the array, update the hash table accordingly, then pop the last element. This avoids the O(n) cost of removing from the middle of an array. For getting a random element, we simply pick a random index from the array.

Intuition

To achieve O(1) average time complexity for all operations, we need to think about the strengths and weaknesses of different data structures.

For insert and remove operations, a hash table immediately comes to mind since it provides O(1) average time for checking existence, adding, and deleting elements. However, hash tables don't support getting a random element efficiently - we'd need to iterate through all keys which takes O(n) time.

For getRandom, an array is perfect because we can generate a random index and access that element in O(1) time. But arrays have a problem: removing an element from the middle takes O(n) time due to shifting elements.

The key insight is to combine both data structures and use a clever trick for removal:

1. Use an array q to store all values - this makes getRandom trivial with O(1) access by random index.

2. Use a hash table d to map each value to its index in the array - this allows O(1) checking if a value exists and finding its position.

3. The removal trick: Instead of removing an element from the middle of the array (which would require shifting all subsequent elements), we swap the element to be removed with the last element in the array. Then we can simply pop the last element in O(1) time. We just need to update the hash table to reflect the new index of the swapped element.

This swap-and-pop technique is the crucial optimization that allows us to maintain O(1) removal while using an array. By always removing from the end, we avoid the costly array reorganization, and the hash table ensures we can quickly find any element's position for the swap.

Solution Approach

The solution uses a combination of a hash table and a dynamic list to achieve O(1) average time complexity for all operations.

Data Structures:

• self.d: A hash table (dictionary) that maps each value to its index in the list
• self.q: A dynamic list (array) that stores all the values in the set

Implementation Details:

1. __init__() Method: Initialize an empty dictionary d and an empty list q.

2. insert(val) Method:

• First check if val exists in the hash table d
• If it exists, return False (value already in set)
• Otherwise:
  • Get the current length of list q as the index for the new element
  • Store this index in the hash table: self.d[val] = len(self.q)
  • Append val to the end of list q: self.q.append(val)
  • Return True (successfully inserted)

3. remove(val) Method:

• First check if val exists in the hash table d
• If it doesn't exist, return False (value not in set)
• Otherwise:
  • Get the index i of val from the hash table: i = self.d[val]
  • Move the last element to position i:
    • Update the hash table entry for the last element: self.d[self.q[-1]] = i
    • Replace the element at position i with the last element: self.q[i] = self.q[-1]
  • Remove the last element from the list: self.q.pop()
  • Remove val from the hash table: self.d.pop(val)
  • Return True (successfully removed)

4. getRandom() Method:

• Use Python's choice() function to randomly select an element from list q
• Return the selected element

The key optimization is in the remove operation: instead of removing an element from the middle of the array (which would take O(n) time), we swap it with the last element and then remove from the end (which takes O(1) time). This swap-and-pop technique maintains the O(1) time complexity while keeping all elements accessible for random selection.

Example Walkthrough

Let's walk through a sequence of operations to see how the data structure works:

Initial State:

• d = {} (empty hash table)
• q = [] (empty array)

Operation 1: insert(10)

• Check if 10 exists in d: No
• Get index for new element: len(q) = 0
• Update hash table: d[10] = 0
• Append to array: q = [10]
• Return True
• State: d = {10: 0}, q = [10]

Operation 2: insert(20)

• Check if 20 exists in d: No
• Get index for new element: len(q) = 1
• Update hash table: d[20] = 1
• Append to array: q = [10, 20]
• Return True
• State: d = {10: 0, 20: 1}, q = [10, 20]

Operation 3: insert(30)

• Check if 30 exists in d: No
• Get index for new element: len(q) = 2
• Update hash table: d[30] = 2
• Append to array: q = [10, 20, 30]
• Return True
• State: d = {10: 0, 20: 1, 30: 2}, q = [10, 20, 30]

Operation 4: remove(20) (This demonstrates the swap-and-pop trick)

• Check if 20 exists in d: Yes, at index 1
• Get index of 20: i = d[20] = 1
• Move last element (30) to position 1:
  • Update hash table for last element: d[30] = 1
  • Replace element at index 1: q[1] = 30, so q = [10, 30, 30]
• Pop last element: q = [10, 30]
• Remove 20 from hash table: d.pop(20)
• Return True
• State: d = {10: 0, 30: 1}, q = [10, 30]

Operation 5: getRandom()

• Randomly select from q = [10, 30]
• Each element has 50% chance of being selected
• Let's say it returns 30

Operation 6: insert(20) (Re-inserting a previously removed value)

• Check if 20 exists in d: No
• Get index for new element: len(q) = 2
• Update hash table: d[20] = 2
• Append to array: q = [10, 30, 20]
• Return True
• State: d = {10: 0, 30: 1, 20: 2}, q = [10, 30, 20]

Operation 7: remove(10) (Removing the first element)

• Check if 10 exists in d: Yes, at index 0
• Get index of 10: i = d[10] = 0
• Move last element (20) to position 0:
  • Update hash table for last element: d[20] = 0
  • Replace element at index 0: q[0] = 20, so q = [20, 30, 20]
• Pop last element: q = [20, 30]
• Remove 10 from hash table: d.pop(10)
• Return True
• State: d = {30: 1, 20: 0}, q = [20, 30]

The key insight demonstrated here is how the remove operation maintains O(1) complexity by always swapping with the last element before removing, avoiding the need to shift elements in the array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) for all operations (insert, remove, and getRandom)

• insert(val): Checking if val exists in the dictionary is O(1). Getting the length of the list is O(1). Adding to the dictionary and appending to the list are both O(1) operations.

• remove(val): Checking dictionary membership is O(1). Accessing elements by index in both the dictionary and list is O(1). Swapping the element to be removed with the last element is O(1). The pop() operation on the list (removing the last element) is O(1). Dictionary deletion with pop(val) is also O(1).

• getRandom(): The choice() function from the random module selects a random element from the list in O(1) time.

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

• The dictionary self.d stores n key-value pairs (value to index mappings), requiring O(n) space.
• The list self.q stores n elements, requiring O(n) space.
• Total space complexity is O(n) + O(n) = O(n).

Common Pitfalls

1. Incorrect Index Update During Removal

The most common mistake is forgetting to handle the edge case when removing the last element from the array. When the element to be removed is already the last element, the swap operation would incorrectly update its own index in the hash table.

Problematic Code:

def remove(self, val: int) -> bool:
    if val not in self.val_to_index:
        return False
  
    index_to_remove = self.val_to_index[val]
    last_element = self.values[-1]
  
    # BUG: This fails when removing the last element
    self.values[index_to_remove] = last_element
    self.val_to_index[last_element] = index_to_remove
  
    self.values.pop()
    del self.val_to_index[val]
    return True

Solution: Add a check to handle when the element to remove is the last element:

def remove(self, val: int) -> bool:
    if val not in self.val_to_index:
        return False
  
    index_to_remove = self.val_to_index[val]
    last_element = self.values[-1]
  
    # Only update if we're not removing the last element
    if index_to_remove != len(self.values) - 1:
        self.values[index_to_remove] = last_element
        self.val_to_index[last_element] = index_to_remove
  
    self.values.pop()
    del self.val_to_index[val]
    return True

2. Order of Operations in Remove

Another pitfall is deleting the value from the hash table before updating the last element's index, which causes a KeyError when the element to remove is the last element.

Problematic Code:

def remove(self, val: int) -> bool:
    if val not in self.val_to_index:
        return False
  
    index_to_remove = self.val_to_index[val]
    last_element = self.values[-1]
  
    # BUG: Deleting too early
    del self.val_to_index[val]  
  
    # This fails if val == last_element
    self.values[index_to_remove] = last_element
    self.val_to_index[last_element] = index_to_remove  # KeyError here!
  
    self.values.pop()
    return True

Solution: Always delete from the hash table after all other operations are complete.

3. Using Wrong Random Selection Method

Using random.randint() incorrectly or implementing custom random selection can lead to index out of bounds errors.

Problematic Code:

import random

def getRandom(self) -> int:
    # BUG: randint is inclusive on both ends, could cause IndexError
    index = random.randint(0, len(self.values))
    return self.values[index]

Solution: Use random.choice() which handles the bounds correctly, or use random.randint(0, len(self.values) - 1) with proper bounds.

from random import choice

def getRandom(self) -> int:
    return choice(self.values)