Get started

Minimize the Maximum Difference of Pairs — Medium Problem & Solution

Form exactly p pairs of indices from nums; no index may appear in more than one pair. The cost of a pair is the absolute difference of its values.

Problem statement

Form exactly p pairs of indices from nums; no index may appear in more than one pair. The cost of a pair is the absolute difference of its values.

Return the minimum possible value of the largest pair cost. If p is 0, the answer is 0.

Example 1

Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: Pair the two 1s and the 2 with the 3.

Example 2

Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: The two 2s cost nothing.

Example 3

Input: nums = [3,4,2,3,2,1,2], p = 3
Output: 1

Constraints

  • 1 <= nums.length <= 100000
  • 0 <= nums[i] <= 1000000000
  • 0 <= p <= nums.length / 2

How to solve Minimize the Maximum Difference of Pairs

Binary search the maximum cost. Once the array is sorted, an optimal pairing only ever joins adjacent elements, so a left-to-right greedy that takes every affordable adjacent pair maximises the number of pairs formed within a budget d.

Approach

  1. Handle p = 0 up front.
  2. Sort nums.
  3. can(d): scan with i; if a[i+1] - a[i] <= d, pair them and jump two, otherwise advance one. Feasible when at least p pairs form.
  4. Binary search the smallest feasible d over [0, max - min].

Why it works

Pairing non-adjacent sorted elements can always be rewritten to adjacent pairs without raising the maximum cost — an exchange argument on any crossing or nesting pair. Given adjacency, the greedy is optimal because taking an affordable pair as early as possible never blocks a later one that a different choice would have allowed. Raising d only admits more pairs, so can is monotone.

Complexity

  • Time — O(n log n + n log V)
  • Space — O(n)

Pitfalls

  • p = 0 must return 0 without entering the search.
  • The greedy must skip one element when a pair is unaffordable, not two.
  • The search starts at 0 — equal neighbours give a zero-cost pair.

Reference solution

Python

from typing import List

def minimizeMax(nums: List[int], p: int) -> int:
    if p == 0:
        return 0
    a = sorted(nums)

    def can(d: int) -> bool:
        cnt, i = 0, 0
        while i + 1 < len(a):
            if a[i + 1] - a[i] <= d:
                cnt += 1
                i += 2
            else:
                i += 1
        return cnt >= p

    lo, hi = 0, a[-1] - a[0]
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var minimizeMax = function(nums, p) {
    if (p === 0) return 0;
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var can = function(d) {
        var cnt = 0, i = 0;
        while (i + 1 < a.length) {
            if (a[i + 1] - a[i] <= d) { cnt++; i += 2; } else i++;
        }
        return cnt >= p;
    };
    var lo = 0, hi = a[a.length - 1] - a[0];
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (can(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue