What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Array + Index Map (Swap-with-Last Delete)

The problem

Insert Delete GetRandom O(1) (LC 380)(opens leetcode.com)

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) adds val if it is missing. It returns true when val was added and false when it was already there.
bool remove(int val) deletes val if it is there. It returns true when val was deleted and false when 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.

Example 1

Input:["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]

Output:[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.

Insert Delete GetRandom

values list + index map ➔ move the last value into the gap ➔ O(1) delete and uniform pick

Spot it when: A set (or a multiset) must support insert, remove and a random pick where every stored value is equally likely (or weighted by its copies), each in O(1) on average.

Python

1	import random
2
3
4	class RandomizedSet:
5	"""Insert Delete GetRandom O(1): a gap-free list for the random pick, a map for each value's slot.
6	Time: O(1) average per call \| Space: O(N)
7	"""
8
9	def __init__(self) -> None:
10	self.values: list[int] = [] # Every value once, no gaps: random.choice is uniform
11	self.index: dict[int, int] = {} # value -> its slot in self.values
12
13	def insert(self, val: int) -> bool:
14	# 1. Reject A Duplicate, Else Append At The Next Free Slot:
15	# The list is always gap-free, so its current length is exactly the slot the new value will occupy.
16	if val in self.index:
17	return False
18	self.index[val] = len(self.values) # The next free slot is the end
19	self.values.append(val)
20	return True
21
22	def remove(self, val: int) -> bool:
23	# 1. Fill val's Slot With The Last Value, Then Drop The Last Slot:
24	# A set has no order, so moving the last value into the freed slot keeps the list gap-free
25	# without shifting anything; the moved value's own map entry must be fixed before val's entry is deleted.
26	if val not in self.index:
27	return False
28	i = self.index[val]
29	last = self.values[-1]
30	self.values[i] = last # Fill the hole with the last value
31	self.index[last] = i # Update the moved value's slot first...
32	del self.index[val] # ...then delete: right even when last == val
33	self.values.pop() # The last slot is now a copy: drop it in O(1)
34	return True
35
36	def getRandom(self) -> int:
37	return random.choice(self.values) # One slot per value: each has a 1-in-n chance

Invariant: self.values holds every stored value exactly once with no gaps, and self.index[v] is always the slot of v in it.

A pick where every value is equally likely needs the values packed in a list, random.choice(self.values), and a list can only drop its last slot without shifting the rest, so remove fills the hole with the last value instead of shifting: self.values[i] = last, then self.values.pop(). A set has no order, so moving one value changes nothing a caller can see, and self.index finds i with one lookup; the list stays gap-free, so every value keeps exactly one slot and the same 1-in-n chance. The trap is the order of the two map writes: self.index[last] = i must come before del self.index[val]. When val is itself the last value, last == val, and deleting first writes val straight back into the map at a slot that pop() removes, so a later insert(val) returns False.

See it run

Insert Delete GetRandom: swap with the last value, ops = insert(1), insert(2), insert(3), remove(2), remove(3), insert(3)

index {}values []

The row is the list values, one box per slot, numbered from 0. The readouts show the dictionary index.

new the slot that insert just filled
slot i the slot of the value being removed
last the last slot, which holds the value that moves
i is last the value to remove is already in the last slot

The set is empty. values has no values, and index has no entries.

1 / 16

Gotchas1 of 3

The trap
Gotcha 1: Deleting self.index[val] before writing self.index[last]
Mistake
```
del self.index[val]
self.index[last] = i
```
Fix
```
self.index[last] = i
del self.index[val]
```
What happens: When val is the last value, last == val. Deleting first removes val, then self.index[last] = i writes it back. pop() removes the slot, but the map still says that val is present. A later insert(val) then returns False.
Example: insert(1), remove(1), then insert(1)
Mistake: returns FalseFix: returns True
Gotcha 2: Popping the last slot before filling the hole
Mistake
```
self.values.pop()
self.values[i] = last
self.index[last] = i
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: When val is the only value, pop() leaves an empty list. self.values[i] = last then writes to slot 0, which no longer exists. So the call raises IndexError. Filling the hole first and popping last works for every i.
Example: insert(1), then remove(1)
Mistake: raises IndexErrorFix: returns True
Gotcha 3: Removing with self.values.pop(i) instead of moving the last value
Mistake
```
self.values.pop(i)
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: pop(i) shifts every value after slot i one slot to the left. That costs O(N) time. The shifted values keep their old slots in self.index, so the map points one slot too far. A later remove of a shifted value reads the wrong slot. self.values.remove(val) has the same two problems.
Example: insert(1), insert(2), insert(3), remove(1), then remove(3)
Mistake: raises IndexErrorFix: returns True

Not this one if…

The structure must keep an order, the order of use as in LRU Cache (LC 146), so no value may be moved into another's slot. See LRU Cache

Deep Dive

Why the last value can fill the hole

getRandom must pick every stored value with equal chance. random.choice(self.values) does that when self.values holds every value once and has no gaps. Each value then owns one slot, and each slot has a 1-in-n chance.

A list can drop only its last slot in O(1). self.values.pop(i) for another i shifts every later item, which costs O(N). So remove avoids the shift. It copies the last value into slot i, and then drops the last slot.

This is allowed because a set has no order. Moving one value to another slot changes nothing a caller can see.

Trace insert(1), insert(2), insert(3). Now values is [1, 2, 3] and index is {1: 0, 2: 1, 3: 2}. remove(2) reads i = 1 and last = 3. It sets values[1] = 3, sets index[3] = 1, deletes index[2], and pops. The result is values = [1, 3] and index = {1: 0, 3: 1}.

This is why the card's invariant says that self.values holds every stored value once with no gaps, and self.index[v] is the slot of v. After each call, both facts hold again.

The order of the two map writes

remove changes two map entries: self.index[last] = i and del self.index[val]. The first must come before the second.

Look at the case where val is the last value. In the trace, after remove(2), remove(3) has i = 1 and last = 3. Here last == val. The code sets values[1] = 3, which changes nothing. Then it sets index[3] = 1, which repeats the old entry. Then it deletes index[3]. The map no longer holds 3, and pop() drops the slot. The state is values = [1] and index = {1: 0}.

Now swap the two lines. del self.index[3] runs first, and self.index[3] = 1 writes the entry back. pop() removes the slot, but the map still says that 3 is stored. A later insert(3) returns False. With the correct order, insert(3) returns True and gives values = [1, 3].

The same order also keeps the card's other case safe. When val is not the last value, the two lines touch different keys, so their order does not matter.

Cost, and why the order of values may change

insert, remove and getRandom each do a fixed number of dictionary and list-end operations. Each is O(1) on average. The space is O(N) for values and index.

The values do not keep insertion order. After remove(2), the value 3 moved from slot 2 to slot 1. The problem asks only for a random pick, so this is fine. If you need the order, this card does not fit.

A check of the pick: in a run of 30,000 calls on values = [4, 5, 6], each value came up about 10,000 times. A skewed result would mean that a value owns two slots or that a slot is empty.

Duplicates: slots as a set

Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) allows the same value many times, and a pick must follow the number of copies. The list then holds one slot per copy.

index[val] becomes the set of slots that hold val. remove takes any slot i from that set, copies last into slot i, moves the slot number of last from the end to i, and pops. Add i to the set of last first, and then discard the old last slot number. The order matters again when i is the last slot.

insert returns True only when the set for the value was empty before the call.

60-Second Pitch

"A uniform pick needs the values in a packed list, and O(1) delete needs the position of a value. So I keep values as a list with no gaps and index as a map from value to slot. insert appends and records the slot. remove reads the slot i of the value, copies the last value into slot i, fixes the map entry of that moved value, deletes the entry of the removed value, and pops the last slot. I write the moved value's entry before the deletion, because the removed value can be the last one. Each call is O(1) on average, and the space is O(N)."

Common Questions

What is the time and space complexity?: insert, remove and getRandom are O(1) on average. The word average is used because dictionary operations are O(1) on average. The space is O(N) for values and index.
Why not delete with self.values.pop(i)?: pop(i) shifts every later item one slot to the left, so it costs O(N). Copying the last value into slot i and popping the end costs O(1). It changes the order of the values, which a set does not need.
Why does getRandom give equal chances?: random.choice picks one slot with equal chance from len(self.values) slots. Each stored value owns exactly one slot, so each value has a 1-in-n chance. The invariant of no gaps and no repeated values is what makes this true.
How does the design change when duplicates are allowed?: Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) keeps one slot per copy, so a pick follows the copy counts. index[val] becomes a set of slots. remove takes any slot from the set, then moves the last value's slot number to i. insert returns True when the set was empty before.
Why is the order of the two map writes important?: When the removed value is the last value, last == val. If del self.index[val] runs first, then self.index[last] = i writes the value back. The map then keeps a value that is no longer stored. Writing self.index[last] = i first, and deleting second, leaves the right state in both cases.

