Insert Delete GetRandom O(1)
Combine an array and a hash map so insert, remove and random selection are all constant time
Problem Statement
Design a data structure supporting three operations in average O(1) time:
insert(val)— addvalif not present; return whether it was addedremove(val)— removevalif present; return whether it was removedgetRandom()— return a random element, each with equal probability
insert(1) → true set: {1}
remove(2) → false (not present)
insert(2) → true set: {1, 2}
getRandom() → 1 or 2, each with probability 1/2
remove(1) → true set: {2}
getRandom() → 2Intuition
Neither obvious structure can do all three.
Why one structure is not enough
A hash set gives O(1) insert and remove — but no random access. Picking a uniformly random element requires iterating to a random position, which is O(n).
An array gives O(1) random access via array[randint(0, n-1)] and O(1) append — but removing a value means finding it (O(n)) and then shifting everything after it (O(n)).
The key insight — use both, and fix removal with a swap
Keep an array of the values (for random access) and a hash map from value to its index in that array (to locate it instantly).
The remaining problem is that deleting from the middle of an array is O(n). The fix:
Swap the doomed element with the last element, then pop the last.
Removing from the end of an array is O(1), and order does not matter because getRandom treats all positions equally.
The swap-with-last trick
array: [10, 20, 30, 40] map: {10:0, 20:1, 30:2, 40:3}
remove(20) → index 1
Step 1: move the last element into the hole
array: [10, 40, 30, 40] map: {10:0, 40:1, 30:2} ← 40's index updated
Step 2: pop the now-duplicated tail
array: [10, 40, 30] map: {10:0, 40:1, 30:2}Two writes and a pop. Nothing shifts.
The step everyone forgets
After moving the last element into the hole, its entry in the map still points at the old index. Update it before popping or every later operation on that value corrupts the structure.
Watch it run
Approach
Maintain two structures
values — a list of the elements. index_of — a map from value to its position in values.
insert(val)
If val is already a key, return false. Otherwise append it and record index_of[val] = len(values) - 1.
remove(val)
If absent, return false. Otherwise: look up its index, copy the last value into that slot, update that value's index in the map, pop the array, and delete val from the map.
getRandom()
Return values[random index]. Because the array is always compact, every element has probability exactly 1/n.
Solution
import random
class RandomizedSet:
"""Insert, remove and uniform random selection, all in average O(1)."""
def __init__(self) -> None:
self._values: list[int] = [] # compact array for random access
self._index_of: dict[int, int] = {} # value -> its index in _values
def insert(self, val: int) -> bool:
if val in self._index_of:
return False
self._index_of[val] = len(self._values)
self._values.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self._index_of:
return False
# Move the last element into the hole left by val.
hole = self._index_of[val]
last = self._values[-1]
self._values[hole] = last
self._index_of[last] = hole # critical: keep the map in sync
self._values.pop()
del self._index_of[val]
return True
def getRandom(self) -> int:
return random.choice(self._values)Why removing the last element still works
When val is the last element, hole equals the final index and last equals val itself. The code writes val back over itself, sets index_of[val] = hole (no change), then pops the array and deletes the map entry.
The redundant write is harmless, and the operation is still correct — which is why no special case is needed. Order matters though: deleting from the map before the swap would remove the entry that the swap then re-adds, leaving a stale key.
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(n)
- Time — every operation is a fixed number of hash lookups and array accesses. "Average"
O(1)because hash collisions are theoretically possible; in practice it is constant. - Space —
O(n)for the array plusO(n)for the map. Doubling memory to make all three operations constant is exactly the trade the problem is about.
Edge Cases
Related Problems
- Min Stack — another design problem where extra storage buys
O(1)queries - Two Sum — hash maps replacing search with lookup
- Contains Duplicate — set membership in
O(1)