Python solution with detailed explanation

  • 0


    Insert Delete GetRandom O(1) - Duplicates allowed

    1. This is an extension of the related problem. Instead of hash-map of value to index, we use a hash-map of value to set of indices.
    2. Insertion is easy - always add to the end.
    3. Removal is tricky as usual.
    • Test if value is in this set or not
    • Pop any index from the set of indices for this value
    • If the index is the last element, pop from nums array and return
    • Otherwise swap with the last element.
    • Then you need to fix the hash-map:
      last_number = self.nums[-1] # Get the last number
      self.nums[idx], self.nums[-1] = last_number, val # Swap with the last number
      self.hmap[last_number].remove(len(self.nums)-1) # Remove the last index for last_number
      self.hmap[last_number].add(idx) # Add idx to the set for last_number
    from random import randint
    class RandomizedCollection(object):
        def __init__(self):
            Initialize your data structure here.
            self.nums = []
            self.hmap = {}
        def insert(self, val):
            Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
            :type val: int
            :rtype: bool
            if (val not in self.hmap):
                self.hmap[val] = set([])
            return True
        def remove(self, val):
            Removes a value from the collection. Returns true if the collection contained the specified element.
            :type val: int
            :rtype: bool
            if val not in self.hmap or not self.hmap[val]:
                return False
                idx = self.hmap[val].pop()
                if idx == len(self.nums)-1:
                    last_number = self.nums[-1]
                    self.nums[idx], self.nums[-1] = last_number, val
                return True        
        def getRandom(self):
            Get a random element from the collection.
            :rtype: int
            if len(self.nums) != 0:
                return self.nums[randint(0, len(self.nums)-1)]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.