Minimize the Maximum Difference of Pairs

Medium
825.

Minimize the Maximum Difference of Pairs

Minimize the Maximum Difference of Pairs is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Arcesium interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} p
 * @return {number}
 */
var minimizeMax = function(nums, p) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize the Maximum Difference of Pairs — Solution

Minimize the Maximum Difference of Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimize the Maximum Difference of Pairs is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Arcesium interviews.

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

Hints for Minimize the Maximum Difference of Pairs

  1. Hint 1

    If a maximum cost d is achievable, so is any larger one — the feasibility is monotone.

  2. Hint 2

    Sort first: in an optimal pairing, every pair is two adjacent elements of the sorted array.

  3. Hint 3

    For a candidate d, greedily pair adjacent elements whose gap fits, skipping one when it does not.

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

Java

private static boolean canPair(int[] a, int p, int d) {
    int cnt = 0, i = 0;
    while (i + 1 < a.length) {
        if (a[i + 1] - a[i] <= d) {
            cnt++;
            i += 2;
        } else {
            i++;
        }
    }
    return cnt >= p;
}

public static int minimizeMax(int[] nums, int p) {
    if (p == 0) return 0;
    int[] a = nums.clone();
    Arrays.sort(a);
    int lo = 0, hi = a[a.length - 1] - a[0];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPair(a, p, mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

C++

static bool canPair(vector<int>& a, int p, int d) {
    int cnt = 0, i = 0;
    while (i + 1 < (int) a.size()) {
        if (a[i + 1] - a[i] <= d) {
            cnt++;
            i += 2;
        } else {
            i++;
        }
    }
    return cnt >= p;
}

int minimizeMax(vector<int>& nums, int p) {
    if (p == 0) return 0;
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int lo = 0, hi = a.back() - a.front();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPair(a, p, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms