Insert Delete GetRandom O(1)

2 min read
LC-Medium

Oct 21, 2022

3 years ago

LeetCode

Solution

Use a hashmap to get O(1) access and a list for O(1) random element
- In the hashmap, key is the value and value is the index in a list
The main problem is the random function because we cannot index a hashset or a hashmap
So we use another list to store values that can get us a random index in O(1) time
Whenever we add a value, add it to the list first, and also add it to the hashmap where the value is the new values' index in the list
When removing, get the index of the value to remove, replace it with the element at the end of the list, and then pop the element from the end of the list
- Then, update the index for the element that was swapped in
- Remove the value from the hashmap
This ensures that all our functions have O(1) TC

Time	Space	Explanation
`O()`	`O()`

class RandomizedSet: def __init__(self): self.v_map = {} self.values = [] def insert(self, val: int) -> bool: if val not in self.v_map: self.values.append(val) idx = len(self.values) - 1 self.v_map[val] = idx return True return False def remove(self, val: int) -> bool: if val in self.v_map: idx = self.v_map[val] n = len(self.values) repl_val = self.values[n - 1] self.values[idx] = repl_val self.v_map[repl_val] = idx self.values.pop() del self.v_map[val] return True return False def getRandom(self) -> int: n = len(self.values) idx = randint(0, n - 1) return self.values[idx]