SWE Reasoning

Spot it

A collection needs insert, remove and a uniform random pick, each in O(1).
Order does not matter to the caller.
A list gives O(1) pick, and a map gives O(1) lookup, but neither does both.
Deleting from the middle of a list would cost O(N).
The statement says "each element must have the same probability" or "proportional to the number of copies".

The invariant, step by step

insert(val) returns False if val is in self.index. Otherwise it writes self.index[val] = len(self.values) and appends val. The new value takes the next free slot.
remove(val) returns False if val is not in self.index. Otherwise it reads i = self.index[val] and last = self.values[-1].
It writes self.values[i] = last. Slot i now holds last, and the last slot holds a second copy of it.
It writes self.index[last] = i, and then runs del self.index[val]. The map now matches the list, except for the extra last slot.
self.values.pop() drops the extra last slot in O(1). Every stored value owns exactly one slot again, and there are no gaps.
getRandom returns random.choice(self.values). With one slot per value, each value has a 1-in-n chance.

Traps

Deleting before writing. del self.index[val] before self.index[last] = i writes val back when last == val. A later insert(val) returns False.
Popping before filling the hole. When val is the only value, pop() empties the list, and self.values[i] = last raises IndexError.
Using self.values.pop(i). It keeps the order but costs O(N), because later items shift.
Forgetting the map write for the moved value. index[last] still names the old last slot. A later remove(last) then reads a slot that does not exist or holds another value.
Picking from the map. random.choice(list(self.index)) builds a list on each call, which costs O(N).
Skipping the duplicate check in insert. The same value then owns two slots, and its pick chance is doubled.

