Solution Approach

The solution combines binary search with a greedy validation function:

Step 1: Sort the array Sorting ensures that elements with smaller differences are adjacent, which is crucial for our greedy approach.

Step 2: Binary Search Template We use the first_true_index template to find the minimum maximum difference:

• Initialize left = 0 and right = nums[-1] - nums[0]
• Track the answer with first_true_index = -1
• Use while left <= right loop structure
• When feasible(mid) returns True, update first_true_index = mid and search left with right = mid - 1
• When feasible(mid) returns False, search right with left = mid + 1

Step 3: Feasible Function (Greedy Validation) The feasible(max_diff) function determines if we can form at least p pairs with maximum difference ≤ max_diff:

def feasible(max_diff: int) -> bool:
    pair_count = index = 0
    while index < len(nums) - 1:
        if nums[index + 1] - nums[index] <= max_diff:
            pair_count += 1
            index += 2
        else:
            index += 1
    return pair_count >= p

Why the Greedy Approach Works: For any given maximum difference threshold, pairing adjacent elements in the sorted array when possible maximizes the total number of pairs. Adjacent elements have the smallest differences, and skipping a valid pair only hurts future pairing options.

Edge Case Handling: When p = 0, no pairs are needed, so the answer is 0. The template handles this gracefully since feasible(0) returns True when p = 0.

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.

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. Using Wrong Binary Search Template

Incorrect:

while left < right:
    mid = (left + right) // 2
    if feasible(mid):
        right = mid
    else:
        left = mid + 1
return left

Correct (template-compliant):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index if first_true_index != -1 else 0

2. Not Sorting the Array First

The greedy approach only works on a sorted array. Without sorting, adjacent elements won't have minimal differences, and the pairing strategy fails.

3. Using Wrong Comparison in Validation Function

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

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

4. Checking for Exactly p Pairs Instead of At Least p Pairs

# WRONG:
return pair_count == p

# CORRECT:
return pair_count >= p

Having more valid pairs than needed still means the threshold works.

5. Edge Case When p = 0

When p = 0, no pairs are needed, so the answer is 0. The template handles this since feasible(0) returns True when p = 0.