Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Insert Delete GetRandom O(1)
Bookmark
Input
Example 1
Example 2
Example 3
Custom
operations
=
[RandomizedSet, insert, insert, remove, insert, getRandom, remove]
,
values
=
[null, 1, 2, 1, 2, null, 2]
RandomizedSet()
insert(1)
=
?
insert(2)
=
?
remove(1)
=
?
insert(2)
=
?
getRandom()
=
?
remove(2)
=
?
array
(empty)
map
(empty)
array for O(1) random access · map for O(1) lookup
RandomizedSet()
insert(1)
=
?
insert(2)
=
?
remove(1)
=
?
insert(2)
=
?
getRandom()
=
?
remove(2)
=
?
array
(empty)
map
(empty)
array for O(1) random access · map for O(1) lookup
RandomizedSet()
insert(1)
=
?
insert(2)
=
?
remove(1)
=
?
insert(2)
=
?
getRandom()
=
?
remove(2)
=
?
array
1
0
map
1
→
0
array.push(
1
) at index 0
RandomizedSet()
insert(1)
=
true
insert(2)
=
?
remove(1)
=
?
insert(2)
=
?
getRandom()
=
?
remove(2)
=
?
array
1
0
map
1
→
0
map.has(2)
false
new value
RandomizedSet()
insert(1)
=
true
insert(2)
=
true
remove(1)
=
?
insert(2)
=
?
getRandom()
=
?
remove(2)
=
?
array
1
0
2
1
map
1
→
0
2
→
1
return
true
RandomizedSet()
insert(1)
=
true
insert(2)
=
true
remove(1)
=
?
insert(2)
=
?
getRandom()
=
?
remove(2)
=
?
array
1
1
2
0
map
1
→
0
2
→
1
swap
1
⇄ last
2
keeps the array dense
RandomizedSet()
insert(1)
=
true
insert(2)
=
true
remove(1)
=
?
insert(2)
=
?
getRandom()
=
?
remove(2)
=
?
array
2
0
map
1
→
✕
2
→
0
delete map[
1
]
RandomizedSet()
insert(1)
=
true
insert(2)
=
true
remove(1)
=
true
insert(2)
=
false
getRandom()
=
?
remove(2)
=
?
array
2
0
map
2
→
0
2
already present
→ false
RandomizedSet()
insert(1)
=
true
insert(2)
=
true
remove(1)
=
true
insert(2)
=
false
getRandom()
=
2
remove(2)
=
?
random → 0
array
2
0
map
2
→
0
return
2
RandomizedSet()
insert(1)
=
true
insert(2)
=
true
remove(1)
=
true
insert(2)
=
false
getRandom()
=
2
remove(2)
=
?
array
(empty)
map
2
→
0
array.pop()
→ 2
O(1), no shifting
RandomizedSet()
insert(1)
=
true
insert(2)
=
true
remove(1)
=
true
insert(2)
=
false
getRandom()
=
2
remove(2)
=
true
array
(empty)
map
(empty)
All operations processed
algo
master
.
io
Step:
RandomizedSet: a dynamic array for O(1) random access + a value→index map for O(1) lookup.
0 / 31
Input
Example 1
Example 2
Example 3
Custom
operations
=
[RandomizedSet, insert, insert, remove, insert, getRandom, remove]
,
values
=
[null, 1, 2, 1, 2, null, 2]
0 / 31
algo
master
.
io
Step:
RandomizedSet: a dynamic array for O(1) random access + a value→index map for O(1) lookup.