Practice

Canonical LeetCode:Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Array + Index Map (Swap-with-Last Delete)

The problem

Insert Delete GetRandom O(1) (LC 380)(opens leetcode.com)

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) adds val if it is missing. It returns true when val was added and false when it was already there.
bool remove(int val) deletes val if it is there. It returns true when val was deleted and false when 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.

Example 1

Input:["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]

Output:[null,true,false,true,2,true,false,2]

Insert Delete GetRandom

values list + index map ➔ move the last value into the gap ➔ O(1) delete and uniform pick

Spot it when: A set (or a multiset) must support insert, remove and a random pick where every stored value is equally likely (or weighted by its copies), each in O(1) on average.

Insert Delete GetRandom

Python

1	import random
2
3
4	class RandomizedSet:
5	"""Insert Delete GetRandom O(1): a gap-free list for the random pick, a map for each value's slot.
6	Time: O(1) average per call \| Space: O(N)
7	"""
8
9	def __init__(self) -> None:
10	self.values: list[int] = [] # Every value once, no gaps: random.choice is uniform
11	self.index: dict[int, int] = {} # value -> its slot in self.values
12
13	def insert(self, val: int) -> bool:
14	# 1. Reject A Duplicate, Else Append At The Next Free Slot:
15	# The list is always gap-free, so its current length is exactly the slot the new value will occupy.
16	if val in self.index:
17	return False
18	self.index[val] = len(self.values) # The next free slot is the end
19	self.values.append(val)
20	return True
21
22	def remove(self, val: int) -> bool:
23	# 1. Fill val's Slot With The Last Value, Then Drop The Last Slot:
24	# A set has no order, so moving the last value into the freed slot keeps the list gap-free
25	# without shifting anything; the moved value's own map entry must be fixed before val's entry is deleted.
26	if val not in self.index:
27	return False
28	i = self.index[val]
29	last = self.values[-1]
30	self.values[i] = last # Fill the hole with the last value
31	self.index[last] = i # Update the moved value's slot first...
32	del self.index[val] # ...then delete: right even when last == val
33	self.values.pop() # The last slot is now a copy: drop it in O(1)
34	return True
35
36	def getRandom(self) -> int:
37	return random.choice(self.values) # One slot per value: each has a 1-in-n chance

Invariant: self.values holds every stored value exactly once with no gaps, and self.index[v] is always the slot of v in it.

See it run

Insert Delete GetRandom: swap with the last value, ops = insert(1), insert(2), insert(3), remove(2), remove(3), insert(3)

index {}values []

The row is the list values, one box per slot, numbered from 0. The readouts show the dictionary index.

new the slot that insert just filled
slot i the slot of the value being removed
last the last slot, which holds the value that moves
i is last the value to remove is already in the last slot

The set is empty. values has no values, and index has no entries.

1 / 16

Gotchas1 of 3

The trap
Gotcha 1: Deleting self.index[val] before writing self.index[last]
Mistake
```
del self.index[val]
self.index[last] = i
```
Fix
```
self.index[last] = i
del self.index[val]
```
What happens: When val is the last value, last == val. Deleting first removes val, then self.index[last] = i writes it back. pop() removes the slot, but the map still says that val is present. A later insert(val) then returns False.
Example: insert(1), remove(1), then insert(1)
Mistake: returns FalseFix: returns True
Gotcha 2: Popping the last slot before filling the hole
Mistake
```
self.values.pop()
self.values[i] = last
self.index[last] = i
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: When val is the only value, pop() leaves an empty list. self.values[i] = last then writes to slot 0, which no longer exists. So the call raises IndexError. Filling the hole first and popping last works for every i.
Example: insert(1), then remove(1)
Mistake: raises IndexErrorFix: returns True
Gotcha 3: Removing with self.values.pop(i) instead of moving the last value
Mistake
```
self.values.pop(i)
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: pop(i) shifts every value after slot i one slot to the left. That costs O(N) time. The shifted values keep their old slots in self.index, so the map points one slot too far. A later remove of a shifted value reads the wrong slot. self.values.remove(val) has the same two problems.
Example: insert(1), insert(2), insert(3), remove(1), then remove(3)
Mistake: raises IndexErrorFix: returns True

Not this one if…

The structure must keep an order, the order of use as in LRU Cache (LC 146), so no value may be moved into another's slot. See LRU Cache

Deep Dive

Why the last value can fill the hole

This is allowed because a set has no order. Moving one value to another slot changes nothing a caller can see.

This is why the card's invariant says that self.values holds every stored value once with no gaps, and self.index[v] is the slot of v. After each call, both facts hold again.

The order of the two map writes

remove changes two map entries: self.index[last] = i and del self.index[val]. The first must come before the second.

The same order also keeps the card's other case safe. When val is not the last value, the two lines touch different keys, so their order does not matter.

Cost, and why the order of values may change

insert, remove and getRandom each do a fixed number of dictionary and list-end operations. Each is O(1) on average. The space is O(N) for values and index.

A check of the pick: in a run of 30,000 calls on values = [4, 5, 6], each value came up about 10,000 times. A skewed result would mean that a value owns two slots or that a slot is empty.

Duplicates: slots as a set

Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) allows the same value many times, and a pick must follow the number of copies. The list then holds one slot per copy.

