# 2616. Minimize the Maximum Difference of Pairs

## Problem Statement

<br>

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

Note that for a pair of elements at the index `i` and `j`, the difference of this pair is `|nums[i] - nums[j]|`, where `|x|` represents the **absolute** **value** of `x`.

Return *the **minimum*** ***maximum** difference among all* `p` *pairs.* We define the maximum of an empty set to be zero.

&#x20;

**Example 1:**

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

**Example 2:**

<pre><code><strong>Input: nums = [4,2,1,2], p = 1
</strong><strong>Output: 0
</strong><strong>Explanation: 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.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 109`
* `0 <= p <= (nums.length)/2`\ <br>

## Intuition

```
Here we have to maximum difference between two pairs

So, instead we take the maximum difference in the entire array after sorting
And with binary search find out if that gives us the p pairs

So, If for a max diff, we get p pairs our job is done

1 2 3 4 5 6
Lowest diff = 0
highest diff = 6-1 = 5

0 to 5 apply BS and check which highest difference gives you those p pairs
```

### Links

<https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/description/>

### Video Links

<https://www.youtube.com/watch?v=kvEVrnNuIUc&t=585s&ab_channel=C0deSutra>

### Approach 1:

```
Binary Search
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        int low = 0;
        int high = nums[n-1] - nums[0];
        //Max difference

        while(low < high){
            int mid = low + (high-low)/2;
            // Having difference as mid
            int countPairs = 0;

            for(int i=1; i<n and countPairs<p; i++){
                if(nums[i] - nums[i-1] <= mid){
                    // Once that index is taken, it cannot be used again
                    i++;
                    countPairs++;
                }
            }
            // If we get the required number of pairs for a particular difference
            // Then we try to find for more lower difference 
            if(countPairs>=p)
            // As mid can be a potential answer as it given required pairs
                high = mid;

            else
            // If pairs are less than p no need of that mid , so low = mid+1
                low = mid+1;

        }

        return low;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/2616.-minimize-the-maximum-difference-of-pairs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.