Hello coders! 🔧
Today, let’s tackle a beautiful binary search + greedy problem from LeetCode — 2616: Minimize the Maximum Difference of Pairs. It's one of those problems that seems hard at first glance but becomes elegant with the right strategy.
Let’s decode it together. 🧩
📜 Problem Overview
Given:
- An integer array
nums - An integer
p(number of index pairs to form)
Objective:
Choose p disjoint pairs (no overlapping indices) such that the maximum absolute difference across all selected pairs is minimized.
✨ Example
Input:
nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation:
Form pairs (1,4) and (2,5):
Differences: |1 - 1| = 0, |2 - 3| = 1 → Max = 1 (minimum possible maximum).
🧠 Intuition & Strategy
This is a "minimize the maximum" problem — a perfect use case for binary search on the answer.
Key Insights:
- Sort the array to allow greedy pairing.
- Use binary search to test if a given
maxDiffallows us to create at leastppairs. - In each check, greedily form a pair with the smallest possible adjacent difference.
⚙️ C++ Code
class Solution {
public:
int minimizeMax(vector<int>& nums, int p) {
ranges::sort(nums);
int l = 0;
int r = nums.back() - nums.front();
while (l < r) {
const int m = (l + r) / 2;
if (numPairs(nums, m) >= p)
r = m;
else
l = m + 1;
}
return l;
}
private:
int numPairs(const vector<int>& nums, int maxDiff) {
int pairs = 0;
for (int i = 1; i < nums.size(); ++i)
if (nums[i] - nums[i - 1] <= maxDiff) {
++pairs;
++i;
}
return pairs;
}
};
🌐 JavaScript Version
var minimizeMax = function(nums, p) {
nums.sort((a, b) => a - b);
let left = 0;
let right = nums[nums.length - 1] - nums[0];
const countPairs = (maxDiff) => {
let pairs = 0;
for (let i = 1; i < nums.length; ++i) {
if (nums[i] - nums[i - 1] <= maxDiff) {
pairs++;
i++;
}
}
return pairs;
};
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (countPairs(mid) >= p) right = mid;
else left = mid + 1;
}
return left;
};
🐍 Python Version
def minimizeMax(nums: list[int], p: int) -> int:
nums.sort()
def count_pairs(max_diff: int) -> int:
pairs = 0
i = 1
while i < len(nums):
if nums[i] - nums[i - 1] <= max_diff:
pairs += 1
i += 2
else:
i += 1
return pairs
left, right = 0, nums[-1] - nums[0]
while left < right:
mid = (left + right) // 2
if count_pairs(mid) >= p:
right = mid
else:
left = mid + 1
return left
🧪 Test Cases
Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Input: nums = [4,2,1,2], p = 1
Output: 0
Input: nums = [1, 1000, 2000, 3000, 4000], p = 2
Output: 1000
⏱ Time & Space Complexity
Time Complexity: O(n log(maxDiff)) — where maxDiff is the difference between max and min in nums.
Space Complexity: O(1) — only a few pointers and counters used.
✅ Wrap-Up
This is a classic problem that tests your algorithmic thinking — combining binary search on answer with a greedy validation strategy. If you've never tried that before, this is a great introduction!
If you liked this breakdown, leave a ❤️ and follow for more practical algorithm guides!
Happy coding! 🛠️
Good One