Minimize the Maximum Difference of Pairs

Med

#2396Time: 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.2 companies

Patterns

Dynamic Programming Greedy

Algorithms

Binary Search Sorting

Data structures

Array

Companies

Media.net Navi

Prompt

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

2 approaches with complexity analysis and trade-offs.

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

Walkthrough

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

1// This approach is too slow and will time out (TLE).2// It is presented for conceptual understanding.3class Solution {4    public int minimizeMax(int[] nums, int p) {5        if (p == 0) {6            return 0;7        }8        int n = nums.length;9        Arrays.sort(nums);10        11        int[][] dp = new int[n + 1][p + 1];12        for (int i = 0; i <= n; i++) {13            Arrays.fill(dp[i], Integer.MAX_VALUE);14        }15        16        for (int i = 0; i <= n; i++) {17            dp[i][0] = 0;18        }19        20        for (int i = 1; i <= n; i++) {21            for (int j = 1; j <= p; j++) {22                // Option 1: Don't include nums[i-1] in a pair23                int option1 = dp[i - 1][j];24                25                // Option 2: Pair nums[i-1] with nums[i-2]26                int option2 = Integer.MAX_VALUE;27                if (i >= 2 && dp[i - 2][j - 1] != Integer.MAX_VALUE) {28                    int diff = nums[i - 1] - nums[i - 2];29                    option2 = Math.max(diff, dp[i - 2][j - 1]);30                }31                32                dp[i][j] = Math.min(option1, option2);33            }34        }35        36        return dp[n][p];37    }38}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Sort the input array nums.
Initialize the binary search range: low = 0, high = nums[n-1] - nums[0].
Initialize result = high.
While low <= high:
mid = low + (high - low) / 2.
If canFormPairs(nums, mid, p) is true:
`result = mid`.
`high = mid - 1` (try for a smaller max difference).
Else:
low = mid + 1 (need a larger max difference).
Return result.

Helper function canFormPairs(nums, max_diff, p):

Initialize count = 0.
Initialize a pointer i = 1.
While i < nums.length:
If nums[i] - nums[i-1] <= max_diff:
Increment `count`.
Increment `i` by 2 (since we used both elements).
Else:
Increment `i` by 1.
Return count >= p.

Walkthrough

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.

1class Solution {2    public int minimizeMax(int[] nums, int p) {3        Arrays.sort(nums);4        int n = nums.length;5        int low = 0, high = nums[n - 1] - nums[0];6        int result = high;7 8        while (low <= high) {9            int mid = low + (high - low) / 2;10            if (canFormPairs(nums, mid, p)) {11                result = mid;12                high = mid - 1;13            } else {14                low = mid + 1;15            }16        }17        return result;18    }19 20    // Greedily checks if we can form at least p pairs21    // with a maximum difference of maxDiff.22    private boolean canFormPairs(int[] nums, int maxDiff, int p) {23        int count = 0;24        int i = 1;25        while (i < nums.length) {26            if (nums[i] - nums[i - 1] <= maxDiff) {27                count++;28                i += 2;29            } else {30                i++;31            }32            if (count >= p) {33                return true;34            }35        }36        return false;37    }38}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1public class Solution {2    public int MinimizeMax(int[] nums, int p) {3        Array.Sort(nums);4        int n = nums.Length;5        int l = 0, r = nums[n - 1] - nums[0] + 1;6        bool check(int diff) {7            int cnt = 0;8            for (int i = 0; i < n - 1; ++i) {9                if (nums[i + 1] - nums[i] <= diff) {10                    ++cnt;11                    ++i;12                }13            }14            return cnt >= p;15        }16        while (l < r) {17            int mid = (l + r) >> 1;18            if (check(mid)) {19                r = mid;20            } else {21                l = mid + 1;22            }23        }24        return l;25    }26}

1class Solution {2public3  int minimizeMax(int[] nums, int p) {4    Arrays.sort(nums);5    int n = nums.length;6    int l = 0, r = nums[n - 1] - nums[0] + 1;7    while (l < r) {8      int mid = (l + r) >>> 1;9      if (count(nums, mid) >= p) {10        r = mid;11      } else {12        l = mid + 1;13      }14    }15    return l;16  }17private18  int count(int[] nums, int diff) {19    int cnt = 0;20    for (int i = 0; i < nums.length - 1; ++i) {21      if (nums[i + 1] - nums[i] <= diff) {22        ++cnt;23        ++i;24      }25    }26    return cnt;27  }28}

1class Solution {2public:3  int minimizeMax(vector<int> &nums, int p) {4    sort(nums.begin(), nums.end());5    int n = nums.size();6    int l = 0, r = nums[n - 1] - nums[0] + 1;7    auto check = [&](int diff) -> bool {8      int cnt = 0;9      for (int i = 0; i < n - 1; ++i) {10        if (nums[i + 1] - nums[i] <= diff) {11          ++cnt;12          ++i;13        }14      }15      return cnt >= p;16    };17    while (l < r) {18      int mid = (l + r) >> 1;19      if (check(mid)) {20        r = mid;21      } else {22        l = mid + 1;23      }24    }25    return l;26  }27};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem