# Python solution (188ms) with time complexity notations for each step

• """

``````from random import randint
class RandomizedSet(object):

def __init__(self):
"""
"""
self.vals = list()
self.locs = dict()

def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val in self.locs: # O(1)
return False
else:
self.vals.append(val)  # O(1)
self.locs[val] = len(self.vals) - 1  # O(1)
return True

def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val in self.locs: # O(1)
lastval = self.vals[-1] # O(1)
if lastval != val:
pos = self.locs[val] # O(1)
self.vals[pos], self.vals[-1] = self.vals[-1], self.vals[pos] # O(1)
self.locs[lastval] = pos # O(1)
self.vals.pop(-1) # O(1)
self.locs.pop(val) # O(1)
return True
else:
return False

def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
return self.vals[randint(0, len(self.vals)-1)] # O(1)
``````

"""

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