Insert Delete GetRandom O(1)
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Design a set with insert(val), remove(val) and getRandom() (each element equally likely), all in average O(1).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Why can't a plain dictionary give a random element in O(1)?
- Hint 2How can you delete from the middle of an array in O(1) if order does not matter?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A row of lockers filled from the left without gaps, plus a register that says which locker holds which item. Picking a random item: choose a random locker number. Removing an item from the middle would leave a hole, so the item in the LAST locker moves into the empty one, the register is updated, and the last locker is closed. The row stays gap-free.
- The obvious way
A list alone: insert O(n) to check duplicates and remove O(n).
- The key insight
Keep a list of values and a dictionary value -> its index in the list. insert: if present False; else append and record the index. remove: if absent False; else move the last value into the removed value's place (update its recorded index), pop the last, delete the removed key. getRandom: choose a random list element.
- The algorithm
- insert: skip if known, else append and record its index.
- remove: copy the last value into the hole and fix its index.
- Pop the last and forget the removed value.
- getRandom: random pick from the list.
Watch it run
Exampleinsert 1; remove 2; insert 2; getRandom; remove 1; insert 2; getRandom
insert 1: new, True. remove 2: not there, False. insert 2: new, True. The lockers hold [1, 2].
[1, 2]
Where people slip
- Update the last value's recorded index BEFORE deleting the removed key; when they are the same value the order matters.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
import random
class RandomizedSet:
def __init__(self):
self.values = [] # lockers filled from the left, no gaps
self.locker_of = {} # value -> its locker number
def insert(self, val):
if val in self.locker_of:
return False
self.locker_of[val] = len(self.values)
self.values.append(val)
return True
def remove(self, val):
if val not in self.locker_of:
return False
locker = self.locker_of[val]
last_value = self.values[-1]
self.values[locker] = last_value # the last item fills the hole
self.locker_of[last_value] = locker
self.values.pop() # close the last locker
del self.locker_of[val]
return True
def getRandom(self):
return random.choice(self.values)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.