Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Partition Array Such That Maximum Difference Is K
Bookmark
Brute Force
Greedy + Sorting
Input
Standard
Example 2
Larger
Custom
nums
=
[3, 6, 1, 2, 5]
,
k
=
2
3
6
1
2
5
0
1
2
3
4
sort, then try 1 group, 2 groups, … each with range ≤ 2
3
6
1
2
5
0
1
2
3
4
sort, then try 1 group, 2 groups, … each with range ≤ 2
1
2
3
5
6
0
1
2
3
4
sorted — now try groupings
trying 1 group
grouping #1
1
2
3
5
6
0
1
2
3
4
Δ5 ✗
does splitting into 1 group keep every range ≤ 2?
trying 2 groups
grouping #2
1
2
3
5
6
0
1
2
3
4
Δ0 ✓
Δ4 ✗
does splitting into 2 groups keep every range ≤ 2?
trying 2 groups
a group exceeds k ✗
grouping #2
1
2
3
5
6
0
1
2
3
4
Δ0 ✓
Δ4 ✗
no, try another split
trying 2 groups
grouping #3
1
2
3
5
6
0
1
2
3
4
Δ1 ✓
Δ3 ✗
does splitting into 2 groups keep every range ≤ 2?
trying 2 groups
a group exceeds k ✗
grouping #3
1
2
3
5
6
0
1
2
3
4
Δ1 ✓
Δ3 ✗
no, try another split
trying 2 groups
all groups fit ✓
grouping #4
1
2
3
5
6
0
1
2
3
4
Δ2 ✓
Δ1 ✓
yes! 2 groups is enough
min groups = 2
1
2
3
5
6
0
1
2
3
4
Δ2 ✓
Δ1 ✓
answer =
2 groups
min groups = 2
1
2
3
5
6
0
1
2
3
4
Δ2 ✓
Δ1 ✓
answer =
2 groups
algo
master
.
io
Step:
Sort, then try every grouping. Keep each group's max − min ≤ 2.
0 / 11
Input
Standard
Example 2
Larger
Custom
nums
=
[3, 6, 1, 2, 5]
,
k
=
2
0 / 11
algo
master
.
io
Step:
Sort, then try every grouping. Keep each group's max − min ≤ 2.
