A set with constant-time insert, remove and random pick. Keep values in a list and their positions in a map, and delete by swapping with the last.
▼The problem
LeetCode 380 (Medium). Design RandomizedSet with insert(val) (returns False if already present), remove(val) (returns False if absent) and getRandom() (each current element equally likely), all in average O(1) time.
A hash set alone can't pick uniformly at random without walking through it; a list alone makes remove O(n) because everything after the removed item shifts. The fix uses both: a list of values plus a map from value to its index. To remove, copy the last value into the removed value's slot, update the moved value's index, then pop the end and delete the removed key.
Walkthrough example, each state computed in src/raffle.jsx (STATES):
| Op | List after | Map after | Note | |---|---|---|---| | insert(5) | [5] | 5→0 | | | insert(8) | [5, 8] | 5→0, 8→1 | | | insert(3) | [5, 8, 3] | …, 3→2 | | | insert(6) | [5, 8, 3, 6] | …, 6→3 | slots 0 to 3 | | remove(8) | [5, 6, 3] | 5→0, 6→1, 3→2 | 8 was in slot 1; 6 (the last) moves there, the end is popped | | getRandom() | | | the wheel lands on slot 2, so it returns 3 |
The solution
class RandomizedSet:
def __init__(self):
self.vals, self.pos = [], {}
def insert(self, x):
if x in self.pos: return False
self.pos[x] = len(self.vals)
self.vals.append(x)
return True
def remove(self, x):
if x not in self.pos: return False
i, last = self.pos[x], self.vals[-1]
self.vals[i], self.pos[last] = last, i
self.vals.pop()
del self.pos[x]
return True
def getRandom(self):
return random.choice(self.vals)Transcript
Insert Delete Get Random O of One. Design a set that can insert a value, remove a value, and return a random one, each equally likely. All three should take constant time on average.
Say the set holds five, eight and three. Get random should return each of them about a third of the time.
A hash set inserts and removes quickly, but it has no positions, so a random pick means walking through it. A list can pick a random index, but removing from the middle shifts everything after it: O of n.
So use both: a list of values, like raffle tickets in numbered slots, and a map from each value to its slot. To remove a ticket, don't leave a gap. Move the last ticket into its slot, update its slot in the map, and drop the end.
In code, insert records the next index, then appends. Remove copies the last value into the gap, fixes its index, then pops and deletes. Get random picks any index.
Let's run it. Insert five, eight, three and six: slots zero to three. Remove eight, in slot one. Six jumps from the end into slot one, the map now says six is at one, and the list shrinks. Get random spins over three slots and lands on slot two: three.
Each move is a map lookup plus work at the end of the list, so all three are O of one on average, with O of n space.
Swap with the last, then pop. That's Insert Delete Get Random.