# Concise Python solution with List, Dict and Set

• This solution assumes there is not ordering requirement for `remove`. `remove` will randomly remove an element among duplicates.

Similar to Problem 380 without duplicates, we use a list to contain all elements and use a dict to keep track of their indices. This time, we use a `set` to keep track of all indices for a value.

Just like Problem 380, when we remove a value, we randomly pop an index for that value from the set, swap the value with the last element of the list, and update the indices for the new value.

``````import random
class RandomizedCollection(object):

def __init__(self):
self.l, self.d = [], collections.defaultdict(set)

def insert(self, val):
self.l.append(val)
return len(self.d[val])==1

def remove(self, val):
if val not in self.d:
return False
i, newVal = self.d[val].pop(), self.l[-1]
len(self.d[val]) > 0 or self.d.pop(val, None)
if newVal in self.d:
self.d[newVal] = (self.d[newVal] | {i}) - {len(self.l)-1}
self.l[i] = newVal
self.l.pop()
return True

def getRandom(self):
return random.choice(self.l)
``````

Longer but clearer version:

``````import random
class RandomizedCollection(object):
def __init__(self):
self.l = []
self.d = collections.defaultdict(set)

def insert(self, val):
b = val not in self.d
self.l.append(val)
return b

def remove(self, val):
if val not in self.d:
return False
i, newVal = self.d[val].pop(), self.l[-1]
if len(self.d[val]) == 0:
del self.d[val]
self.l[i] = newVal
if newVal in self.d:
self.l.pop()
return True

def getRandom(self):
return random.choice(self.l)
``````

• @o_sharp Great use of list and defaultdict with set to make every method O(1)!

• @o_sharp I think your `remove()` in the longer version is bugged. It fails for the following input (thanks to @StefanPochmann for creating it):

``````rc = RandomizedCollection()
rc.insert(1)
rc.insert(0)
rc.insert(1)
rc.insert(1)
rc.insert(1)
rc.insert(1)
rc.insert(1)
rc.insert(1)
rc.insert(0)
rc.remove(0)
rc.remove(0)
``````

Can you understand how to fix it? I made the same mistake in my own solution (https://discuss.leetcode.com/topic/53896/frugal-python-code) but now I fixed it.

We should add a test case to the OJ to weed out this bug.

• This post is deleted!

• @agave Here's the input in LeetCode format:

``````["RandomizedCollection","insert","insert","insert","insert","insert","insert","insert","insert","insert","remove","remove"]
[[],[1],[0],[1],[1],[1],[1],[1],[1],[0],[0],[0]]
``````

Running that as Custom Testcase, @o_sharp's second solution fails with `Line 19: IndexError: list assignment index out of range` and the OJ fails as well, says Expected answer `Line 19: IndexError: list assignment index out of range`.

• @agave Here's the input in LeetCode format:

``````["RandomizedCollection","insert","insert","insert","insert","insert","insert","insert","insert","insert","remove","remove"]
[[],[1],[0],[1],[1],[1],[1],[1],[1],[0],[0],[0]]
``````

Running that as Custom Testcase, @o_sharp's second solution fails with `Line 19: IndexError: list assignment index out of range` and the OJ fails as well, says Expected answer `Line 19: IndexError: list assignment index out of range`.

@StefanPochmann thanks Stefan.
@1337c0d3r we should add this testcase to the OJ.

• @agave @StefanPochmann Thanks for the test case, guys! I have fixed my code, both versions.

I'm not sure why I let it slide, but I thought about handling this...

• @StefanPochmann Thanks so much for your test case, Stefan. I have just added it.

• @agave I encountered the same problem, then how to fix it?

• @leiyama001 check this out.

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