Scale Engineer

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 ProgrammingGreedy
Algorithms
Binary SearchSorting
Data structures
Array
Companies
Media.netNavi

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 <= 105
  • 0 <= nums[i] <= 109
  • 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

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

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

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

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.

Solutions

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 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 →

Next problem