<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> and an integer <code>p</code>. Find <code>p</code> pairs of indices of <code>nums</code> such that the <strong>maximum</strong> difference amongst all the pairs is <strong>minimized</strong>. Also, ensure no index appears more than once amongst the <code>p</code> pairs.</p>

<p>Note that for a pair of elements at the index <code>i</code> and <code>j</code>, the difference of this pair is <code>|nums[i] - nums[j]|</code>, where <code>|x|</code> represents the <strong>absolute</strong> <strong>value</strong> of <code>x</code>.</p>

<p>Return <em>the <strong>minimum</strong> <strong>maximum</strong> difference among all </em><code>p</code> <em>pairs.</em> We define the maximum of an empty set to be zero.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,1,2,7,1,3], p = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5. 
The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,2,1,2], p = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> Let the indices 1 and 3 form a pair. The difference of that pair is |2 - 2| = 0, which is the minimum we can attain.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= p &lt;= (nums.length)/2</code></li>
</ul>

"""
we can brute force o(n^2) each pair

10, 1       9
10, 2       8   
10, 7       3
10, 1       9
10, 3       7
1,2         1
1,7         6
1,1         0
1,3         2
2,7         5
2,1         1
2,3         1
7,1         6
7,3         4
1,3         2

we can go thru each one, o(n^2) and find the max() of the min p pairs
max(0, 1) = 1

what if we sort
1,1,2,3,7,10
min differences will be with it's neighbors

then we can just pair them up
1,1
1,2
2,3
3,7 
7,10

and find minimum two
essentially o(n)? but how do we keep track of minimum p pairs?
heap? of size p, 
but this wouldn't work since we can't re-use numbers
"""
class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        nums.sort()
        
        l, r = 0, 10**9
        ans = 10**9

        def is_valid(m):
            """ Given m, return True if there are p pairs with diff <= m, else return False
            """
            # print('testing', m)
            pairs = 0
            i = 0
            while i < len(nums) - 1:
                if abs(nums[i] - nums[i+1]) <= m:
                    pairs += 1
                    i += 2
                else:
                    i += 1
            # print('val', pairs >= p)
            return pairs >= p

        while l < r:
            m = l + (r - l) // 2
            if is_valid(m):
                r = m
            else:
                l = m + 1
        return l
        
983