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! 🛠️
Top comments (7)
Great
Thanks
Love how you broke this down, really helps demystify the greedy + binary search approach.
Have you run into any tricky edge cases where it doesn't work as expected?
It was easy, it worked perfectly at first go
Good One
Thanks Anna
Some comments may only be visible to logged-in visitors. Sign in to view all comments. Some comments have been hidden by the post's author - find out more