Problem Description

You have an integer array nums (0-indexed) and an integer p. Your task is to find p pairs of indices from nums such that:

1. The maximum difference among all the pairs is as small as possible (minimized)
2. No index can be used more than once across all pairs

For any pair of elements at indices i and j, the difference is calculated as |nums[i] - nums[j]| (absolute value).

Your goal is to return the minimum possible value of the maximum difference among all p pairs. If no pairs are selected (empty set), the maximum is defined as zero.

Example to clarify:

• If you have nums = [1, 3, 5, 7] and need to form p = 2 pairs
• You might choose pairs like (index 0, index 1) with difference |1-3| = 2 and (index 2, index 3) with difference |5-7| = 2
• The maximum difference among these pairs is 2
• The goal is to find the selection of pairs that makes this maximum as small as possible

The challenge is to strategically select which indices to pair together to achieve the smallest possible maximum difference while ensuring you can form exactly p valid pairs without reusing any index.

Intuition

The key insight is recognizing that this problem has a monotonic property: if we can form p pairs where the maximum difference is at most x, then we can definitely form p pairs where the maximum difference is at most x+1 (or any value larger than x). This is because any valid solution for x is also valid for x+1.

This monotonic property immediately suggests binary search on the answer. We can search for the smallest value of maximum difference that allows us to form at least p pairs.

But how do we check if a given maximum difference diff is achievable? Here's where the second key insight comes in:

After sorting the array, adjacent elements will have the smallest differences. If we want to minimize the maximum difference, we should prefer pairing elements that are close to each other in the sorted array.

The greedy strategy emerges naturally: traverse the sorted array from left to right. At each position i, if nums[i+1] - nums[i] <= diff, we should immediately form this pair. Why? Because:

1. This pair has an acceptable difference (≤ diff)
2. Using nums[i] now with its closest neighbor nums[i+1] is optimal - any other pairing for nums[i] would likely result in a larger difference
3. Once we use indices i and i+1, we skip to i+2 to avoid reusing indices

If the difference exceeds our threshold, we skip nums[i] and move to the next element. This greedy approach maximizes the number of pairs we can form for any given maximum difference threshold.

The combination of binary search (to find the minimum maximum difference) and greedy validation (to check if a difference is achievable) gives us an efficient solution.

Learn more about Greedy, Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

The solution combines binary search with a greedy validation function:

Step 1: Sort the array

nums.sort()

Sorting ensures that elements with smaller differences are adjacent, which is crucial for our greedy approach.

Step 2: Define the search range The minimum possible maximum difference is 0 (when pairs have identical elements), and the maximum possible is nums[-1] - nums[0] (the difference between the largest and smallest elements). So our search range is [0, nums[-1] - nums[0]].

Step 3: Binary search with validation We use bisect_left to find the smallest value where our validation function returns True:

bisect_left(range(nums[-1] - nums[0] + 1), True, key=check)

Step 4: Greedy validation function The check(diff) function determines if we can form at least p pairs with maximum difference ≤ diff:

def check(diff: int) -> bool:
    cnt = i = 0
    while i < len(nums) - 1:
        if nums[i + 1] - nums[i] <= diff:
            cnt += 1      # Found a valid pair
            i += 2        # Skip both indices (they're used)
        else:
            i += 1        # Skip only current index
    return cnt >= p

How the greedy algorithm works:

• Start from the beginning of the sorted array
• At position i, check if nums[i+1] - nums[i] <= diff
• If yes: form the pair (i, i+1), increment pair count, and jump to i+2
• If no: skip i and try from i+1
• After traversing, check if we formed at least p pairs

Why this greedy approach is optimal: For any given maximum difference threshold, pairing adjacent elements in the sorted array when possible maximizes the total number of pairs we can form. This is because:

1. Adjacent elements have the smallest differences
2. If we skip pairing nums[i] with nums[i+1] when their difference is acceptable, any future pairing of nums[i] will likely have a larger difference
3. This strategy leaves more flexibility for forming pairs with the remaining elements

The binary search finds the minimum value of diff where check(diff) returns True, giving us the minimum possible maximum difference.

Example Walkthrough

Let's walk through the solution with nums = [10, 1, 2, 7, 1, 3] and p = 2.

Step 1: Sort the array After sorting: nums = [1, 1, 2, 3, 7, 10]

Step 2: Set up binary search range

• Minimum possible difference: 0
• Maximum possible difference: 10 - 1 = 9
• Search range: [0, 9]

Step 3: Binary search process

Let's trace through the binary search:

First iteration: mid = 4

• Check if we can form 2 pairs with max difference ≤ 4
• Greedy validation:
  • i=0: nums[1] - nums[0] = 1 - 1 = 0 ≤ 4 ✓ Form pair (0,1), cnt=1, move to i=2
  • i=2: nums[3] - nums[2] = 3 - 2 = 1 ≤ 4 ✓ Form pair (2,3), cnt=2, move to i=4
  • i=4: nums[5] - nums[4] = 10 - 7 = 3 ≤ 4 ✓ Form pair (4,5), cnt=3
