Minimize the Maximum Difference of Pairs

medium array binary search greedy

Problem

Form p pairs from a positive integer array nums (each index used at most once). Minimize the maximum absolute difference among the chosen pairs.

Inputnums = [10, 1, 2, 7, 1, 3], p = 2

Output1

Sort → [1,1,2,3,7,10]; pair (1,1) and (2,3): max diff = 1.

nums (comma-separated)

def minimize_max(nums, p):
    nums.sort()
    def can(d):
        cnt, i = 0, 0
        while i < len(nums) - 1:
            if nums[i + 1] - nums[i] <= d:
                cnt += 1
                i += 2
            else:
                i += 1
        return cnt >= p
    lo, hi = 0, nums[-1] - nums[0]
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid): hi = mid
        else: lo = mid + 1
    return lo

function minimizeMax(nums, p) {
  nums.sort((a, b) => a - b);
  const can = (d) => {
    let cnt = 0, i = 0;
    while (i < nums.length - 1) {
      if (nums[i + 1] - nums[i] <= d) { cnt++; i += 2; }
      else i++;
    }
    return cnt >= p;
  };
  let lo = 0, hi = nums[nums.length - 1] - nums[0];
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (can(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

class Solution {
    public int minimizeMax(int[] nums, int p) {
        java.util.Arrays.sort(nums);
        int lo = 0, hi = nums[nums.length - 1] - nums[0];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canPair(nums, mid, p)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private boolean canPair(int[] nums, int d, int p) {
        int cnt = 0, i = 0;
        while (i < nums.length - 1) {
            if (nums[i + 1] - nums[i] <= d) { cnt++; i += 2; }
            else i++;
        }
        return cnt >= p;
    }
}

int minimizeMax(vector<int>& nums, int p) {
    sort(nums.begin(), nums.end());
    auto can = [&](int d) {
        int cnt = 0, i = 0;
        while (i < (int)nums.size() - 1) {
            if (nums[i + 1] - nums[i] <= d) { cnt++; i += 2; }
            else i++;
        }
        return cnt >= p;
    };
    int lo = 0, hi = nums.back() - nums.front();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (can(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Explanation

We need p pairs with the smallest possible maximum difference. The "can we form p pairs all within difference d?" question gets easier as d grows, so we binary-search the answer d after sorting the array.

Why sort first? After sorting, the closest values sit next to each other, so the best pairs are always adjacent. That lets a simple greedy scan in can(d) walk left to right: if nums[i+1] - nums[i] <= d, pair them and skip both (i += 2); otherwise move on (i += 1). Count how many pairs we form.

If the greedy makes at least p pairs, d works, so we shrink (hi = mid); if not, we raise (lo = mid + 1). The range starts at [0, max - min], and the loop lands on the smallest feasible d.

Example: nums = [10,1,2,7,1,3], p = 2. Sorted is [1,1,2,3,7,10]. With d = 1 we pair (1,1) and (2,3), two pairs, so the answer is 1.

The greedy is safe because skipping a fitting adjacent pair never helps; taking it leaves the rest in the best shape to keep pairing.

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