Partition Array Such That Maximum Difference Is K

Partition Array Such That Maximum Difference Is K

What is this problem about?

The Partition Array Such That Maximum Difference Is K problem asks you to partition the array into the minimum number of contiguous groups such that within each group, max - min ≤ k. Return the minimum number of groups. This coding problem uses a greedy approach after sorting. The array, sorting, and greedy interview pattern is demonstrated.

Why is this asked in interviews?

Amazon and Google ask this to test greedy reasoning on sorted arrays. The key insight: sort the array, then greedily extend each group as far as possible while current - group_start ≤ k. This gives the minimum number of groups.

Algorithmic pattern used

Sort + greedy sweep. Sort the array. Initialize group_start = arr[0], count = 1. Scan from left: if arr[i] - group_start > k, start a new group (group_start = arr[i], count++). Return count.

Example explanation

arr=[3,6,1,2,5], k=2. Sort: [1,2,3,5,6].

• group_start=1. Scan: 1(ok),2(ok),3(ok),5: 5-1=4>2 → new group! group_start=5. count=2.
• Scan: 5(ok),6(ok). Final count = 2.

Common mistakes candidates make

• Not sorting first (greedy only works on sorted array).
• Using arr[i] - arr[i-1] > k instead of arr[i] - group_start > k.
• Off-by-one: initialize count=1 (first group always exists).
• Not handling k=0 case (all elements must be equal in each group).

Interview preparation tip

"Minimum groups with max-min ≤ k" is a classic greedy interval partition. After sorting, the problem becomes one-dimensional: greedily extend each interval until it exceeds width k. This identical pattern appears in "minimum number of jumps," "interval scheduling," and "merge overlapping intervals." Sorting + greedy sweep is the universal approach for range-constrained grouping.