Insert Delete GetRandom O(1) (Leetcode 380)

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

class RandomizedSet:

    def __init__(self):
        self.d={}
        self.nums=[]
        
    def insert(self, val: int) -> bool:
        
        if(val in self.d):
            return False    
        else:
            self.d[val]=len(self.nums)
            self.nums.append(val)
            return True
        
    def remove(self, val: int) -> bool:
        if(val not in self.d):
            return False
        else:
            idx=self.d[val]
            lastele=self.nums[-1]
            self.nums[idx]=lastele
            # Do not write del self.d[val] in this line
            # write it at the end.
            # To understand more, try a testcase where
            # there is only one element
            # Try this test case:
            # ["RandomizedSet","remove","remove","insert","getRandom","remove","insert"]
            # [[],[0],[0],[0],[],[0],[0]]
            self.nums.pop()
            self.d[lastele]=idx
            del self.d[val]
            return True

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


# 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()

Last updated