Minimize the Maximum Difference of Pairs solution and explanation
Google
9 more videos on this problem
Minimize the Maximum Difference of Pairs - Leetcode 2616 - PythonNeetCodeIO · 16:56 · 23K views
Minimize the Maximum Difference of Pairs | Intuition | META | Leetcode 2616 | codestorywithMIKcodestorywithMIK · 31:06 · 17K views
Minimize the Maximum Difference of Pairs | Leetcode 2616Techdose · 23:13 · 4K views
LeetCode 2616. Minimize the Maximum Difference of Pairs | Weekly Contest 340 | OffCampus PhodengeOffCampus Phodenge | Aman Chowdhury · 20:49 · 2K views
Leetcode 2616 Minimize the Maximum Difference of PairsJeevan Kumar - Cracckify · 10:52 · 2K views
Minimize the Maximum Difference of Pairs | 6359 | Weekly Contest 340codingMohan · 18:54 · 1K views
2616. Minimize the Maximum Difference of Pairs | Greedy | LeetcodeRapid Syntax · 16:09 · 975 views
Leetcode 2616: Minimize the Maximum Difference of PairsAlgorithms Casts · 19:12 · 818 views
2616. Minimize the Maximum Difference of Pairs (Leetcode Medium)Programming Live with Larry · 11:59 · 779 views
2616 Minimize the Maximum Difference of Pairs | Leetcode Weekly Contest 340Md Zuhair · 6:15 · 522 views
The problem
You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs.
Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x.
Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.
Example 1:
Input: nums = [10,1,2,7,1,3], p = 2 Output: 1 Explanation: The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5. The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.
Example 2:
Input: nums = [4,2,1,2], p = 1 Output: 0 Explanation: Let the indices 1 and 3 form a pair. The difference of that pair is |2 - 2| = 0, which is the minimum we can attain.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= p <= (nums.length)/2
Approach overview
Problem Overview: You are given an integer array and a number p. The task is to create p disjoint pairs such that the maximum absolute difference among those pairs is minimized. Each element can be used at most once, so the challenge is choosing pairs carefully to keep the worst difference as small as possible.
Approach 1: Sorting with Greedy Pairing (Binary Search Optimization) (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
The key idea is that once the array is sorted, close numbers naturally produce smaller differences. After sorting, use binary search on the answer — the maximum allowed difference. For a candidate difference d, greedily scan the array and pair adjacent elements whenever their difference is ≤ d. Each time a valid pair is formed, skip both indices and continue. If you can form at least p pairs, the difference d is feasible, so search for a smaller value.
This works because feasibility is monotonic: if a maximum difference d works, any larger value also works. Sorting the array ensures the greedy step always picks the smallest possible differences first, which maximizes the number of valid pairs. Binary search narrows the optimal maximum difference efficiently.
Approach 2: Priority Queue to Manage Differences (Time: O(n log n), Space: O(n))
Another strategy computes candidate pair differences and processes them using a greedy strategy backed by a priority queue. After sorting the array, push adjacent pair differences into a min-heap. Repeatedly extract the smallest difference and select the pair if neither index has been used yet. Continue until p pairs are formed.
The heap ensures the smallest differences are processed first, which tends to minimize the maximum difference among selected pairs. However, managing index conflicts and maintaining the heap introduces additional overhead compared with the binary-search feasibility check. While still valid, this approach is usually less efficient in practice.
Recommended for interviews: The sorting + binary search approach is what interviewers typically expect. It demonstrates strong understanding of monotonic search space reduction and greedy validation. A brute-force pairing idea shows initial reasoning, but the optimized solution proves you can combine binary search with a greedy feasibility check to reach an optimal O(n log n) solution.
Approach 1: Approach 1: Sorting with Greedy Pairing
The primary idea of this approach is to first sort the array so that elements which are closer in value are positioned adjacent to each other. This can help in reducing the maximum difference within selected pairs when paired greedily. Once sorted, the greedy approach looks to form pairs consecutively and calculate the differences. By doing so repetitively and minimizing the maximum difference, an optimal solution is achieved.
def minimize_max_difference(nums, p):
nums.sort()
left, right = 0, nums[-1] - nums[0]
while left < right:
mid = (left + right) // 2
count, i = 0, 1
while i < len(nums) and count < p:
if nums[i] - nums[i - 1] <= mid:
count += 1
i += 1 # Skip the next index
i += 1
if count >= p:
right = mid
else:
left = mid + 1
return left
nums = [10, 1, 2, 7, 1, 3]
p = 2
print(minimize_max_difference(nums, p))import java.util.Arrays;
public class MinMaxDifference {
public int minimizeMaxDifference(int[] nums, int p) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 1; i < nums.length && count < p; ++i) {
if (nums[i] - nums[i - 1] <= mid) {
count++;
i++; // Ensure each number is used at most once
}
}
if (count >= p) right = mid;
else left = mid + 1;
}
return left;
}
public static void main(String[] args) {
int[] nums = {10, 1, 2, 7, 1, 3};
int p = 2;
MinMaxDifference mmd = new MinMaxDifference();
System.out.println(mmd.minimizeMaxDifference(nums, p));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minimizeMaxDifference(std::vector<int>& nums, int p) {
std::sort(nums.begin(), nums.end());
int left = 0, right = nums[nums.size() - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 1; i < nums.size() && count < p; ++i) {
if (nums[i] - nums[i - 1] <= mid) {
count++;
i++; // Skip the next index to ensure each number is used at most once
}
}
if (count >= p) right = mid;
else left = mid + 1;
}
return left;
}
int main() {
std::vector<int> nums = {10, 1, 2, 7, 1, 3};
int p = 2;
std::cout << minimizeMaxDifference(nums, p) << std::endl;
return 0;
}function minimizeMaxDifference(nums, p) {
nums.sort((a, b) => a - b);
let left = 0;
let right = nums[nums.length - 1] - nums[0];
while (left < right) {
let mid = Math.floor((left + right) / 2);
let count = 0;
for (let i = 1; i < nums.length && count < p; ++i) {
if (nums[i] - nums[i - 1] <= mid) {
count++;
i++; // Skip the next index to ensure each number is used at most once
}
}
if (count >= p) right = mid;
else left = mid + 1;
}
return left;
}
let nums = [10, 1, 2, 7, 1, 3];
let p = 2;
console.log(minimizeMaxDifference(nums, p));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minimizeMaxDifference(int* nums, int numsSize, int p) {
qsort(nums, numsSize, sizeof(int), cmp);
int left = 0, right = nums[numsSize - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 1; i < numsSize && count < p; ++i) {
if (nums[i] - nums[i - 1] <= mid) {
count++;
i++; // Skip the next index to ensure each number is used at most once
}
}
if (count >= p) right = mid;
else left = mid + 1;
}
return left;
}
int main() {
int nums[] = {10, 1, 2, 7, 1, 3};
int p = 2;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minimizeMaxDifference(nums, size, p));
return 0;
}using System;
using System.Linq;
public class MinMaxDifference {
public int MinimizeMaxDifference(int[] nums, int p) {
Array.Sort(nums);
int left = 0, right = nums[nums.Length - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 1; i < nums.Length && count < p; ++i) {
if (nums[i] - nums[i - 1] <= mid) {
count++;
i++; // Ensure each number is used at most once
}
}
if (count >= p) right = mid;
else left = mid + 1;
}
return left;
}
public static void Main() {
int[] nums = {10, 1, 2, 7, 1, 3};
int p = 2;
MinMaxDifference mmd = new MinMaxDifference();
Console.WriteLine(mmd.MinimizeMaxDifference(nums, p));
}
}This Python solution uses the sort method to order the elements in the list before using a binary search through the differences to count how many valid pairs can be formed.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) auxiliary space.
Approach 2: Approach 2: Priority Queue to Manage Differences
This approach also begins by sorting the input array, but tackles the problem by employing a min-heap (priority queue). The idea is to manage the smallest differences available and decide pairs greedily based on this. The heap helps efficiently remove and manage differences, ensuring that the maximum difference in the formed pairs remains minimal.
from heapq import heappush, heappop
def minimize_max_difference(nums, p):
nums.sort()
difference_heap = []
for i in range(1, len(nums)):
heappush(difference_heap, (nums[i] - nums[i - 1], i - 1, i))
count = 0
result = 0
used = [False] * len(nums)
while count < p and difference_heap:
diff, first, second = heappop(difference_heap)
if not used[first] and not used[second]:
result = diff
used[first] = used[second] = True
count += 1
return result
nums = [10, 1, 2, 7, 1, 3]
p = 2
print(minimize_max_difference(nums, p))import java.util.PriorityQueue;
import java.util.Arrays;
public class MinMaxDifferenceHeap {
public int minimizeMaxDifference(int[] nums, int p) {
Arrays.sort(nums);
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (int i = 1; i < nums.length; i++) {
heap.offer(new int[] { nums[i] - nums[i - 1], i - 1, i });
}
boolean[] used = new boolean[nums.length];
int count = 0, result = 0;
while (count < p && !heap.isEmpty()) {
int[] top = heap.poll();
if (!used[top[1]] && !used[top[2]]) {
result = top[0];
used[top[1]] = true;
used[top[2]] = true;
count++;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {10, 1, 2, 7, 1, 3};
int p = 2;
MinMaxDifferenceHeap mmd = new MinMaxDifferenceHeap();
System.out.println(mmd.minimizeMaxDifference(nums, p));
}
}In this Python code, we sort the array and then push all possible adjacent differences into a min-heap. We then pop the smallest difference and form pairs while keeping track of used elements until the required number of pairs is formed.
Time Complexity: O(n log n) due to the heap operations.
Space Complexity: O(n) for holding the differences.
Approach 3: Binary Search + Greedy
We notice that the maximum difference has monotonicity: if a maximum difference x is feasible, then x-1 is also feasible. Therefore, we can use binary search to find the minimal feasible maximum difference.
First, sort the array nums. Then, for a given maximum difference x, check whether it is possible to form p pairs of indices such that the maximum difference in each pair does not exceed x. If possible, we can try a smaller x; otherwise, we need to increase x.
To check whether p such pairs exist with maximum difference at most x, we can use a greedy approach. Traverse the sorted array nums from left to right. For the current index i, if the difference between nums[i+1] and nums[i] does not exceed x, we can form a pair with i and i+1, increment the pair count cnt, and increase i by 2. Otherwise, increase i by 1. After traversing, if cnt geq p, then such p pairs exist; otherwise, they do not.
The time complexity is O(n times (log n + log m)), where n is the length of nums and m is the difference between the maximum and minimum values in nums. The space complexity is O(1).
function minimizeMax(nums: number[], p: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let l = 0,
r = nums[n - 1] - nums[0] + 1;
const check = (diff: number): boolean => {
let cnt = 0;
for (let i = 0; i < n - 1; ++i) {
if (nums[i + 1] - nums[i] <= diff) {
++cnt;
++i;
}
}
return cnt >= p;
};
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}func minimizeMax(nums []int, p int) int {
sort.Ints(nums)
n := len(nums)
r := nums[n-1] - nums[0] + 1
return sort.Search(r, func(diff int) bool {
cnt := 0
for i := 0; i < n-1; i++ {
if nums[i+1]-nums[i] <= diff {
cnt++
i++
}
}
return cnt >= p
})
}class Solution {
func minimizeMax(_ nums: [Int], _ p: Int) -> Int {
var nums = nums.sorted()
let n = nums.count
var l = 0
var r = nums[n - 1] - nums[0] + 1
func check(_ diff: Int) -> Bool {
var cnt = 0
var i = 0
while i < n - 1 {
if nums[i + 1] - nums[i] <= diff {
cnt += 1
i += 2
} else {
i += 1
}
}
return cnt >= p
}
while l < r {
let mid = (l + r) >> 1
if check(mid) {
r = mid
} else {
l = mid + 1
}
}
return l
}
}impl Solution {
pub fn minimize_max(mut nums: Vec<i32>, p: i32) -> i32 {
nums.sort();
let n = nums.len();
let (mut l, mut r) = (0, nums[n - 1] - nums[0] + 1);
let check = |diff: i32| -> bool {
let mut cnt = 0;
let mut i = 0;
while i < n - 1 {
if nums[i + 1] - nums[i] <= diff {
cnt += 1;
i += 2;
} else {
i += 1;
}
}
cnt >= p
};
while l < r {
let mid = (l + r) / 2;
if check(mid) {
r = mid;
} else {
l = mid + 1;
}
}
l
}
}class Solution {
/**
* @param Integer[] $nums
* @param Integer $p
* @return Integer
*/
function minimizeMax($nums, $p) {
sort($nums);
$n = count($nums);
$l = 0;
$r = $nums[$n - 1] - $nums[0] + 1;
$check = function ($diff) use ($nums, $n, $p) {
$cnt = 0;
for ($i = 0; $i < $n - 1; ++$i) {
if ($nums[$i + 1] - $nums[$i] <= $diff) {
++$cnt;
++$i;
}
}
return $cnt >= $p;
};
while ($l < $r) {
$mid = intdiv($l + $r, 2);
if ($check($mid)) {
$r = $mid;
} else {
$l = $mid + 1;
}
}
return $l;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting with Greedy Pairing | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Priority Queue to Manage Differences | Time Complexity: O(n log n) due to the heap operations. |
| Binary Search + Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Greedy Pairing with Binary Search | O(n log n) | O(1) auxiliary | Best general solution; minimizes maximum difference efficiently using monotonic feasibility |
| Priority Queue on Pair Differences | O(n log n) | O(n) | Useful when exploring smallest pair differences first or demonstrating heap-based greedy selection |
Frequently asked questions
Is Minimize the Maximum Difference of Pairs easy or hard?
The problem is rated Medium on LeetCode. The main challenge is recognizing that the answer can be searched using binary search and validated with a greedy pairing strategy after sorting.
Minimize the Maximum Difference of Pairs Python or Java solution
Typical implementations sort the array and apply binary search on the difference range. The greedy feasibility check counts how many pairs can be formed without overlapping indices. This pattern translates directly to Python, Java, C++, C#, and JavaScript.
How to solve Minimize the Maximum Difference of Pairs in O(n log n)?
First sort the array so nearby numbers have small differences. Then binary search the maximum allowed difference. For each candidate value, iterate through the array and greedily pair adjacent elements if their difference is within the limit, counting how many pairs can be formed.
What is the best approach for Minimize the Maximum Difference of Pairs?
The most efficient approach sorts the array and then uses binary search on the maximum allowed pair difference. For each candidate difference, a greedy scan forms pairs whenever adjacent numbers differ by at most that value. This method runs in O(n log n) time due to sorting and binary search iterations.
What data structure is used in Minimize the Maximum Difference of Pairs?
The optimal solution primarily uses arrays with sorting and a greedy scan. Binary search is applied over the range of possible differences. An alternative implementation may use a priority queue (min-heap) to process pair differences in increasing order.
What is the time complexity of Minimize the Maximum Difference of Pairs?
The optimal solution runs in O(n log n) time. Sorting the array takes O(n log n), and each binary search step performs a linear greedy scan to count valid pairs. Space complexity is O(1) auxiliary aside from sorting.
Is Minimize the Maximum Difference of Pairs asked at Google or Amazon interviews?
Problems combining binary search with greedy validation appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this question test your ability to recognize monotonic search spaces and design feasibility checks efficiently.