Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
First Missing Positive
Bookmark
Hash Set
Sorting
Cyclic Sort
Input
Example 1
Example 2
Example 3
Custom
nums
=
[3, 4, -1, 1]
set holds
0
values in [1, 4]
probe upward from 1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
bank every value, then walk upward until one is missing
set holds
0
values in [1, 4]
probe upward from 1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
bank every value, then walk upward until one is missing
set holds
1
value in [1, 4]
probe upward from 1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
set.add(
3
)
set holds
2
values in [1, 4]
probe upward from 1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
set.add(
4
)
set holds
2
values in [1, 4]
probe upward from 1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
set.add(
-1
)
set holds
3
values in [1, 4]
probe upward from 1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
set.add(
1
)
set holds
3
values in [1, 4]
probe upward from 1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
every value banked, now probe from
1
set holds
3
values in [1, 4]
trying
1
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
1 in set
true
try 2
set holds
3
values in [1, 4]
trying
2
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
2 in set
false
this is the gap
set holds
3
values in [1, 4]
trying
2
3
4
-1
1
0
1
2
3
is it in the set?
1
2
3
4
5
first missing positive =
2
algo
master
.
io
Step:
Start: bank every value in a set, then probe 1, 2, 3 in turn
0 / 8
Input
Example 1
Example 2
Example 3
Custom
nums
=
[3, 4, -1, 1]
0 / 8
algo
master
.
io
Step:
Start: bank every value in a set, then probe 1, 2, 3 in turn
