Insert Delete GetRandom O(1) | Solution Explained
LeetCode 380. Insert Delete GetRandom O(1) is an implementation based question, requiring us to know the time complexities of simple data structures like lists and sets. Problem Link.
Insert Delete GetRandom: Inefficient Version
- my first instinct was to use sets.
- it works great for
- insert
- remove
- but it fails in the case of
getRandom, where we’ll have a type error
- it works great for
The only way to get around it, is to use random.choice(list(set)), which is going to convert the entire list into a set. But, this takes O(N) time.
class RandomizedSet:
def __init__(self):
self.s = set()
def insert(self, val: int) -> bool:
if val in self.s:
return False
self.s.add(val)
return True
def remove(self, val: int) -> bool:
if val in self.s:
self.s.remove(val)
return True
return False
def getRandom(self) -> int:
return random.choice(list(self.s))
Insert Delete GetRandom: Optimized
- we need a list,
data, that stores all the items in a list - since search and removal is inefficient in list, we workaround by using another dictionary for O(1) retrieval of information – is the
valin the list or not?
class RandomizedSet:
def __init__(self):
self.data = []
self.d = {}
def insert(self, val: int) -> bool: #O(1)
if val in self.d: return False
self.d[val] = len(self.data)
self.data.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.d: return False
index = self.d[val]
last = self.data[-1]
curr = self.data[index]
self.data[index] = last
self.data[-1] = curr
self.data.pop()
self.d[last] = index
del self.d[curr]
return True
def getRandom(self) -> int: # O(1)
return random.choice(self.data)
References:
The below link is an amazing resource. I keep it bookmarked for future reference 🙂
- https://wiki.python.org/moin/TimeComplexity
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022