NUHMAN.com

📘 Problem Statement

Design a data structure that supports the following operations:

• insert(val): Inserts an item val to the data structure if not already present.
• remove(val): Removes an item val from the data structure if present.
• getRandom(): Returns a random element from the current set of elements.

All operations should be done in O(1) average time complexity.

Example:

python

obj = RandomizedSet()
obj.insert(1)  # Returns true as 1 was inserted successfully.
obj.remove(2)  # Returns false as 2 does not exist.
obj.insert(2)  # Returns true as 2 was inserted successfully.
obj.getRandom() # Returns either 1 or 2 randomly.

🧠 Key Insight

To achieve O(1) time complexity for the three operations, we need to design a solution that allows us to:

1. Insert a new element in constant time.
2. Remove an element in constant time.
3. Get a random element in constant time.

To accomplish this, we use a combination of a HashMap (dictionary in Python) and a List.

Key Components:

• HashMap: The key-value pairs in the map will store the element as the key and its index in the list as the value.
• List: The list will store the elements, which allows us to access any element by its index. To remove an element, we can swap it with the last element and then pop the last element to achieve O(1) deletion.

💡 Approach

1. Insert Operation:

• If the element does not exist, insert it into the dictionary with its index in the list and append it to the list.

1. Remove Operation:

• If the element exists, swap it with the last element in the list, pop the last element, and update the dictionary to reflect the new index.

1. GetRandom Operation:

• Use the random.choice function on the list to return a random element in constant time.

🐍 Python Code

python

import random

class RandomizedSet:

    def __init__(self):
        self.val_to_index = {}  # Dictionary to store element and its index in the list
        self.values = []        # List to store elements
    
    def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        self.val_to_index[val] = len(self.values)
        self.values.append(val)
        return True
    
    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        # Swap the element with the last element
        index = self.val_to_index[val]
        last_element = self.values[-1]
        self.values[index] = last_element
        self.val_to_index[last_element] = index
        # Remove the last element
        self.values.pop()
        del self.val_to_index[val]
        return True
    
    def getRandom(self) -> int:
        return random.choice(self.values)

🔍 Step-by-Step Explanation

1. Insert Operation

python

if val in self.val_to_index:
    return False
self.val_to_index[val] = len(self.values)
self.values.append(val)
return True

• Check if Element Exists: First, check if the element val is already in the dictionary val_to_index. If it exists, return False since duplicates are not allowed.
• Add Element: If the element does not exist, add it to the dictionary with its index in the list (the index is len(self.values)).
• Append to List: Append the element to the list values and return True.

2. Remove Operation

python

if val not in self.val_to_index:
    return False
# Swap the element with the last element
index = self.val_to_index[val]
last_element = self.values[-1]
self.values[index] = last_element
self.val_to_index[last_element] = index
# Remove the last element
self.values.pop()
del self.val_to_index[val]
return True

• Check if Element Exists: First, check if the element val exists in the dictionary val_to_index. If not, return False.
• Swap with Last Element: If the element exists, get its index from the dictionary. Then, swap it with the last element in the list.
• Update Dictionary: Update the dictionary with the new index of the last element after the swap.
• Pop Last Element: After the swap, remove the last element from the list using pop().
• Delete from Dictionary: Remove the element from the dictionary.

3. GetRandom Operation

python

return random.choice(self.values)

• Random Selection: Use the random.choice() function to randomly pick an element from the list values, which gives us a random element in constant time O(1).

💡 Example Walkthrough

python

Input:
randomized_set = RandomizedSet()
randomized_set.insert(1)  # Returns True
randomized_set.insert(2)  # Returns True
randomized_set.getRandom() # Returns either 1 or 2 randomly
randomized_set.remove(1)  # Returns True
randomized_set.getRandom() # Returns 2

• After insert(1) and insert(2), the list values will contain [1, 2], and the dictionary val_to_index will contain {1: 0, 2: 1}.
• Calling getRandom() will return either 1 or 2 randomly.
• After remove(1), the list will contain [2] (1 is swapped with 2 and removed), and the dictionary will contain {2: 0}.
• Calling getRandom() will now return 2.

⏱️ Time & Space Complexity

MetricComplexityInsertO(1)RemoveO(1)GetRandomO(1)Space ComplexityO(n)

• Insert: Inserting an element requires checking if it exists (O(1)) and appending it to the list (O(1)). Therefore, the time complexity is O(1).
• Remove: Removing an element involves swapping it with the last element and popping it from the list (all O(1) operations). Thus, the time complexity is O(1).
• GetRandom: Accessing a random element using random.choice() is a constant-time operation, so the time complexity is O(1).
• Space Complexity: We store the elements in a list and a dictionary, so the space complexity is proportional to the number of elements in the set, i.e., O(n).

🧵 Final Thoughts

LeetCode 380 provides an excellent example of using a combination of HashMap and List to perform three critical operations in constant time. By leveraging the list's ability to access elements by index and the dictionary's fast look-up times, we achieve efficient O(1) operations for insert, remove, and getRandom.

This solution is optimal for problems that require constant-time operations for dynamic sets, and it showcases how combining data structures can lead to elegant and efficient algorithms.