Minimize the Maximum of Pairs
Problem Description
Given a 0-indexed integer array nums and integer p, select p pairs of indices (i, j) such that i < j. The score of a pair is |nums[i] - nums[j]|.
Return the minimum possible value of the maximum score among all p pairs.
Pattern: Binary search on the answer. Binary search on maxDiff: check if we can greedily form p pairs where each adjacent (after sorting) pair has difference ≤ maxDiff.
Key insight: Sort nums. Optimal pairs always come from adjacent elements after sorting.
Example 1:
Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: Pairs (1,1) and (2,3) — max score = 1.
Example 2:
Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: Pair (2,2) — score = 0.
Example Test Cases
Example 1
Input: [[10,1,2,7,1,3],2]
Expected: 1
Example 2
Input: [[4,2,1,2],1]
Expected: 0
Example 3
Input: [[3,4,2,3,2,1,2],3]
Expected: 1
Run your code to see the results