Concise Python solution with List, Dict and Set


  • 1
    O

    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.d[val].add(len(self.l))
            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.d[val].add(len(self.l))
            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.d[newVal].add(i)
                self.d[newVal].discard(len(self.l)-1)
            self.l.pop()
            return True
    
        def getRandom(self):
            return random.choice(self.l)
    

  • 0
    W

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


  • 0

    @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.


  • 0
    This post is deleted!

  • 1

    @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.


  • 0

    @StefanPochmann said in Concise Python solution with List, Dict and Set:

    @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.


  • 0
    O

    @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...


  • 0

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


  • 0
    L

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


  • 0

    @leiyama001 check this out.


Log in to reply
 

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