# Minimize the Maximum Difference of Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs)
Canonical: https://scaleengineer.com/dsa/problems/minimize-the-maximum-difference-of-pairs
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net), [Navi](https://scaleengineer.com/companies/navi)
---
## Problem
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.

**Example 1:**

**Input:** nums = [10,1,2,7,1,3], p = 2
**Output:** 1
**Explanation:** 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.

**Example 2:**

**Input:** nums = [4,2,1,2], p = 1
**Output:** 0
**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.

**Constraints:**

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

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. The core idea is to build up a solution by finding the minimum maximum difference for smaller subproblems. We first sort the array to easily calculate differences between adjacent elements. We define `dp[i][k]` as the minimum maximum difference required to form `k` pairs from the first `i` elements of the sorted array.
**Time:** O(n * p). Sorting takes O(n log n). The nested loops for the DP table run n * p times. Since p can be up to n/2, this is roughly O(n^2) in the worst case, which is too slow for the given constraints. · **Space:** O(n * p) for the DP table. This can be optimized to O(p) by only keeping track of the previous two rows of the DP table.
**Pros:** It's a structured way to think about the problem by breaking it down into subproblems.
**Cons:** The time complexity is too high and will result in a "Time Limit Exceeded" error on most platforms for the given constraints.; The space complexity is also high without optimization.
### Explanation
First, sort the input array `nums` in non-decreasing order. This is crucial because to minimize the difference, we should always pair adjacent or close-by elements.
Create a 2D DP table, `dp[i][k]`, where `i` ranges from 0 to `n` (the number of elements) and `k` ranges from 0 to `p`. `dp[i][k]` will store the minimum possible value of the maximum difference among `k` pairs that can be formed using elements from the prefix `nums[0...i-1]`.
The state transition for `dp[i][k]` considers two possibilities for the `i`-th element (`nums[i-1]`):
1.  **`nums[i-1]` is not part of any pair:** In this case, we must form `k` pairs from the first `i-1` elements. The value would be `dp[i-1][k]`.
2.  **`nums[i-1]` is paired with `nums[i-2]`:** This is only possible if `i >= 2`. We form one pair `(nums[i-2], nums[i-1])`. The difference for this new pair is `nums[i-1] - nums[i-2]`. The remaining `k-1` pairs must be formed from the first `i-2` elements. The maximum difference for this choice would be `max(nums[i-1] - nums[i-2], dp[i-2][k-1])`.
The recurrence relation is: `dp[i][k] = min(dp[i-1][k], max(nums[i-1] - nums[i-2], dp[i-2][k-1]))`.
The base cases are `dp[i][0] = 0` for all `i`, and `dp[i][k] = infinity` if `2*k > i`.
The final answer is `dp[n][p]`.
The space complexity can be optimized from O(n*p) to O(p) since `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`.

```java
// This approach is too slow and will time out (TLE).
// It is presented for conceptual understanding.
class Solution {
    public int minimizeMax(int[] nums, int p) {
        if (p == 0) {
            return 0;
        }
        int n = nums.length;
        Arrays.sort(nums);
        
        int[][] dp = new int[n + 1][p + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        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++) {
                // Option 1: Don't include nums[i-1] in a pair
                int option1 = dp[i - 1][j];
                
                // Option 2: Pair nums[i-1] with nums[i-2]
                int option2 = Integer.MAX_VALUE;
                if (i >= 2 && dp[i - 2][j - 1] != Integer.MAX_VALUE) {
                    int diff = nums[i - 1] - nums[i - 2];
                    option2 = Math.max(diff, dp[i - 2][j - 1]);
                }
                
                dp[i][j] = Math.min(option1, option2);
            }
        }
        
        return dp[n][p];
    }
}
```
### Algorithm
1. Sort the input array `nums`.
2. Initialize a DP table `dp` of size `(n+1) x (p+1)` with a large value.
3. Set `dp[i][0] = 0` for all `i` from 0 to `n`.
4. Iterate `i` from 1 to `n`:
5.   Iterate `k` from 1 to `p`:
6.     // Option 1: Don't use nums[i-1]
7.     `option1 = dp[i-1][k]`
8.     // Option 2: Pair nums[i-1] with nums[i-2]
9.     `option2 = infinity`
10.    If `i >= 2`:
11.      `diff = nums[i-1] - nums[i-2]`
12.      `option2 = max(diff, dp[i-2][k-1])`
13.    `dp[i][k] = min(option1, option2)`
14. Return `dp[n][p]`.

## Binary Search on the Answer with Greedy Check
This is the most efficient approach. The problem asks to "minimize the maximum" of some value, which is a strong indicator that we can binary search on the answer. The "answer" here is the maximum allowed difference. We can search for the smallest possible value for this maximum difference, let's call it `max_diff`, for which we can still form `p` pairs.
**Time:** O(n log n + n log(max_val)). Sorting takes O(n log n). The binary search runs `log(max_val)` times, where `max_val` is the difference between the maximum and minimum elements in `nums`. Inside each binary search iteration, the `canFormPairs` check takes O(n). The `n log n` term from sorting is typically dominant. · **Space:** O(log n) or O(n) depending on the implementation of the sorting algorithm used. This is the space required for the recursion stack in quicksort or for a temporary array in mergesort.
**Pros:** Highly efficient and passes within the time limits.; The logic is clean and leverages a common algorithmic pattern (binary search on the answer).
**Cons:** The insight to use binary search on the answer might not be immediately obvious.
### Explanation
The range of possible answers for `max_diff` is from `0` to `nums[n-1] - nums[0]` (after sorting). We can perform a binary search on this range.
For each `mid` value in our binary search (which represents a potential `max_diff`), we need a way to check if it's feasible to form `p` pairs such that no pair has a difference greater than `mid`.
This check can be done greedily. First, we sort the array `nums`. Then, we iterate through the sorted array and try to form pairs. When we are at index `i`, we check the difference `nums[i] - nums[i-1]`.
If `nums[i] - nums[i-1] <= mid`, we can form a valid pair. It's always optimal to form this pair because it uses adjacent elements (the smallest possible difference for `nums[i]`) and leaves the rest of the array for other pairs. After forming this pair, we increment our pair count and skip both `nums[i-1]` and `nums[i]` by advancing our pointer by 2.
If `nums[i] - nums[i-1] > mid`, we cannot form a pair with `nums[i-1]` and `nums[i]`. We must discard `nums[i-1]` and try to pair `nums[i]` with `nums[i+1]` in the next step. So, we advance our pointer by 1.
After iterating through the array, if the count of pairs we formed is greater than or equal to `p`, then `mid` is a feasible maximum difference.
The binary search proceeds as follows:
- If `check(mid)` is true, it means `mid` is a possible answer. We try to find an even smaller answer, so we set `ans = mid` and `high = mid - 1`.
- If `check(mid)` is false, `mid` is too small. We need to allow a larger difference, so we set `low = mid + 1`.

```java
class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int n = nums.length;
        int low = 0, high = nums[n - 1] - nums[0];
        int result = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canFormPairs(nums, mid, p)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }

    // Greedily checks if we can form at least p pairs
    // with a maximum difference of maxDiff.
    private boolean canFormPairs(int[] nums, int maxDiff, int p) {
        int count = 0;
        int i = 1;
        while (i < nums.length) {
            if (nums[i] - nums[i - 1] <= maxDiff) {
                count++;
                i += 2;
            } else {
                i++;
            }
            if (count >= p) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
1. Sort the input array `nums`.
2. Initialize the binary search range: `low = 0`, `high = nums[n-1] - nums[0]`.
3. Initialize `result = high`.
4. While `low <= high`:
5.   `mid = low + (high - low) / 2`.
6.   If `canFormPairs(nums, mid, p)` is true:
7.     `result = mid`.
8.     `high = mid - 1` (try for a smaller max difference).
9.   Else:
10.    `low = mid + 1` (need a larger max difference).
11. Return `result`.

Helper function `canFormPairs(nums, max_diff, p)`:
1. Initialize `count = 0`.
2. Initialize a pointer `i = 1`.
3. While `i < nums.length`:
4.   If `nums[i] - nums[i-1] <= max_diff`:
5.     Increment `count`.
6.     Increment `i` by 2 (since we used both elements).
7.   Else:
8.     Increment `i` by 1.
9. Return `count >= p`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinimizeMax(int[] nums, int p) {
        Array.Sort(nums);
        int n = nums.Length;
        int l = 0, r = nums[n - 1] - nums[0] + 1;
        bool check(int diff) {
            int cnt = 0;
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i + 1] - nums[i] <= diff) {
                    ++cnt;
                    ++i;
                }
            }
            return cnt >= p;
        }
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
```

### Java

```java
class Solution {
public
  int minimizeMax(int[] nums, int p) {
    Arrays.sort(nums);
    int n = nums.length;
    int l = 0, r = nums[n - 1] - nums[0] + 1;
    while (l < r) {
      int mid = (l + r) >>> 1;
      if (count(nums, mid) >= p) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
private
  int count(int[] nums, int diff) {
    int cnt = 0;
    for (int i = 0; i < nums.length - 1; ++i) {
      if (nums[i + 1] - nums[i] <= diff) {
        ++cnt;
        ++i;
      }
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizeMax(vector<int> &nums, int p) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int l = 0, r = nums[n - 1] - nums[0] + 1;
    auto check = [&](int diff) -> bool {
      int cnt = 0;
      for (int i = 0; i < n - 1; ++i) {
        if (nums[i + 1] - nums[i] <= diff) {
          ++cnt;
          ++i;
        }
      }
      return cnt >= p;
    };
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int: def check(diff: int) -> bool: cnt = i = 0 while i < len(nums) - 1: if nums[i + 1] - nums[i] <= diff: cnt += 1 i += 2 else: i += 1 return cnt >= p nums . sort() return bisect_left(range(nums[- 1] - nums[0] + 1), True, key=check)

```