# Simple solution in Python

• 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
``````

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

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

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

• 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]
``````

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

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

• @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?

• 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

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

• len(self.nums) is O(n)

Uh... it's also O(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).

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

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