Partition Array Such That Maximum Difference Is K

medium array greedy sorting

Problem

You are given an integer array nums and an integer k. Split every element into groups so that, within any group, the difference between the largest and smallest value is at most k. Return the minimum number of groups you need. Each element must belong to exactly one group, and the order of elements does not matter.

Inputnums = [3, 6, 1, 2, 5], k = 2

Output2

Sort → [1, 2, 3, 5, 6]. Group {1, 2, 3} (max−min = 2) and group {5, 6} (max−min = 1). Two groups suffice.

nums (comma-separated)

def partition_array(nums, k):
    nums.sort()
    groups = 0
    start = None
    for x in nums:
        if start is None or x - start > k:
            groups += 1
            start = x
    return groups

function partitionArray(nums, k) {
  nums.sort((a, b) => a - b);
  let groups = 0;
  let start = null;
  for (const x of nums) {
    if (start === null || x - start > k) {
      groups += 1;
      start = x;
    }
  }
  return groups;
}

class Solution {
    public int partitionArray(int[] nums, int k) {
        Arrays.sort(nums);
        int groups = 0;
        int start = Integer.MIN_VALUE;
        for (int x : nums) {
            if (groups == 0 || x - start > k) {
                groups += 1;
                start = x;
            }
        }
        return groups;
    }
}

int partitionArray(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int groups = 0;
    int start = 0;
    for (int x : nums) {
        if (groups == 0 || x - start > k) {
            groups += 1;
            start = x;
        }
    }
    return groups;
}

Explanation

We want the fewest groups such that inside each group the gap between the biggest and smallest value is no more than k. Since group order and element order do not matter, the first move is to sort the array. After sorting, the elements of any sensible group are contiguous — there is never a reason to skip over a value and pick it up later.

Now scan left to right and run a simple greedy rule. Keep track of start, the smallest value of the group we are currently filling. Each new element x can join that group only if x − start ≤ k. The moment x − start > k, the current group cannot stretch any further, so we close it, open a brand new group, and reset start = x.

Why is being greedy optimal? Because the array is sorted, start is the minimum of the open group, so x − start is exactly the largest difference that group would have if x joined. If that already exceeds k, no later (even larger) element could fit either, so splitting here is forced — we lose nothing by doing it as late as possible.

Example: nums = [3, 6, 1, 2, 5], k = 2 sorts to [1, 2, 3, 5, 6]. Open group 1 with start = 1: 2−1 = 1 and 3−1 = 2 both fit. At 5, 5−1 = 4 > 2, so we open group 2 with start = 5; then 6−5 = 1 fits. Two groups total.

Sorting dominates the running time; the single scan afterward is linear, so the whole thing is fast.

Time: O(n log n) Space: O(1)