Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Maximum Gap
Bookmark
Input
Standard
Large Gap
Custom
nums
=
[3, 6, 9, 1]
INPUT ARRAY
3
6
9
1
find the largest gap between sorted neighbors
INPUT ARRAY
3
6
9
1
find the largest gap between sorted neighbors
INPUT ARRAY
min =
3
max =
6
i
3
6
9
1
min =
3
, max =
6
INPUT ARRAY
min =
1
max =
9
i
3
6
9
1
min =
1
, max =
9
INPUT ARRAY
NUMBER LINE (buckets by value range)
B0
B1
B2
B3
B4
1
9
3
6
9
1
a gap inside a bucket is at most bucketSize — the answer must span buckets
INPUT ARRAY
i
NUMBER LINE (buckets by value range)
B0
B1
B2
B3
B4
1
9
3
6
9
1
place into
B2
→ [
6, 6
]
INPUT ARRAY
i
NUMBER LINE (buckets by value range)
B0
B1
B2
B3
B4
1
9
3
6
9
1
place into
B4
→ [
9, 9
]
INPUT ARRAY
NUMBER LINE (buckets by value range)
B0
B1
B2
B3
B4
1
9
3
6
9
1
scan buckets — measure each gap prevMax → next bucket min
INPUT ARRAY
NUMBER LINE (buckets by value range)
B0
B1
B2
B3
B4
1
9
2
3
6
9
1
gap =
3
−
1
=
2
, maxGap =
2
INPUT ARRAY
NUMBER LINE (buckets by value range)
B0
B1
B2
B3
B4
1
9
3
3
6
9
1
B
3
is empty → skip
INPUT ARRAY
NUMBER LINE (buckets by value range)
B0
B1
B2
B3
B4
1
9
3
3
6
9
1
maximum gap = 3
algo
master
.
io
Step:
Find the maximum gap between sorted neighbors using bucket sort
0 / 17
Input
Standard
Large Gap
Custom
nums
=
[3, 6, 9, 1]
0 / 17
algo
master
.
io
Step:
Find the maximum gap between sorted neighbors using bucket sort
