LeetCode #380 Medium

Insert Delete GetRandom O(1)

Design a set with average O(1) insertion, removal, and uniform random selection.

arrayhash-tabledesignrandomized

02

Intuition

A hash set gives constant-time membership and removal, but it cannot choose a uniformly random stored value by index. An array gives constant-time random indexing, yet deleting from its middle normally shifts later elements. Keep both structures synchronized: the map tells you where a value sits in the array, and removal fills the hole with the array's last value before popping the end. That swap changes only one stored index, so both deletion and random access remain O(1).

How to spot this pattern

Constant-time membership and deletion suggest hashing, while uniform random selection suggests a dense indexable array. When both are required, store value-to-index mappings and use swap-delete to prevent gaps and shifts.

03

Approach

1

Pair a dense value array with an index map

Store every value once in values, and map that value to its current array index. Insertion checks the map, records the next array position, and appends. The array stays dense, which is necessary for every index to have equal probability in getRandom.

2

Delete by moving the final value into the hole

Use the map to find the removed value's index. Copy the final array value into that index, update the moved value's map entry, then pop the array tail and delete the removed key. This also works when the removed value is already last: the temporary self-update is harmless before its key is deleted.

3

Sample directly from the dense array

Choose a random array element rather than a random map key. Because every stored value occupies exactly one array position, uniform random indexing gives every value equal probability. Each public operation is O(1) on average.

04

Solution

▶1class RandomizedSet:
▶2    def __init__(self):
▶3        self.values = []
▶4        self.index = {}
▶5 
▶6    def insert(self, val: int) -> bool:
▶7        if val in self.index:
▶8            return False
▶9 
▶10        self.index[val] = len(self.values)
▶11        self.values.append(val)
▶12        return True
▶13 
▶14    def remove(self, val: int) -> bool:
▶15        if val not in self.index:
▶16            return False
▶17 
▶18        index = self.index[val]
▶19        last_value = self.values[-1]
▶20        self.values[index] = last_value
▶21        self.index[last_value] = index
▶22 
▶23        self.values.pop()
▶24        del self.index[val]
▶25        return True
▶26 
▶27    def getRandom(self) -> int:
▶28        return random.choice(self.values)

05

Common pitfalls

Using linear array removal

✗ Wrong

self.values.remove(val)

✓ Right

self.values[index] = last_value

list.remove searches and shifts elements, violating the average O(1) requirement.

Leaving the moved value's old index

✗ Wrong

self.index[last_value] = len(self.values) - 1

✓ Right

self.index[last_value] = index

After the swap, the last value occupies the removed value's former slot. Keeping its tail index corrupts the next removal.

Sampling the map instead of the array

✗ Wrong

return random.choice(self.index)

✓ Right

return random.choice(self.values)

The array is the dense random-access structure; random.choice does not operate on a dictionary as a value sequence.

06

Edge cases

Removing the only stored value

The value is copied onto its own index, popped, and removed from the map, leaving both structures empty.

Inserting a value that already exists

The map check returns false before either structure changes, so no duplicate array slot is created.

Removing a missing value

The method returns false immediately and leaves the array-map invariant untouched.

07

Complexity

Time

O(1) average per operation

Space

O(n)

The list and map each store one entry per value.