# Python solution with detailed explanation

• Solution

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.nums.pop()
``````from random import randint
class RandomizedCollection(object):
def __init__(self):
"""
"""
self.nums = []
self.hmap = {}
return

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([])
self.nums.append(val)
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
else:
idx = self.hmap[val].pop()
if idx == len(self.nums)-1:
self.nums.pop()
else:
last_number = self.nums[-1]
self.nums[idx], self.nums[-1] = last_number, val
self.hmap[last_number].remove(len(self.nums)-1)
self.nums.pop()
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)]
``````

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