⚡Flashcard Drill➔
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

  1. Binary search on the maximum allowed difference d: "can we form at least p pairs with difference at most d" is monotone.
  2. Sort the array. For a given d, greedily pair adjacent elements whenever their difference is at most d, skipping two positions on a match.
  3. 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.
  4. 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 - 1 when 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 initial lo = 0 gives directly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems