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.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Binary Search
- Asked at: Amazon, Google, Arcesium
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1000000 <= nums[i] <= 10000000000 <= p <= nums.length / 2
Hints for Minimize the Maximum Difference of Pairs
Hint 1
If a maximum cost
dis achievable, so is any larger one — the feasibility is monotone.Hint 2
Sort first: in an optimal pairing, every pair is two adjacent elements of the sorted array.
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
- Handle
p = 0up front. - Sort
nums. can(d): scan withi; ifa[i+1] - a[i] <= d, pair them and jump two, otherwise advance one. Feasible when at leastppairs form.- Binary search the smallest feasible
dover[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 = 0must 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 loJava
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