Minimize the Maximum Difference of Pairs

How it works

Instead of DP, we can binary search on the answer. Given a threshold t, we greedily check if we can form p pairs where each pair has difference at most t. After sorting, we scan left to right: whenever two adjacent elements have difference at most t, we pair them and skip both. This greedy approach works because pairing earlier elements never blocks better options later.

The answer lies between 0 and max - min of the sorted array, so we binary search to find the smallest threshold that allows forming p pairs.

Steps

1. Handle edge case: if p == 0, return 0.
2. Sort the array.
3. Binary search on threshold between 0 and nums[n-1] - nums[0]:
   • For each threshold mid, check if we can greedily form p pairs:
     • Scan the sorted array. If nums[i+1] - nums[i] <= mid, count a pair and skip to i+2. Otherwise move to i+1.
     • If count reaches p, the threshold is valid.
   • If valid, try a smaller threshold. Otherwise try larger.
4. Return the smallest valid threshold.

Complexity

• Time complexity: O(nlog n + nlog m)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Where n is the size of the input array and m is the maximum value in the array.

Things to watch for

Forgetting to Sort the Array First

Optimal pairs in this problem are always adjacent elements in the sorted array. If you try to form pairs without sorting, you might pair elements that are far apart in value, leading to suboptimal or incorrect results. Always sort the array before applying either the DP or binary search approach.

Incorrect Greedy Pairing in Binary Search Validation

When validating a threshold in the binary search approach, you must skip both elements when forming a pair (move to i + 2), not just one. A common bug is incrementing by 1 after forming a pair, which would allow the same element to be used in multiple pairs. Remember: if nums[i] and nums[i+1] form a valid pair, jump to index i + 2 to ensure non-overlapping pairs.

Not Handling the Edge Case When p Equals Zero

When p = 0, no pairs need to be formed, so the answer is always 0 regardless of the array contents. Some solutions fail to handle this edge case and may return incorrect results or encounter errors when attempting to form zero pairs. Always check for p == 0 at the start and return 0 immediately.

from typing import List

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        if p == 0:
            return 0

        def isValid(threshold):
            i, cnt = 0, 0
            while i < len(nums) - 1:
                if abs(nums[i] - nums[i + 1]) <= threshold:
                    cnt += 1
                    i += 2
                else:
                    i += 1
                if cnt == p:
                    return True
            return False

        nums.sort()
        l, r = 0, nums[-1] - nums[0]
        res = nums[-1] - nums[0]

        while l <= r:
            m = l + (r - l) // 2
            if isValid(m):
                res = m
                r = m - 1
            else:
                l = m + 1

        return res

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        if (p == 0) return 0;

        sort(nums.begin(), nums.end());
        int left = 0, right = nums.back() - nums[0];
        int result = right;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(nums, mid, p)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result;
    }

private:
    bool isValid(vector<int>& nums, int threshold, int p) {
        int i = 0, count = 0;
        while (i < nums.size() - 1) {
            if (abs(nums[i] - nums[i + 1]) <= threshold) {
                count++;
                i += 2;
            } else {
                i++;
            }
            if (count == p) return true;
        }
        return false;
    }
};