insert returns True only when the set for the value was empty before the call.

60-Second Pitch

Common Questions

What is the time and space complexity?: insert, remove and getRandom are O(1) on average. The word average is used because dictionary operations are O(1) on average. The space is O(N) for values and index.
Why not delete with self.values.pop(i)?: pop(i) shifts every later item one slot to the left, so it costs O(N). Copying the last value into slot i and popping the end costs O(1). It changes the order of the values, which a set does not need.
Why does getRandom give equal chances?: random.choice picks one slot with equal chance from len(self.values) slots. Each stored value owns exactly one slot, so each value has a 1-in-n chance. The invariant of no gaps and no repeated values is what makes this true.
How does the design change when duplicates are allowed?: Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) keeps one slot per copy, so a pick follows the copy counts. index[val] becomes a set of slots. remove takes any slot from the set, then moves the last value's slot number to i. insert returns True when the set was empty before.
Why is the order of the two map writes important?: When the removed value is the last value, last == val. If del self.index[val] runs first, then self.index[last] = i writes the value back. The map then keeps a value that is no longer stored. Writing self.index[last] = i first, and deleting second, leaves the right state in both cases.

SWE Reasoning

Spot it

A collection needs insert, remove and a uniform random pick, each in O(1).
Order does not matter to the caller.
A list gives O(1) pick, and a map gives O(1) lookup, but neither does both.
Deleting from the middle of a list would cost O(N).
The statement says "each element must have the same probability" or "proportional to the number of copies".

The invariant, step by step

