Simple solution in Python


  • 31

    We just keep track of the index of the added elements, so when we remove them, we copy the last one into it.

    From Python docs (https://wiki.python.org/moin/TimeComplexity) we know that list.append() takes O(1), both average and amortized. Dictionary get and set functions take O(1) average, so we are OK.

    import random
    
    class RandomizedSet(object):
    
        def __init__(self):
            self.nums, self.pos = [], {}
            
        def insert(self, val):
            if val not in self.pos:
                self.nums.append(val)
                self.pos[val] = len(self.nums) - 1
                return True
            return False
            
    
        def remove(self, val):
            if val in self.pos:
                idx, last = self.pos[val], self.nums[-1]
                self.nums[idx], self.pos[last] = last, idx
                self.nums.pop(); self.pos.pop(val, 0)
                return True
            return False
                
        def getRandom(self):
            return self.nums[random.randint(0, len(self.nums) - 1)]
    
    # 15 / 15 test cases passed.
    # Status: Accepted
    # Runtime: 144 ms
    

  • 0
    M

    @agave Interesting. Using "random.choice(self.pos.keys())" would make it O(n) correct? hence we can't use that in the random method.


  • 1
    Z

    How does self.pos.pop make O(1)? it should be O(n)


  • 0
    R

    I still don't understand why do you need a list ? you can store everything in a dictionary ?


  • 1
    X

    This code does the same thing(O(1)).

    def getRandom(self):
        return random.choice(self.nums)
    

    In python lib's random.py:

        def choice(self, seq):
            try:
                i = self._randbelow(len(seq))
            except ValueError:
                raise IndexError('Cannot choose')
            return seq[i]
    

  • 3
    X

    @rahul8590
    When you store everything in a dictionary or set, it's fine when you insert or remove.

    But if you want to achieve O(1) on getRandom(), it's impossible.
    You have to turn it into a list first, which is O(n).


  • 0

    @zhahaoyu self.pos is a dictionary and removing a key, value pair from a dictionary should take O(1) time


  • 0
    R

    @agave I'm tried to solve this problem. But Getting random number in the set is differed. So my test case is getting failed

    My OP - [null,true,false,true,1,true,false,1]
    test case - [null,true,false,true,2,true,false,2]

    Here getting a random number may differ.

    can you help me in this?


  • 1
    T

    Thanks for the working example.

    It was really hard to read the remove method because there were 2 operations per line. Yes, this style does have a place in Python, but I'd argue this usage is just chasing a low line count: Mutliple assignment (e.g. a, b = b, a) is great when the operands have a dependency on each other, which is not really the case here. Mulitple statements per line are just hard to read.

    I've updated the method to be more readable:

        def remove(self, val):
            if val in self.pos:
                idx = self.pos[val] # get val index in list
                last = self.nums[-1] # get the last addition
                self.nums[idx] = last # overwrite val index with last addition
                self.pos[last] = idx # update the last addition's index to it's new spot
                self.nums.pop() # get rid of the last addition from it's original spot...it now has a new home elsewhere
                del self.pos[val] # original line was "self.pos.pop(val, 0)". we don't need pop-or-default semantics here, del will work
                return True
            return False
    

    I'd also recommend the nicer random.choice(list) interface over random.randint-ing over the length of the array. Less error prone and still O(1). Under the hood, it does the same thing. https://github.com/python/cpython/blob/3.6/Lib/random.py#L253


  • 0
    W

    well, len(self.nums) is O(n). I would suggest to add a self.N=0 at init to record the length of the array.


  • 1

    @weidairpi said in Simple solution in Python:

    len(self.nums) is O(n)

    Uh... it's also O(1).


  • 1

    @weidairpi As ManueIP pointed out I believe each iterable has a length property and len() just retrieves that value making the process O(1).


  • 2
    T

    @Ellest said in Simple solution in Python:

    @weidairpi As ManueIP pointed out I believe each iterable has a length property and len() just retrieves that value making the process O(1).

    Sorry to split hairs, but "iterable" has a precise meaning in Python that is different than the ability to return a length.

    For example itertools.repeat("same") is iterable, but does not offer a length.


Log in to reply
 

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