# 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

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
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 `val` in 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

##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.