Minimize the Maximum Difference of Pairs

To solve this problem, let’s first understand the key insight:

If we sort the array nums, then to minimize the maximum difference among p pairs, we should try pairing the numbers as closely as possible in the sorted array.

To determine if a difference diff is achievable or not, we can iterate through the sorted array. For each number, we can try pairing it with the nearest number that is within diff distance.

Given this insight, we can employ a binary search on the diff to find the smallest possible value of diff for which p pairs can be formed. The search space for diff ranges from 0 to nums[-1] - nums[0].

Here’s the approach:

  1. Sort the array and keep the original indices using enumerate.
  2. Define a function canFormPairs that checks if p pairs can be formed for a given diff.
  3. Use binary search to find the smallest diff for which canFormPairs returns True.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        # Sort the nums with original indices
        nums = sorted(enumerate(nums), key=lambda x: x[1])

        # Check if it's possible to form p pairs with maximum difference <= diff
        def canFormPairs(diff):
            used = set()
            pairs = 0
            for i, (idx, num) in enumerate(nums):
                if i not in used:
                    # Find the closest number within diff
                    j = i + 1
                    while j < len(nums) and nums[j][1] - num <= diff:
                        if j not in used:
                            pairs += 1
                            used.add(i)
                            used.add(j)
                            break
                        j += 1
            return pairs >= p

        # Binary search to find the minimum diff
        l, r = 0, nums[-1][1] - nums[0][1]
        ans = r
        while l <= r:
            mid = (l + r) // 2
            if canFormPairs(mid):
                ans = mid
                r = mid - 1
            else:
                l = mid + 1

        return ans

This solution has a time complexity of O(n log n) due to sorting and binary search.