You are given an integer array nums and an integer p. You need to select p pairs of indices such that no index is used in more than one pair.

The difference between a pair of elements at indices i and j is defined as $|$nums[i] $-$ nums[j]$|$.

Return the minimum possible maximum difference among all p pairs. If p is equal to $0$, return $0$.

Constraints:

• $1 \leq$ nums.length $\leq 10^5$

• $0 \leq$ nums[i] $\leq 10^9$

• $0 \leq$ p $\leq$ nums.length $/ 2$

Input: nums = [8,3,14,6,1]-List[int], p = 0-int
Output: 0-int
Explanation: Since p is 0, no pairs need to be selected, so the minimum possible maximum difference is 0.

Input: nums = [11,11,4,20,5,5]-List[int], p = 2-int
Output: 0-int
Explanation: Two pairs with equal values can be selected: (11, 11) and (5, 5). Both differences are 0, so the maximum difference is 0.

Input: nums = [0,100,3,98,6,95]-List[int], p = 3-int
Output: 89-int
Explanation: The pairs (0, 3), (6, 95), and (98, 100) have differences 3, 89, and 2, respectively. Thus, the minimum possible maximum difference is 89.

Input: nums = [1000000000,0,999999999,2,500000000]-List[int], p = 1-int
Output: 1-int
Explanation: Pairing 999999999 with 1000000000 gives a difference of 1, which is the smallest possible difference for one pair.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.