insert(val) returns False if val is in self.index. Otherwise it writes self.index[val] = len(self.values) and appends val. The new value takes the next free slot.
remove(val) returns False if val is not in self.index. Otherwise it reads i = self.index[val] and last = self.values[-1].
It writes self.values[i] = last. Slot i now holds last, and the last slot holds a second copy of it.
It writes self.index[last] = i, and then runs del self.index[val]. The map now matches the list, except for the extra last slot.
self.values.pop() drops the extra last slot in O(1). Every stored value owns exactly one slot again, and there are no gaps.
getRandom returns random.choice(self.values). With one slot per value, each value has a 1-in-n chance.

Traps

Deleting before writing. del self.index[val] before self.index[last] = i writes val back when last == val. A later insert(val) returns False.
Popping before filling the hole. When val is the only value, pop() empties the list, and self.values[i] = last raises IndexError.
Using self.values.pop(i). It keeps the order but costs O(N), because later items shift.
Forgetting the map write for the moved value. index[last] still names the old last slot. A later remove(last) then reads a slot that does not exist or holds another value.
Picking from the map. random.choice(list(self.index)) builds a list on each call, which costs O(N).
Skipping the duplicate check in insert. The same value then owns two slots, and its pick chance is doubled.

Practice

Canonical LeetCode:Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Array + Index Map (Swap-with-Last Delete)

The problem

Insert Delete GetRandom O(1) (LC 380)(opens leetcode.com)

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) adds val if it is missing. It returns true when val was added and false when it was already there.
bool remove(int val) deletes val if it is there. It returns true when val was deleted and false when 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.

Example 1

Input:["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]

Output:[null,true,false,true,2,true,false,2]

Insert Delete GetRandom

values list + index map ➔ move the last value into the gap ➔ O(1) delete and uniform pick

Spot it when: A set (or a multiset) must support insert, remove and a random pick where every stored value is equally likely (or weighted by its copies), each in O(1) on average.

Insert Delete GetRandom

Python

1	import random
2
3
4	class RandomizedSet:
5	"""Insert Delete GetRandom O(1): a gap-free list for the random pick, a map for each value's slot.
6	Time: O(1) average per call \| Space: O(N)
7	"""
8
9	def __init__(self) -> None:
10	self.values: list[int] = [] # Every value once, no gaps: random.choice is uniform
11	self.index: dict[int, int] = {} # value -> its slot in self.values
12
13	def insert(self, val: int) -> bool:
14	# 1. Reject A Duplicate, Else Append At The Next Free Slot:
15	# The list is always gap-free, so its current length is exactly the slot the new value will occupy.
16	if val in self.index:
17	return False
18	self.index[val] = len(self.values) # The next free slot is the end
19	self.values.append(val)
20	return True
21
22	def remove(self, val: int) -> bool:
23	# 1. Fill val's Slot With The Last Value, Then Drop The Last Slot:
24	# A set has no order, so moving the last value into the freed slot keeps the list gap-free
25	# without shifting anything; the moved value's own map entry must be fixed before val's entry is deleted.
26	if val not in self.index:
27	return False
28	i = self.index[val]
29	last = self.values[-1]
30	self.values[i] = last # Fill the hole with the last value
31	self.index[last] = i # Update the moved value's slot first...
32	del self.index[val] # ...then delete: right even when last == val
33	self.values.pop() # The last slot is now a copy: drop it in O(1)
34	return True
35
36	def getRandom(self) -> int:
37	return random.choice(self.values) # One slot per value: each has a 1-in-n chance

Invariant: self.values holds every stored value exactly once with no gaps, and self.index[v] is always the slot of v in it.

See it run

Insert Delete GetRandom: swap with the last value, ops = insert(1), insert(2), insert(3), remove(2), remove(3), insert(3)

index {}values []

The row is the list values, one box per slot, numbered from 0. The readouts show the dictionary index.

new the slot that insert just filled
slot i the slot of the value being removed
last the last slot, which holds the value that moves
i is last the value to remove is already in the last slot

The set is empty. values has no values, and index has no entries.

1 / 16

Gotchas1 of 3

The trap
Gotcha 1: Deleting self.index[val] before writing self.index[last]
Mistake
```
del self.index[val]
self.index[last] = i
```
Fix
```
self.index[last] = i
del self.index[val]
```
What happens: When val is the last value, last == val. Deleting first removes val, then self.index[last] = i writes it back. pop() removes the slot, but the map still says that val is present. A later insert(val) then returns False.
Example: insert(1), remove(1), then insert(1)
Mistake: returns FalseFix: returns True
Gotcha 2: Popping the last slot before filling the hole
Mistake
```
self.values.pop()
self.values[i] = last
self.index[last] = i
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: When val is the only value, pop() leaves an empty list. self.values[i] = last then writes to slot 0, which no longer exists. So the call raises IndexError. Filling the hole first and popping last works for every i.
Example: insert(1), then remove(1)
Mistake: raises IndexErrorFix: returns True
Gotcha 3: Removing with self.values.pop(i) instead of moving the last value
Mistake
```
self.values.pop(i)
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: pop(i) shifts every value after slot i one slot to the left. That costs O(N) time. The shifted values keep their old slots in self.index, so the map points one slot too far. A later remove of a shifted value reads the wrong slot. self.values.remove(val) has the same two problems.
Example: insert(1), insert(2), insert(3), remove(1), then remove(3)
Mistake: raises IndexErrorFix: returns True

Not this one if…

The structure must keep an order, the order of use as in LRU Cache (LC 146), so no value may be moved into another's slot. See LRU Cache

Deep Dive

Why the last value can fill the hole

This is allowed because a set has no order. Moving one value to another slot changes nothing a caller can see.

This is why the card's invariant says that self.values holds every stored value once with no gaps, and self.index[v] is the slot of v. After each call, both facts hold again.

The order of the two map writes

remove changes two map entries: self.index[last] = i and del self.index[val]. The first must come before the second.

The same order also keeps the card's other case safe. When val is not the last value, the two lines touch different keys, so their order does not matter.

Cost, and why the order of values may change

insert, remove and getRandom each do a fixed number of dictionary and list-end operations. Each is O(1) on average. The space is O(N) for values and index.

A check of the pick: in a run of 30,000 calls on values = [4, 5, 6], each value came up about 10,000 times. A skewed result would mean that a value owns two slots or that a slot is empty.

Duplicates: slots as a set

Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) allows the same value many times, and a pick must follow the number of copies. The list then holds one slot per copy.

