> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/2616.-minimize-the-maximum-difference-of-pairs.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` 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>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.