Minimize the Maximum Difference of Pairs

MEDIUM

Description

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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= p <= (nums.length)/2

Approaches

Checkout 2 different approaches to solve Minimize the Maximum Difference of Pairs. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Sort the input array nums.
Initialize a DP table dp of size (n+1) x (p+1) with a large value.
Set dp[i][0] = 0 for all i from 0 to n.
Iterate i from 1 to n:
Iterate k from 1 to p:
```
// Option 1: Don't use nums[i-1]
```
```
`option1 = dp[i-1][k]`
```

// Option 2: Pair nums[i-1] with nums[i-2]

```
`option2 = infinity`
```
If i >= 2:
```
 `diff = nums[i-1] - nums[i-2]`
```
```
 `option2 = max(diff, dp[i-2][k-1])`
```
dp[i][k] = min(option1, option2)
Return dp[n][p].

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]):

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

// 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];
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Minimize the Maximum Difference of Pairs. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Minimize the Maximum Difference of Pairs

Algorithms:

Binary SearchSorting

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

Array

Companies:

Media.net |Navi |