LC380 Insert Delete GetRandom O(1)

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {} # value : idx 
        self.arr = []   

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
                """time O(1) space O(N) N:  number of insertion
        1. check if val in dict
        2. update list, get val's index 
        3. update dictionary with val's index 
        """
        if val not in self.d:
            self.arr.append(val)
            self.d[val] = len(self.arr)-1
            return True
        return False

    def remove(self, val: int) -> bool:
        """ time O(1) space O(1)
        1.check if val in dict,get its idx 
        2. swap with last val in list 
        3. remove last val in the list and val's entry in the dict 
        4. update swapped val's idx 
        """
#step1 check if in dic:  
#step 2 if yes => find idx and target last number in the list, swap 
#step3 pop() last element in the list and remove history in htable ;  #step4 update new idx for swaped val in htable
        f val in self.d:
            # swap/replace with last element in arr and update self.d 
            idx = self.d[val]
            last =self.arr[-1] # cache last value for future self.d update 
            self.arr[idx]= self.arr[-1]
            self.arr.pop()
            self.d[last] = idx 
             # dictionary operation for removing specific key; can also use del self.htable[val]
            self.d.pop(val) 
            return True
        return False 

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        """ time O(1) space O(1)
        1. get left, right boundry of random val
        2. get random val 
        3. return its correspoinding val 
        """ 
        ridx = random.randint(0,len(self.arr)-1)
        return self.arr[ridx]

        


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