LC 0380 [M] Insert Delete GetRandom O(1) - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=j4KwhBziOpg&ab_channel=NeetCode

implement a set

the difficulty comes from needing to remove from the middle of the list (so we use a hashmap with positions instead of a hashset) and the getRandom() which requires equal probability

class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.pos = {} # value to index
        

    def insert(self, val: int) -> bool:
        if val not in self.pos:
            self.nums.append(val)
            self.pos[val] = len(self.nums) - 1
            return True
        return False
    

    def remove(self, val: int) -> bool:
        # take the last value, move it into the index we're removing from, then pop that last value (to maintain getRandom() equal probability) 
        if val in self.pos:
            pos = self.pos[val] # find pos to remove
            last = self.nums[-1] # get last value

            self.nums[pos] = last # set value at pos to the last value
            self.pos[last] = pos # set pos of last value to pos removed

            self.nums.pop() # remove last value
            del self.pos[val] # delete pos of value

            return True
        return False
        

    def getRandom(self) -> int:
        pos = randint(0, len(self.nums) - 1) # random.choice(self.nums)
        return self.nums[pos]
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()