Problem Description

The RandomizedSet class is designed to perform operations on a collection of unique elements. It allows for the insertion and removal of elements and getting a random element from the set. The class methods which are required to be implemented are as follows:

• insert(val): Adds the val to the set if it's not already present, and returns true; if val is already in the set, it returns false.
• remove(val): Removes the val from the set if it's present and returns true; if val is not present in the set, it returns false.
• getRandom(): Returns a random element from the set, ensuring each element has an equal probability of being selected.

The constraint given is that each function should operate in average constant time, i.e., O(1) time complexity.

Intuition

The challenge lies in achieving O(1) time complexity for each operation - insert, remove, and getRandom. A standard set data structure wouldn’t suffice for getRandom() to be O(1). For efficient random access, we need to use a list structure where random access is O(1). However, a list alone does not provide O(1) time complexity for insert and remove operations due to potential shifting of elements. To navigate this, we use a combination of a hash table (dictionary in Python) and a dynamic array (list in Python).

For insertion, a dynamic array (list) supports adding an element in O(1) time. To handle duplicates, we accompany the list with a hash table that stores elements as keys and their respective indices in the list as values. This simultaneously checks for duplicates and maintains the list of elements.

For removals, a list doesn't remove an element in O(1) time because it might have to shift elements. To circumvent this, we swap the element to be removed with the last element and then pop the last element from the list. This way, the removal doesn't require shifting all subsequent elements. After swapping and before popping, we must update the hash table accordingly to reflect the new index of the element that was swapped.

Getting a random element efficiently is accomplished with a list since we can access elements by an index in O(1) time. Since all elements in the set have an equal probability of being picked, we can select a random index and return the element at that index from the list.

Overall, the use of both data structures allows us to maintain the average constant time complexity constraint required by the problem for all operations, giving us an efficient solution that meets the problem requirements.

Learn more about Math patterns.

Solution Approach

The solution approach utilizes a blend of data structures and careful bookkeeping to ensure that each operation—insert, remove, and getRandom—executes in average constant O(1) time complexity.

Algorithms and Data Structures:

• Hash Table/Dictionary (self.d): This hash table keeps track of the values as keys and their corresponding indices in the dynamic array as values. The hash table enables O(1) access time for checking if a value is already in the set and for removing values by looking up their index.
• Dynamic Array/List (self.q): The dynamic array stores the elements of the set and allows us to utilize the O(1) access time to get a random element.

insert Implementation:

• Check if val is already in the self.d hash table. If it is, return false because no duplicate values are allowed in the set.
• If val is not present, add val as a key to self.d with the value being the current size of the list self.q (which will be the index of the inserted value).
• Then, append val to the list self.q.
• Return true because a new value has been successfully inserted into the set.

remove Implementation:

• Check if val is present in the self.d hash table. If not, return false because there's nothing to remove.
• If val is present, locate its index i in self.q using self.d[val].
• Swap the value val in self.q with the last element in self.q to move val to the end of the list for O(1) removal.
• The hash table self.d needs to be updated to reflect the new index for the value that was swapped to the position previously held by val.
• Pop the last element from self.q, which is now val.
• Remove val from the hash table self.d.
• Return true because the value has been successfully removed from the set.

getRandom Implementation:

• Use Python's choice function from the random module to select a random element from the list self.q. The choice function inherently operates in O(1) time complexity because it selects an index randomly and returns the element at that index from the list.

This approach essentially provides an efficient and elegant solution to conduct insert, remove, and getRandom operations on a set with constant average time complexity, fulfilling the problem's constraints using the combination of a hash table with a dynamic array.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

1. Initialize:

   • We start by initializing our RandomizedSet. Both the dynamic array self.q and the hash table self.d are empty.

2. Insert 5:

   • Call insert(5). Since 5 is not in self.d, we add it with its index to self.d (i.e., self.d[5] = 0) and append it to self.q (i.e., self.q = [5]).
   • The operation returns true.

3. Insert 10:

   • Call insert(10). Similarly, since 10 is not in self.d, we add it with the next index to self.d (i.e., self.d[10] = 1) and append it to self.q (i.e., self.q = [5, 10]).
   • The operation returns true.

4. Insert 5 again:

   • Call insert(5). Since 5 is already in self.d, we do not add it to self.q and return false.

5. Get a random element:

   • Call getRandom(). The function could return either 5 or 10, each with a 50% probability.

6. Remove 5:

   • Call remove(5). We find the index of 5 from self.d, which is 0. We then swap self.q[0] (5) with the last element in self.q (which is 10), resulting in self.q = [10, 5].
   • We update self.d to reflect the swap (now self.d[10] = 0), pop the last element in self.q (removing 5), and delete self.d[5].
   • The operation returns true.

7. Current state:

   • The dynamic array self.q now holds [10], and self.d holds {10: 0}.

This simple example demonstrates the processes of each operation and how the combination of a hash table and a dynamic array can achieve O(1) average time complexity for insertions, removals, and accessing a random element.

Solution Implementation

Time and Space Complexity

Time Complexity:

• insert(val: int) -> bool: The insertion function consists of a dictionary check and insertion into a dictionary and a list, which are typically O(1) operations. Thus, the time complexity is O(1).
• remove(val: int) -> bool: The remove function performs a dictionary check, index retrieval, and element swap in the list, as well as removal from both the dictionary and list. Dictionary and list operations involved here are usually O(1). Therefore, the time complexity is O(1).
• getRandom() -> int: The getRandom function makes a single call to the choice() function from the Python random module, which selects a random element from the list in O(1) time. Hence, the time complexity is O(1).

Overall, each of the operations provided by the RandomizedSet class have O(1) time complexity.

Space Complexity:

• The RandomizedSet class maintains a dictionary (self.d) and a list (self.q). The dictionary maps element values to their indices in the list, and both data structures store up to n elements, where n is the total number of unique elements inserted into the set. Hence, the space complexity is O(n), accounting for the storage of n elements in both the dictionary and the list.

Learn more about how to find time and space complexity quickly using problem constraints.