insert returns True only when the set for the value was empty before the call.

60-Second Pitch

Common Questions

What is the time and space complexity?: insert, remove and getRandom are O(1) on average. The word average is used because dictionary operations are O(1) on average. The space is O(N) for values and index.
Why not delete with self.values.pop(i)?: pop(i) shifts every later item one slot to the left, so it costs O(N). Copying the last value into slot i and popping the end costs O(1). It changes the order of the values, which a set does not need.
Why does getRandom give equal chances?: random.choice picks one slot with equal chance from len(self.values) slots. Each stored value owns exactly one slot, so each value has a 1-in-n chance. The invariant of no gaps and no repeated values is what makes this true.
How does the design change when duplicates are allowed?: Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) keeps one slot per copy, so a pick follows the copy counts. index[val] becomes a set of slots. remove takes any slot from the set, then moves the last value's slot number to i. insert returns True when the set was empty before.
Why is the order of the two map writes important?: When the removed value is the last value, last == val. If del self.index[val] runs first, then self.index[last] = i writes the value back. The map then keeps a value that is no longer stored. Writing self.index[last] = i first, and deleting second, leaves the right state in both cases.

SWE Reasoning

Spot it

A collection needs insert, remove and a uniform random pick, each in O(1).
Order does not matter to the caller.
A list gives O(1) pick, and a map gives O(1) lookup, but neither does both.
Deleting from the middle of a list would cost O(N).
The statement says "each element must have the same probability" or "proportional to the number of copies".

The invariant, step by step

insert(val) returns False if val is in self.index. Otherwise it writes self.index[val] = len(self.values) and appends val. The new value takes the next free slot.
remove(val) returns False if val is not in self.index. Otherwise it reads i = self.index[val] and last = self.values[-1].
It writes self.values[i] = last. Slot i now holds last, and the last slot holds a second copy of it.
It writes self.index[last] = i, and then runs del self.index[val]. The map now matches the list, except for the extra last slot.
self.values.pop() drops the extra last slot in O(1). Every stored value owns exactly one slot again, and there are no gaps.
getRandom returns random.choice(self.values). With one slot per value, each value has a 1-in-n chance.

Traps

