[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

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

Similar to the problem # 380, to get O(1) time complexity for deleting operation, we need to save the index of each value in the value list.  Because it allows duplicated value be inserted and deleting item from bidirectional linked list is O(1). we can manage nodes with same value in a bidirectional linked list. Then the hash table saves the index of the last item of one value's bidirectional linked list. 

class Node:
    def __init__(self, val, pre, nxt):
        self.val = val
        self.pre = pre
        self.nxt = nxt
        
        
class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        # nodes with same value are linked as a bidirectional linked list
        # dict[K] save the index of the last node of number K's linked list 
        self.dict = defaultdict(lambda: -1)
        
        # save all values
        self.list = []
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        
        index = len(self.list)
        
        if self.dict[val] == -1:
            node = Node(val = val, pre = -1, nxt = -1)
            
            self.dict[val] = index
            self.list.append(node)
            
            return True
        else:
            pre = self.dict[val]
            node = Node(val = val, pre = pre, nxt = -1)
            
            # append to the existing bidirectional link
            
            preNode = self.list[pre]
            preNode.nxt = index
            
            self.dict[val] = index
            self.list.append(node)
            
            return False

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        
        if self.dict[val] == -1:
            return False
        
        # use the last item of self.list to replace the removed item
        # and update the the altered item indices
        
        index = self.dict[val]
        node = self.list[index]
        
        if node.pre == -1:
            self.dict[val] = -1
        else:
            # remove from the removed node's bidirectional linked list
            self.dict[val] = node.pre
            self.list[node.pre].nxt = -1
            
        tailIndex = len(self.list) - 1
        tailNode = self.list.pop()

        if index != tailIndex:
            self.list[index] = tailNode

            # update tailNode's bidirectional linked list
            if self.dict[tailNode.val] == tailIndex:
                self.dict[tailNode.val] = index

            if tailNode.pre != -1:
                self.list[tailNode.pre].nxt = index

            if tailNode.nxt != -1:
                self.list[tailNode.nxt].pre = index
                
        return True
    
    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        
        index = random.randint(0, len(self.list) - 1)
        return self.list[index].val


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

P.S. We can also use hash set to save all list item indices of a given value. Deleting item from hash set is also O(1).