NeetCode #280LC-2616MediumBinary Search
← Back to All Problems#280 · #2616 · Minimize the Maximum Difference of Pairs(最小化数对的最大差值)
📌 Problem Statement & Constraints
You are given a 0-indexed integer array
nums and an integer p. Find p pairs of indices such that no index appears in more than one pair, minimising the maximum difference among the pairs. Return that minimum possible maximum difference. Constraints: 1 <= nums.length <= 10^5, 0 <= nums[i] <= 10^9, 0 <= p <= nums.length / 2.💡 Core Algorithmic Approaches
- Binary search on the maximum allowed difference
d: "can we form at leastppairs with difference at mostd" is monotone. - Sort the array. For a given
d, greedily pair adjacent elements whenever their difference is at mostd, skipping two positions on a match. - The greedy is optimal for maximising the number of pairs under a difference cap, because sorting makes the best partner for each element its immediate neighbour.
- Use the upper-biased midpoint to find the smallest feasible
d.
💻 Benchmark Python3 Implementation
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
nums.sort()
def pairs_within(limit: int) -> int:
cnt = 0
i = 0
while i < len(nums) - 1:
if nums[i + 1] - nums[i] <= limit:
cnt += 1
i += 2 # both used
else:
i += 1
return cnt
lo, hi = 0, nums[-1] - nums[0]
while lo < hi:
mid = (lo + hi) // 2
if pairs_within(mid) >= p:
hi = mid # feasible -> try a smaller limit
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n + n log(max difference)): the sort plus O(log V) greedy passes.
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to sort: the greedy pairing relies on adjacent elements being the closest available.
- Using
hi = mid - 1when feasible: could skip the optimum. - Pairing non-adjacent elements greedily: after sorting, pairing adjacent elements is optimal for maximising the count.
- Handling
p == 0: the answer is 0, which the initiallo = 0gives directly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.