Deleting before writing. del self.index[val] before self.index[last] = i writes val back when last == val. A later insert(val) returns False.
Popping before filling the hole. When val is the only value, pop() empties the list, and self.values[i] = last raises IndexError.
Using self.values.pop(i). It keeps the order but costs O(N), because later items shift.
Forgetting the map write for the moved value. index[last] still names the old last slot. A later remove(last) then reads a slot that does not exist or holds another value.
Picking from the map. random.choice(list(self.index)) builds a list on each call, which costs O(N).
Skipping the duplicate check in insert. The same value then owns two slots, and its pick chance is doubled.

Practice

Canonical LeetCode:Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P2MediumMental model~4 min speedrun

Array + Index Map (Swap-with-Last Delete)

The problem

Insert Delete GetRandom O(1) (LC 380)(opens leetcode.com)

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) adds val if it is missing. It returns true when val was added and false when it was already there.
bool remove(int val) deletes val if it is there. It returns true when val was deleted and false when 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.

Example 1

Input:["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]

Output:[null,true,false,true,2,true,false,2]

Insert Delete GetRandom

values list + index map ➔ move the last value into the gap ➔ O(1) delete and uniform pick

Spot it when: A set (or a multiset) must support insert, remove and a random pick where every stored value is equally likely (or weighted by its copies), each in O(1) on average.

Insert Delete GetRandom

Python

1	import random
2
3
4	class RandomizedSet:
5	"""Insert Delete GetRandom O(1): a gap-free list for the random pick, a map for each value's slot.
6	Time: O(1) average per call \| Space: O(N)
7	"""
8
9	def __init__(self) -> None:
10	self.values: list[int] = [] # Every value once, no gaps: random.choice is uniform
11	self.index: dict[int, int] = {} # value -> its slot in self.values
12
13	def insert(self, val: int) -> bool:
14	# 1. Reject A Duplicate, Else Append At The Next Free Slot:
15	# The list is always gap-free, so its current length is exactly the slot the new value will occupy.
16	if val in self.index:
17	return False
18	self.index[val] = len(self.values) # The next free slot is the end
19	self.values.append(val)
20	return True
21
22	def remove(self, val: int) -> bool:
23	# 1. Fill val's Slot With The Last Value, Then Drop The Last Slot:
24	# A set has no order, so moving the last value into the freed slot keeps the list gap-free
25	# without shifting anything; the moved value's own map entry must be fixed before val's entry is deleted.
26	if val not in self.index:
27	return False
28	i = self.index[val]
29	last = self.values[-1]
30	self.values[i] = last # Fill the hole with the last value
31	self.index[last] = i # Update the moved value's slot first...
32	del self.index[val] # ...then delete: right even when last == val
33	self.values.pop() # The last slot is now a copy: drop it in O(1)
34	return True
35
36	def getRandom(self) -> int:
37	return random.choice(self.values) # One slot per value: each has a 1-in-n chance

Invariant: self.values holds every stored value exactly once with no gaps, and self.index[v] is always the slot of v in it.

See it run

Insert Delete GetRandom: swap with the last value, ops = insert(1), insert(2), insert(3), remove(2), remove(3), insert(3)

index {}values []

The row is the list values, one box per slot, numbered from 0. The readouts show the dictionary index.

new the slot that insert just filled
slot i the slot of the value being removed
last the last slot, which holds the value that moves
i is last the value to remove is already in the last slot

The set is empty. values has no values, and index has no entries.

1 / 16

Gotchas1 of 3

The trap
Gotcha 1: Deleting self.index[val] before writing self.index[last]
Mistake
```
del self.index[val]
self.index[last] = i
```
Fix
```
self.index[last] = i
del self.index[val]
```
What happens: When val is the last value, last == val. Deleting first removes val, then self.index[last] = i writes it back. pop() removes the slot, but the map still says that val is present. A later insert(val) then returns False.
Example: insert(1), remove(1), then insert(1)
Mistake: returns FalseFix: returns True
Gotcha 2: Popping the last slot before filling the hole
Mistake
```
self.values.pop()
self.values[i] = last
self.index[last] = i
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: When val is the only value, pop() leaves an empty list. self.values[i] = last then writes to slot 0, which no longer exists. So the call raises IndexError. Filling the hole first and popping last works for every i.
Example: insert(1), then remove(1)
Mistake: raises IndexErrorFix: returns True
Gotcha 3: Removing with self.values.pop(i) instead of moving the last value
Mistake
```
self.values.pop(i)
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: pop(i) shifts every value after slot i one slot to the left. That costs O(N) time. The shifted values keep their old slots in self.index, so the map points one slot too far. A later remove of a shifted value reads the wrong slot. self.values.remove(val) has the same two problems.
Example: insert(1), insert(2), insert(3), remove(1), then remove(3)
Mistake: raises IndexErrorFix: returns True

Not this one if…

The structure must keep an order, the order of use as in LRU Cache (LC 146), so no value may be moved into another's slot. See LRU Cache

Deep Dive

Why the last value can fill the hole

This is allowed because a set has no order. Moving one value to another slot changes nothing a caller can see.

This is why the card's invariant says that self.values holds every stored value once with no gaps, and self.index[v] is the slot of v. After each call, both facts hold again.

The order of the two map writes

remove changes two map entries: self.index[last] = i and del self.index[val]. The first must come before the second.

The same order also keeps the card's other case safe. When val is not the last value, the two lines touch different keys, so their order does not matter.

Cost, and why the order of values may change

insert, remove and getRandom each do a fixed number of dictionary and list-end operations. Each is O(1) on average. The space is O(N) for values and index.

A check of the pick: in a run of 30,000 calls on values = [4, 5, 6], each value came up about 10,000 times. A skewed result would mean that a value owns two slots or that a slot is empty.

Duplicates: slots as a set

Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) allows the same value many times, and a pick must follow the number of copies. The list then holds one slot per copy.

