{x}
blog image

Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

 

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

 

Constraints:

  • -231 <= val <= 231 - 1
  • At most 2 * 105 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

Solution Explanation: RandomizedSet with O(1) Time Complexity

The problem requires implementing a RandomizedSet data structure that supports insertion, deletion, and random element retrieval, all with an average time complexity of O(1). This is achieved using a combination of a hash table (dictionary in Python, map in Java, etc.) and a dynamic array (list in Python, ArrayList in Java, etc.).

Data Structures:

  • Hash Table (d): Maps each element (val) to its index in the dynamic array. This allows for O(1) lookup of an element's index, crucial for both insertion and deletion.

  • Dynamic Array (q): Stores the elements of the set. This structure allows for efficient random element retrieval via random index selection.

Algorithm:

  1. insert(val):

    • Check if val exists in the hash table (d). If it does, return false (element already present).
    • If not, add val to the end of the dynamic array (q).
    • Add the val and its index (its new position in q) to the hash table (d).
    • Return true (insertion successful).

  2. remove(val):

    • Check if val exists in the hash table (d). If not, return false (element not present).
    • Get the index (i) of val from the hash table (d).
    • Swap: Swap val with the last element in q. This is a key optimization to maintain O(1) average time complexity. We replace val with the last element to avoid shifting other elements.
    • Update the index of the swapped element in d.
    • Remove the last element from q (which is now the former val).
    • Remove val from the hash table (d).
    • Return true (removal successful).

  3. getRandom():

    • Generate a random index within the bounds of the current size of q.
    • Return the element at that random index from q.

Time Complexity Analysis:

  • insert(val): O(1) on average. Hash table operations (insertion, lookup) take O(1) average time. Appending to a dynamic array is also O(1) amortized time.

  • remove(val): O(1) on average. Hash table operations (lookup, deletion) take O(1) on average. Swapping two elements is O(1).

  • getRandom(): O(1). Accessing an element by index in a dynamic array takes O(1) time.

Space Complexity: O(n), where n is the number of elements in the set. Both the hash table and the dynamic array store n elements in the worst case.

Example Code (Python):

import random
 
class RandomizedSet:
    def __init__(self):
        self.map = {}  # Hash table
        self.list = [] # Dynamic array
 
    def insert(self, val: int) -> bool:
        if val in self.map:
            return False
        self.map[val] = len(self.list)
        self.list.append(val)
        return True
 
    def remove(self, val: int) -> bool:
        if val not in self.map:
            return False
        index = self.map[val]
        last_val = self.list[-1]
        self.list[index] = last_val # Swap
        self.map[last_val] = index # Update index in map
        self.list.pop() # Remove last
        del self.map[val] # Remove from map
        return True
 
    def getRandom(self) -> int:
        return random.choice(self.list)

The code in other languages follows the same logic, using the appropriate data structures for each language. The key is the efficient use of the hash table for fast lookups and the swap operation to avoid the O(n) time complexity of removing an element from the middle of a list.