• Result: cnt=3 ≥ 2, so diff=4 works. Search lower half: [0, 3]

Second iteration: mid = 1

• Check if we can form 2 pairs with max difference ≤ 1
• Greedy validation:
  • i=0: nums[1] - nums[0] = 1 - 1 = 0 ≤ 1 ✓ Form pair (0,1), cnt=1, move to i=2
  • i=2: nums[3] - nums[2] = 3 - 2 = 1 ≤ 1 ✓ Form pair (2,3), cnt=2, move to i=4
  • i=4: nums[5] - nums[4] = 10 - 7 = 3 > 1 ✗ Skip i=4, move to i=5
  • i=5: Out of bounds
• Result: cnt=2 ≥ 2, so diff=1 works. Search lower half: [0, 0]

Third iteration: mid = 0

• Check if we can form 2 pairs with max difference ≤ 0
• Greedy validation:
  • i=0: nums[1] - nums[0] = 1 - 1 = 0 ≤ 0 ✓ Form pair (0,1), cnt=1, move to i=2
  • i=2: nums[3] - nums[2] = 3 - 2 = 1 > 0 ✗ Skip i=2, move to i=3
  • i=3: nums[4] - nums[3] = 7 - 3 = 4 > 0 ✗ Skip i=3, move to i=4
  • i=4: nums[5] - nums[4] = 10 - 7 = 3 > 0 ✗ Skip i=4, move to i=5
  • i=5: Out of bounds
• Result: cnt=1 < 2, so diff=0 doesn't work

Binary search conclusion: The minimum value where we can form at least 2 pairs is 1.

Verification: With max difference = 1, we can form pairs:

• Pair 1: indices (0,1) with values (1,1), difference = 0
• Pair 2: indices (2,3) with values (2,3), difference = 1

The maximum difference among all pairs is 1, which is the minimum possible for this input.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × (log n + log m))

The time complexity consists of two main parts:

• Sorting the array takes O(n log n) time, where n is the length of nums
• Binary search using bisect_left performs O(log m) iterations, where m = nums[-1] - nums[0] (the difference between maximum and minimum values)
• For each binary search iteration, the check function is called, which takes O(n) time to iterate through the array
• Therefore, the binary search portion contributes O(n × log m) time
• Total time complexity: O(n log n) + O(n × log m) = O(n × (log n + log m))

Space Complexity: O(1)

The space complexity is constant because:

• The sorting is done in-place (Python's sort modifies the original list)
• The check function only uses a constant amount of extra space for variables cnt and i
• The binary search doesn't create any additional data structures proportional to the input size
• Only a fixed number of variables are used regardless of input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Edge Case When p = 0

When p = 0, no pairs need to be formed, so the maximum difference should be 0. The current implementation handles this correctly since the validation function will immediately return True for any threshold when p = 0, and binary search will return the minimum value (0).

2. Incorrect Greedy Strategy: Trying to Form "Optimal" Pairs Instead of Maximum Pairs

A common mistake is trying to be too clever with the validation function. For example:

# WRONG: Trying to find the "best" pairs within threshold
def check(diff):
    used = set()
    pairs = []
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[j] - nums[i] <= diff and i not in used and j not in used:
                pairs.append((i, j))
                used.add(i)
                used.add(j)
    return len(pairs) >= p

This approach is both inefficient (O(n²)) and incorrect. The greedy approach of always taking adjacent valid pairs in the sorted array is both optimal and efficient.

3. Off-by-One Error in Binary Search Range

A subtle pitfall is setting the wrong upper bound for binary search:

# WRONG: May miss the actual answer
right = nums[-1] - nums[0] - 1  # Off by one

# CORRECT: Include the full range
right = nums[-1] - nums[0]

The maximum possible difference could be exactly nums[-1] - nums[0] if we need to pair the smallest and largest elements.

4. Not Sorting the Array First

The greedy approach only works on a sorted array. Without sorting:

# WRONG: Forgetting to sort
def minimizeMax(self, nums, p):
    # nums.sort()  # Missing this crucial step!
    def check(diff):
        # ... greedy logic won't work correctly

The algorithm relies on adjacent elements having small differences, which is only guaranteed after sorting.

5. Using Wrong Comparison in Validation Function

Be careful with the comparison operator:

# WRONG: Using < instead of <=
if nums[i + 1] - nums[i] < diff:  # Should be <=

# CORRECT: 
if nums[i + 1] - nums[i] <= diff:

Using < would incorrectly reject valid pairs where the difference equals the threshold.

6. Misunderstanding the Problem: Trying to Form Exactly p Pairs

The validation function should check if we can form at least p pairs, not exactly p pairs:

# WRONG: Checking for exact count
return cnt == p

# CORRECT: Checking for at least p pairs
return cnt >= p

We want to know if a given threshold is feasible, and having more valid pairs than needed still means the threshold works.