insert returns True only when the set for the value was empty before the call.

60-Second Pitch

Common Questions

What is the time and space complexity?: insert, remove and getRandom are O(1) on average. The word average is used because dictionary operations are O(1) on average. The space is O(N) for values and index.
Why not delete with self.values.pop(i)?: pop(i) shifts every later item one slot to the left, so it costs O(N). Copying the last value into slot i and popping the end costs O(1). It changes the order of the values, which a set does not need.
Why does getRandom give equal chances?: random.choice picks one slot with equal chance from len(self.values) slots. Each stored value owns exactly one slot, so each value has a 1-in-n chance. The invariant of no gaps and no repeated values is what makes this true.
How does the design change when duplicates are allowed?: Insert Delete GetRandom O(1) - Duplicates allowed (LC 381) keeps one slot per copy, so a pick follows the copy counts. index[val] becomes a set of slots. remove takes any slot from the set, then moves the last value's slot number to i. insert returns True when the set was empty before.
Why is the order of the two map writes important?: When the removed value is the last value, last == val. If del self.index[val] runs first, then self.index[last] = i writes the value back. The map then keeps a value that is no longer stored. Writing self.index[last] = i first, and deleting second, leaves the right state in both cases.

SWE Reasoning

Spot it

A collection needs insert, remove and a uniform random pick, each in O(1).
Order does not matter to the caller.
A list gives O(1) pick, and a map gives O(1) lookup, but neither does both.
Deleting from the middle of a list would cost O(N).
The statement says "each element must have the same probability" or "proportional to the number of copies".

The invariant, step by step

insert(val) returns False if val is in self.index. Otherwise it writes self.index[val] = len(self.values) and appends val. The new value takes the next free slot.
remove(val) returns False if val is not in self.index. Otherwise it reads i = self.index[val] and last = self.values[-1].
It writes self.values[i] = last. Slot i now holds last, and the last slot holds a second copy of it.
It writes self.index[last] = i, and then runs del self.index[val]. The map now matches the list, except for the extra last slot.
self.values.pop() drops the extra last slot in O(1). Every stored value owns exactly one slot again, and there are no gaps.
getRandom returns random.choice(self.values). With one slot per value, each value has a 1-in-n chance.

Traps

Deleting before writing. del self.index[val] before self.index[last] = i writes val back when last == val. A later insert(val) returns False.
Popping before filling the hole. When val is the only value, pop() empties the list, and self.values[i] = last raises IndexError.
Using self.values.pop(i). It keeps the order but costs O(N), because later items shift.
Forgetting the map write for the moved value. index[last] still names the old last slot. A later remove(last) then reads a slot that does not exist or holds another value.
Picking from the map. random.choice(list(self.index)) builds a list on each call, which costs O(N).
Skipping the duplicate check in insert. The same value then owns two slots, and its pick chance is doubled.

Practice

Canonical LeetCode:Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)