Choose exactly p disjoint pairs from an array so that the largest absolute difference among the chosen pairs is as small as possible.
You are given an integer array and an integer . Form exactly disjoint pairs using elements from the array, where each element can belong to at most one pair. The cost of a pair is the absolute difference of its two values.
Your task is to minimize the maximum pair cost among the pairs.
In other words, among all ways to select non-overlapping pairs, find the smallest possible value of the largest difference inside any chosen pair.
Input Format
- An integer array
nums. - An integer
p, the number of disjoint pairs to form.
Output Format
- Return the minimum possible value of the maximum absolute difference among the chosen pairs.
Constraints
- The array contains at least
2pelements. - Elements are integers.
- Pairing must be disjoint; each index may be used at most once.
- The objective is to minimize the worst pair difference.
Example 1
Input
nums = [10,1,2,7,1,3], p = 2
Output
1
Explanation
After sorting, one optimal pairing is (1,1) and (2,3). The pair differences are 0 and 1, so the maximum is 1, which is minimal.
Example 2
Input
nums = [4,2,1,2], p = 1
Output
0
Explanation
Sort the array as [1,2,2,4]. Pair the two 2s to get difference 0.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.