<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>

// BY BINARY SEARCH APPROACH:

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        if(p==0) return 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int l = INT_MAX;
        int r = INT_MIN;
        for(int i=1;i<n;i++){
            int diff = abs(nums[i]-nums[i-1]);
            l = min(l, diff);
            r = max(r, diff);
        }

        while(l<r){
            int mid = (l+r)/2;
            if(isFeasible(mid,nums,p)) r = mid;
            else l = mid+1;
        }

        return l;
    }

    bool isFeasible(int maxDiff, vector<int> nums, int p){
        // cout<<"maxDiff: "<<maxDiff<<" "<<"p: "<<p<<endl;
        // for(int e : nums){
        //     cout<<e<< " ";
        // }
        // cout<<endl;
        int count = 0;
        for(int i=1;i<nums.size();i++){
            int diff = abs(nums[i]-nums[i-1]);
            if(maxDiff>= diff){
                count++;
                i++;
                if(count==p) return true;
            }
        }
        return false;
    }
};


// BY DP APPROACH: 

// class Solution {
// public:
//     int minimizeMax(vector<int>& nums, int p) {
//         int n = nums.size();

//         sort(nums.begin(), nums.end());

//         vector<vector<int>> dp(n, vector<int>(p + 1, INT_MAX));

//         for (int i = 0; i < n; i++) {
//             dp[i][0] = 0;
//         }

//         for (int i = 1; i < n; i++) {
//             for (int j = 1; j <= p; j++) {
//                 if(j*2>i+1){
//                     continue;
//                 }
//                 int notTaken = dp[i-1][j];
//                 int taken = abs(nums[i]-nums[i-1]);
//                 if(i>1) taken = max(dp[i-2][j-1], taken);

//                 dp[i][j] = min(taken, notTaken);
//             }
//         }

//         return dp[n-1][p];
//     }
// };
103900