Insert Delete GetRandom O(1)

 

Problem Description: Design a data structure that supports insert, delete, and getRandom operations, all in O(1) average time complexity.

Example:

python
# Example usage of the data structure
obj = RandomizedSet()
param_1 = obj.insert(1)  # Returns True
param_2 = obj.remove(2)  # Returns False
param_3 = obj.insert(2)  # Returns True
param_4 = obj.getRandom()  # Returns 1 or 2 randomly
param_5 = obj.remove(1)  # Returns True
param_6 = obj.insert(2)  # Returns False (2 already exists)
param_7 = obj.getRandom()  # Returns 2

1. Clarify the problem: Before starting, let's ask some clarifying questions to ensure we fully understand the problem requirements:

  • Can the elements in the data structure be of any data type, or are they restricted to integers?
  • Can the getRandom operation return the same element multiple times in a row, or should it always return a new random element?

2. Analyze the problem: Let's break down the problem to better understand its components:

  • Input: Commands to insert, delete, or get a random element from the data structure.
  • Output: The result of each command.
  • Constraints: The insert and delete operations should have O(1) average time complexity.

3. Design an algorithm: To solve this problem efficiently, we can use a combination of a dictionary and a list to achieve constant time complexity for insert, delete, and getRandom operations:

  • We can use a dictionary to store the elements as keys, and their corresponding indices in the list as values.
  • The list will store the elements in the order they were inserted, allowing us to access elements by their indices.

Here's an outline of the algorithm:

  1. Initialize an empty dictionary element_to_index and an empty list elements.
  2. For the insert operation, check if the element already exists in the dictionary. If it does, return False. Otherwise, add the element to the dictionary with its index as the value, add the element to the list, and return True.
  3. For the delete operation, check if the element exists in the dictionary. If it does not, return False. Otherwise, get the index of the element from the dictionary, replace the element at that index in the list with the last element in the list, update the index of the last element in the dictionary, remove the element from the dictionary, and remove the last element from the list. Finally, return True.
  4. For the getRandom operation, generate a random index within the range of the list length and return the element at that index.

4. Explain your approach: We will use a dictionary to store the elements as keys and their indices in the list as values. This allows us to perform insert, delete, and getRandom operations in constant time. The insert operation checks if the element already exists in the dictionary before adding it. The delete operation checks if the element exists in the dictionary before removing it. The getRandom operation generates a random index to access a random element from the list.

5. Write clean and readable code:

Here's an implementation of the algorithm in Python:

python
import random

class RandomizedSet:
    def __init__(self):
        self.element_to_index = {}
        self.elements = []

    def insert(self, val):
        if val in self.element_to_index:
            return False

        self.element_to_index[val] = len(self.elements)
        self.elements.append(val)
        return True

    def remove(self, val):
        if val not in self.element_to_index:
            return False

        index = self.element_to_index[val]
        last_element = self.elements[-1]

        self.elements[index] = last_element
        self.element_to_index[last_element] = index

        self.elements.pop()
        del self.element_to_index[val]
        return True

    def getRandom(self):
        random_index = random.randint(0, len(self.elements) - 1)
        return self.elements[random_index]

6. Test your code: Now, let's test the code with the example usage and some additional test cases to verify its correctness:

python
# Example usage
obj = RandomizedSet()
print(obj.insert(1))  # Output: True
print(obj.remove(2))  # Output: False
print(obj.insert(2))  # Output: True
print(obj.getRandom())  # Output: 1 or 2 randomly
print(obj.remove(1))  # Output: True
print(obj.insert(2))  # Output: False (2 already exists)
print(obj.getRandom())  # Output: 2

# Additional test cases
obj = RandomizedSet()
print(obj.insert(1))  # Output: True
print(obj.remove(2))  # Output: False
print(obj.insert(2))  # Output: True
print(obj.insert(3))  # Output: True
print(obj.getRandom())  # Output: 1, 2, or 3 randomly
print(obj.remove(2))  # Output: True
print(obj.getRandom())  # Output: 1 or 3 randomly

7. Optimize if necessary: The given solution already achieves the desired time complexity of O(1) for all operations. There is no further optimization needed.

8. Handle error cases: In the code implementation, the insert and remove operations return False when the element does not exist in the data structure. This can be considered as handling error cases or invalid input.

9. Discuss complexity analysis:

  • Time complexity: The insert, remove, and getRandom operations all have a time complexity of O(1) on average. This is achieved by using a dictionary to store the elements and their indices, allowing constant-time access and update operations.
  • Space complexity: The space complexity is O(n), where n is the number of elements inserted into the data structure. The elements are stored in both the dictionary and the list, each occupying O(n) space.
Next Post Previous Post