Insert Delete GetRandom O(1) (LeetCode 380)
Build a class, RandomizedSet, that stores a set of distinct integers and can hand back one of them at random. Every operation has to take O(1) time on average.
RandomizedSet()creates an empty set.bool insert(int val)addsvalif it is missing. It returnstruewhenvalwas added andfalsewhen it was already there.bool remove(int val)deletesvalif it is there. It returnstruewhenvalwas deleted andfalsewhen it was not in the set.int getRandom()returns one of the stored values, chosen so that every value in the set at that moment is equally likely.
Worked Examples
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]][null,true,false,true,2,true,false,2]insert(1) adds 1. remove(2) returns false: 2 is not stored. insert(2) adds 2, so the set is {1, 2} and the first getRandom() may return 1 or 2, each with probability 1/2 (LeetCode shows 2). remove(1) leaves {2}, insert(2) returns false because 2 is already stored, and the last getRandom() can only return 2.⚖️Formal Constraints & Bounds
-231 <= val <= 231 - 1At most
2 * 105calls are made toinsert,removeandgetRandomaltogether.getRandomis only called when the set holds at least one value.
Core Insight
A list gives a uniform random pick but only deletes its last slot in O(1), so delete by moving the last value into the hole and recording its new slot in the map: the list stays gap-free and every value keeps exactly one slot.
Real-World Scenario & Production Applications
A load balancer that sends each request to a random healthy server, a game that picks a random live enemy, or a sampler that draws a random active user all need to add and drop members constantly and pick one at random with equal chances. A hash set can't pick at random without copying itself; a packed array with a value-to-slot map does all three in O(1).
Step-by-Step Execution Trace Table
The debugger's first preset (the trap case: remove(2) while 2 is the last value):
| Call | self.values after the call | self.index after the call | Returns | What happened |
|---|---|---|---|---|
RandomizedSet() | [] | {} | null | An empty set |
insert(1) | [1] | {1: 0} | true | 1 takes slot 0 |
insert(2) | [1, 2] | {1: 0, 2: 1} | true | 2 takes slot 1 |
insert(3) | [1, 2, 3] | {1: 0, 2: 1, 3: 2} | true | 3 takes slot 2 |
remove(1) | [3, 2] | {2: 1, 3: 0} | true | i = 0, last = 3: 3 moves into slot 0, self.index[3] = 0, then pop() |
remove(2) | [3] | {3: 0} | true | i = 1 and last = 2: 2 is the last value. self.index[2] = 1, then del self.index[2]. Deleting first would write 2: 1 back |
insert(2) | [3, 2] | {3: 0, 2: 1} | true | With a stale 2: 1 left in the map, this would return false |
remove(3) | [2] | {2: 0} | true | i = 0, last = 2: 2 moves into slot 0 |
getRandom() | [2] | {2: 0} | 2 | random.choice([2]): the only value |
| 1 | A random pick where every value is equally likely needs the values packed in a list with no gaps, and a list only deletes its last slot in O(1): so fill a removed value's slot with the last value. |
| 2 | Keep this true: `self.values` holds each value once with no gaps, and `self.index[v]` is the slot of `v`. Every `remove` has to leave both true. |
| 3 | `insert`: return `False` if `val in self.index`, else record `self.index[val] = len(self.values)` and append. `remove`: `i = self.index[val]`, `last = self.values[-1]`, `self.values[i] = last`, fix the map, `pop()`. `getRandom`: `random.choice(self.values)`. |
| 4 | The trap: write `self.index[last] = i` before `del self.index[val]`. When `val` is the last value, `last == val`, and the other order puts `val` back in the map. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash set inserts and removes in O(1), but it can't hand back a uniformly random member: it has no positions to pick from. A list can: random.choice(self.values) picks each slot 0 .. n - 1 with the same chance. But a list only removes its last slot in O(1); removing from the middle shifts everything after it. Insert Delete GetRandom keeps both: the list for the random pick, and a map self.index from each value to its slot. To remove val, don't close the gap by shifting: move the last value into val's slot, record that value's new slot in self.index, and pop the end. A set has no order, so moving one value changes nothing a caller can see.
🅿️ The Analogy: A Car Park With Numbered Bays
A car park fills its bays in order from bay 0, and a notebook says which bay each car is in. To pick a car at random, draw a bay number from 0 to n - 1: every bay is full, so every car has the same chance. When the car in bay 3 leaves, you don't move every later car forward one bay: you drive the car from the last bay into bay 3, correct its line in the notebook, and the last bay is free. If the leaving car is the one in the last bay, it "moves" into its own bay, so correct the notebook first and cross the leaving car out second, or you write it straight back in.
🔑 Why It Works
After these lines self.values is still gap-free and every stored value still has exactly one slot, so random.choice stays uniform. The order of the two map writes only matters when val is the last value: then last == val, the write self.index[last] = i touches val's own entry, and del self.index[val] removes it right after. In the other order, delete then write, the write puts val back into the map.
Deleting before updating:
del self.index[val]followed byself.index[last] = iis wrong whenvalis the last value (last == val): the write putsvalback at a slot thatpop()removes, so a laterinsert(val)returnsfalse. Updateself.index[last]first, then delete.Forgetting the moved value: after
self.values[i] = last, the map must sayself.index[last] = i; otherwise it still points at the old last slot, and removinglastlater fills the wrong slot.Popping before filling the hole:
last = self.values.pop()and thenself.values[i] = lastraisesIndexErrorwhenvalwas in the last slot. Fill the hole first, pop last.Removing from the middle:
self.values.remove(val)orself.values.pop(i)shifts every later value:O(N)per call, about1010steps at these limits, and every shifted slot inself.indexgoes stale.A biased pick:
random.randint(0, len(self.values) - 2)never returns the last value, andself.values[0]is not random at all.random.choice(self.values)gives each slot, and so each value, a 1-in-n chance.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"hand back one of them at random" with "equally likely", next to insert and remove "O(1) time on average": a uniform pick needs the values packed in an array, and removing by value in O(1) needs a map from value to slot. A set has no order, which is the signal that a value may be moved: Insert Delete GetRandom, delete by moving the last value into the hole.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
self.values holds every stored value exactly once with no gaps, and self.index[v] is the slot of v in self.values. insert records self.index[val] = len(self.values) and appends; remove moves last into slot i, sets self.index[last] = i, deletes self.index[val] and pops.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap, as the debugger's first preset shows it:
remove(2)while 2 is the last value, theninsert(2); the map-write order decides whether thatinsert(2)returnstrue.removeof a value that is not stored must returnfalsebefore touching the list:i = self.index[val]on a missing key raisesKeyError.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Insert Delete GetRandom design: an array plus an index map. A pick where every value is equally likely needs the values packed in an array, so getRandom is random choice over it, and a map from each value to its slot makes insert and the lookup in remove
O(1). The hard part is deleting from the middle of the array inO(1). A set has no order, so I move the last value into the removed value's slot, record that value's new slot in the map, delete the removed value's entry and pop the end. The array stays gap-free, so every value keeps exactly one slot and the same chance. The trap is the order of the two map writes: when the removed value is itself the last one, updating first and deleting second is right, while deleting first writes it straight back into the map. Every call isO(1)on average, and the space isO(N).
Complexity & Mathematical Proof
O(1) average per call
Look at each method. insert does one map lookup (val in self.index), one map write and one append. remove does one lookup, reads self.values[-1], writes one list slot, writes one map entry, deletes one map entry and pops the end of the list: nothing shifts. getRandom draws one random index and reads one slot. Map operations are O(1) on average (hashing), and append and pop() at the end of a Python list are amortized O(1), so every call is O(1) on average and a run of Q calls costs O(Q).
O(N)
self.values and self.index each hold one entry per stored value: O(N) for N values. No recursion, and no call builds a temporary list.
T(Q) = Q · O(1) = O(Q) for Q calls (average)
Derivation Progression
O(1) average
One lookup val in self.index, one map write self.index[val] = len(self.values), one append at the end of the list.
O(1) average
One lookup, one read of self.values[-1], one slot write self.values[i] = last, one map write, one del, one pop() at the end: nothing shifts.
O(1)
random.choice(self.values) draws one index and reads one slot.
O(Q)
Constant average work per call over Q calls.
Variable Definitions
Number of values in the set, len(self.values)
Number of calls to insert, remove and getRandom (at most 2 * 105)
Memory Architecture & Bounds
O(1) No recursion
O(N): one list slot and one map entry per stored value
O(1) per call: one boolean or integer
Boundary Best / Worst Cases
per call
per call
for one call when the list grows its buffer (O(1) amortized over a run), and O(N) per call if every value collides in the hash map (why the bound is an average, not a worst case)
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "hand back one of them at random", "equally likely", "O(1) time on average" for insert and remove. A uniform pick needs the values packed in an array; deleting by value in O(1) needs a map from value to slot: Insert Delete GetRandom, an array plus an index map, deleting by moving the last value into the hole.
Up to calls, values in . A hash set alone can't pick uniformly without copying itself into a list ( per getRandom); a list alone removes in (search, then shift), up to about steps. Array plus map: average per call for memory.
If several threads share the set, remove changes two slots and two map entries, so it must run as one critical section: a getRandom between the move and the pop can see the moved value twice. Python's dict is O(1) on average, not in the worst case.
Core Algorithmic State Invariants
- Order Is the Price
Every remove moves the last value into the hole, so the list's order changes all the time. That is fine for a uniform pick, but this design cannot also answer "oldest first" or "in insertion order"; a question that needs order needs another structure.
Insert Delete GetRandom O(1) (LeetCode 380)
Build a class, RandomizedSet, that stores a set of distinct integers and can hand back one of them at random. Every operation has to take O(1) time on average.
RandomizedSet()creates an empty set.bool insert(int val)addsvalif it is missing. It returnstruewhenvalwas added andfalsewhen it was already there.bool remove(int val)deletesvalif it is there. It returnstruewhenvalwas deleted andfalsewhen it was not in the set.int getRandom()returns one of the stored values, chosen so that every value in the set at that moment is equally likely.
Worked Examples
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]][null,true,false,true,2,true,false,2]insert(1) adds 1. remove(2) returns false: 2 is not stored. insert(2) adds 2, so the set is {1, 2} and the first getRandom() may return 1 or 2, each with probability 1/2 (LeetCode shows 2). remove(1) leaves {2}, insert(2) returns false because 2 is already stored, and the last getRandom() can only return 2.⚖️Formal Constraints & Bounds
-231 <= val <= 231 - 1At most
2 * 105calls are made toinsert,removeandgetRandomaltogether.getRandomis only called when the set holds at least one value.
Core Insight
A list gives a uniform random pick but only deletes its last slot in O(1), so delete by moving the last value into the hole and recording its new slot in the map: the list stays gap-free and every value keeps exactly one slot.
Real-World Scenario & Production Applications
A load balancer that sends each request to a random healthy server, a game that picks a random live enemy, or a sampler that draws a random active user all need to add and drop members constantly and pick one at random with equal chances. A hash set can't pick at random without copying itself; a packed array with a value-to-slot map does all three in O(1).
Step-by-Step Execution Trace Table
The debugger's first preset (the trap case: remove(2) while 2 is the last value):
| Call | self.values after the call | self.index after the call | Returns | What happened |
|---|---|---|---|---|
RandomizedSet() | [] | {} | null | An empty set |
insert(1) | [1] | {1: 0} | true | 1 takes slot 0 |
insert(2) | [1, 2] | {1: 0, 2: 1} | true | 2 takes slot 1 |
insert(3) | [1, 2, 3] | {1: 0, 2: 1, 3: 2} | true | 3 takes slot 2 |
remove(1) | [3, 2] | {2: 1, 3: 0} | true | i = 0, last = 3: 3 moves into slot 0, self.index[3] = 0, then pop() |
remove(2) | [3] | {3: 0} | true | i = 1 and last = 2: 2 is the last value. self.index[2] = 1, then del self.index[2]. Deleting first would write 2: 1 back |
insert(2) | [3, 2] | {3: 0, 2: 1} | true | With a stale 2: 1 left in the map, this would return false |
remove(3) | [2] | {2: 0} | true | i = 0, last = 2: 2 moves into slot 0 |
getRandom() | [2] | {2: 0} | 2 | random.choice([2]): the only value |
| 1 | A random pick where every value is equally likely needs the values packed in a list with no gaps, and a list only deletes its last slot in O(1): so fill a removed value's slot with the last value. |
| 2 | Keep this true: `self.values` holds each value once with no gaps, and `self.index[v]` is the slot of `v`. Every `remove` has to leave both true. |
| 3 | `insert`: return `False` if `val in self.index`, else record `self.index[val] = len(self.values)` and append. `remove`: `i = self.index[val]`, `last = self.values[-1]`, `self.values[i] = last`, fix the map, `pop()`. `getRandom`: `random.choice(self.values)`. |
| 4 | The trap: write `self.index[last] = i` before `del self.index[val]`. When `val` is the last value, `last == val`, and the other order puts `val` back in the map. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash set inserts and removes in O(1), but it can't hand back a uniformly random member: it has no positions to pick from. A list can: random.choice(self.values) picks each slot 0 .. n - 1 with the same chance. But a list only removes its last slot in O(1); removing from the middle shifts everything after it. Insert Delete GetRandom keeps both: the list for the random pick, and a map self.index from each value to its slot. To remove val, don't close the gap by shifting: move the last value into val's slot, record that value's new slot in self.index, and pop the end. A set has no order, so moving one value changes nothing a caller can see.
🅿️ The Analogy: A Car Park With Numbered Bays
A car park fills its bays in order from bay 0, and a notebook says which bay each car is in. To pick a car at random, draw a bay number from 0 to n - 1: every bay is full, so every car has the same chance. When the car in bay 3 leaves, you don't move every later car forward one bay: you drive the car from the last bay into bay 3, correct its line in the notebook, and the last bay is free. If the leaving car is the one in the last bay, it "moves" into its own bay, so correct the notebook first and cross the leaving car out second, or you write it straight back in.
🔑 Why It Works
After these lines self.values is still gap-free and every stored value still has exactly one slot, so random.choice stays uniform. The order of the two map writes only matters when val is the last value: then last == val, the write self.index[last] = i touches val's own entry, and del self.index[val] removes it right after. In the other order, delete then write, the write puts val back into the map.
Deleting before updating:
del self.index[val]followed byself.index[last] = iis wrong whenvalis the last value (last == val): the write putsvalback at a slot thatpop()removes, so a laterinsert(val)returnsfalse. Updateself.index[last]first, then delete.Forgetting the moved value: after
self.values[i] = last, the map must sayself.index[last] = i; otherwise it still points at the old last slot, and removinglastlater fills the wrong slot.Popping before filling the hole:
last = self.values.pop()and thenself.values[i] = lastraisesIndexErrorwhenvalwas in the last slot. Fill the hole first, pop last.Removing from the middle:
self.values.remove(val)orself.values.pop(i)shifts every later value:O(N)per call, about1010steps at these limits, and every shifted slot inself.indexgoes stale.A biased pick:
random.randint(0, len(self.values) - 2)never returns the last value, andself.values[0]is not random at all.random.choice(self.values)gives each slot, and so each value, a 1-in-n chance.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"hand back one of them at random" with "equally likely", next to insert and remove "O(1) time on average": a uniform pick needs the values packed in an array, and removing by value in O(1) needs a map from value to slot. A set has no order, which is the signal that a value may be moved: Insert Delete GetRandom, delete by moving the last value into the hole.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
self.values holds every stored value exactly once with no gaps, and self.index[v] is the slot of v in self.values. insert records self.index[val] = len(self.values) and appends; remove moves last into slot i, sets self.index[last] = i, deletes self.index[val] and pops.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap, as the debugger's first preset shows it:
remove(2)while 2 is the last value, theninsert(2); the map-write order decides whether thatinsert(2)returnstrue.removeof a value that is not stored must returnfalsebefore touching the list:i = self.index[val]on a missing key raisesKeyError.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Insert Delete GetRandom design: an array plus an index map. A pick where every value is equally likely needs the values packed in an array, so getRandom is random choice over it, and a map from each value to its slot makes insert and the lookup in remove
O(1). The hard part is deleting from the middle of the array inO(1). A set has no order, so I move the last value into the removed value's slot, record that value's new slot in the map, delete the removed value's entry and pop the end. The array stays gap-free, so every value keeps exactly one slot and the same chance. The trap is the order of the two map writes: when the removed value is itself the last one, updating first and deleting second is right, while deleting first writes it straight back into the map. Every call isO(1)on average, and the space isO(N).
Complexity & Mathematical Proof
O(1) average per call
Look at each method. insert does one map lookup (val in self.index), one map write and one append. remove does one lookup, reads self.values[-1], writes one list slot, writes one map entry, deletes one map entry and pops the end of the list: nothing shifts. getRandom draws one random index and reads one slot. Map operations are O(1) on average (hashing), and append and pop() at the end of a Python list are amortized O(1), so every call is O(1) on average and a run of Q calls costs O(Q).
O(N)
self.values and self.index each hold one entry per stored value: O(N) for N values. No recursion, and no call builds a temporary list.
T(Q) = Q · O(1) = O(Q) for Q calls (average)
Derivation Progression
O(1) average
One lookup val in self.index, one map write self.index[val] = len(self.values), one append at the end of the list.
O(1) average
One lookup, one read of self.values[-1], one slot write self.values[i] = last, one map write, one del, one pop() at the end: nothing shifts.
O(1)
random.choice(self.values) draws one index and reads one slot.
O(Q)
Constant average work per call over Q calls.
Variable Definitions
Number of values in the set, len(self.values)
Number of calls to insert, remove and getRandom (at most 2 * 105)
Memory Architecture & Bounds
O(1) No recursion
O(N): one list slot and one map entry per stored value
O(1) per call: one boolean or integer
Boundary Best / Worst Cases
per call
per call
for one call when the list grows its buffer (O(1) amortized over a run), and O(N) per call if every value collides in the hash map (why the bound is an average, not a worst case)
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "hand back one of them at random", "equally likely", "O(1) time on average" for insert and remove. A uniform pick needs the values packed in an array; deleting by value in O(1) needs a map from value to slot: Insert Delete GetRandom, an array plus an index map, deleting by moving the last value into the hole.
Up to calls, values in . A hash set alone can't pick uniformly without copying itself into a list ( per getRandom); a list alone removes in (search, then shift), up to about steps. Array plus map: average per call for memory.
If several threads share the set, remove changes two slots and two map entries, so it must run as one critical section: a getRandom between the move and the pop can see the moved value twice. Python's dict is O(1) on average, not in the worst case.
Core Algorithmic State Invariants
- Order Is the Price
Every remove moves the last value into the hole, so the list's order changes all the time. That is fine for a uniform pick, but this design cannot also answer "oldest first" or "in insertion order"; a question that needs order needs another structure.