Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/

 

class RandomizedSet:

    def __init__(self):
        self.numMap = {}
        self.numList = []

    def insert(self, val: int) -> bool:
        res = val not in self.numMap
        if res:
            self.numMap[val] = len(self.numList)
            self.numList.append(val)
        return res

    def remove(self, val: int) -> bool:
        res = val in self.numMap
        if res:
            idx = self.numMap[val]
            lastVal = self.numList[-1]
            self.numList[idx] = lastVal
            self.numList.pop()
            self.nunMap[lastVal] = idx
            del self.numMap[val]
        return res

    def getRandom(self) -> int:
        return random.choice(self.numList)

remove operation is the key here

when removing we do not iterate through whole list , which cost O(n) , we simply have a index in map.

and then we swap with last list value , which takes O(1)