0380.Insert Delete GetRandom O(1)

• Link: 380. Insert Delete GetRandom O(1) - Medium
• Track: NeetCode150

Question

Restate the problem

Design a data structure that supports these operations in average O(1) time:

• insert(val): insert val if it does not already exist
• remove(val): remove val if it exists
• getRandom(): return a random element from the current set, where each element should have equal probability of being returned

Edge Case

• Insert a value that already exists → return False
• Remove a value that does not exist → return False
• Remove the last element in the array
• getRandom() is only called when at least one element exists

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Array + Hash Map	- insert: $O(1)$ average - remove: $O(1)$ average - getRandom: $O(1)$	$O(n)$

Method 1 - Array + Hash Map

Approach

Key idea:

• a list array to store values, so getRandom() can return a random element in O(1)
• a hash map pos to store {value: index}, so we can find any value’s position in O(1)

Why not remove directly from the middle of the array?

• Removing from the middle of a Python list is O(n), because elements after it must shift.

• To make removal O(1):

  • find the index of the value to remove
  • take the last element in the array
  • move that last element into the removal position
  • update its index in the hash map
  • pop the last element from the array

Complexity

• Time Complexity:
  • insert: $O(1)$ average
  • remove: $O(1)$ average
  • getRandom: $O(1)$
• Space Complexity: $O(n)$

Code

import random
 
class RandomizedSet:
 
    def __init__(self):
        self.values = []
        self.pos = {}
 
    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
 
        self.pos[val] = len(self.values)
        self.values.append(val)
        return True
 
    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False
 
        # find remove_idx and last_val
        remove_idx = self.pos[val]
        last_val = self.values[-1]
 
        # move the last to remove_idx position
        self.values[remove_idx] = last_val
        self.pos[last_val] = remove_idx
 
        # update array and hashmap
        self.values.pop()
        del self.pos[val]
        
        return True
 
    def getRandom(self) -> int:
        return random.choice(self.values)

---

Mistake

• import random → random.choice
• In remove(), self.pos[last_val] = remove_idx