Minimize the Maximum Difference of Pairs

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.

Examples

Example 1:

1
2
3
4
5
6
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:

1
2
3
4
5
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.

Solution

Method 1 - Binary Search

We start by sorting the array to focus on the differences between elements rather than their original order.

The possible answer lies between left = 0 and right = nums[n-1] - nums[0]. Using binary search, for each mid = (left + right) / 2, we check if it’s possible to form p pairs where the difference in each pair is at most mid.

We greedily pair adjacent elements if their difference is less than or equal to mid, skipping to the next available pair each time a pair is formed.

After each check, if we can form at least p pairs, we set right = mid; otherwise, we set left = mid + 1.

The final answer is the value of left after binary search completes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
	public int minimizeMax(int[] nums, int p) {
		Arrays.sort(nums);
		int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
		while (left < right) {
			int mid = (left + right) / 2, k = 0;
			for (int i = 1; i < n && k < p; ++i) {
				if (nums[i] - nums[i - 1] <= mid) {
					k++;
					i++;
				}
			}
			if (k >= p) {
				right = mid;
			}
			else {
				left = mid + 1;
			}
		}
		return left;        
	}	
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def minimizeMax(self, nums: list[int], p: int) -> int:
        nums.sort()
        n: int = len(nums)
        left: int = 0
        right: int = nums[-1] - nums[0]

        def can_form_pairs(max_diff: int) -> bool:
            count: int = 0
            i: int = 1
            while i < n:
                if nums[i] - nums[i - 1] <= max_diff:
                    count += 1
                    i += 2
                else:
                    i += 1
            return count >= p

        while left < right:
            mid: int = (left + right) // 2
            if can_form_pairs(mid):
                right = mid
            else:
                left = mid + 1
        return left

Complexity

Time: O(n log D), n is length of nums and D is difference between max and min in nums. Sorting takes O(n log n), and each binary search step (O(log D)) does an O(n) greedy check.
Space: O(1)

Problem#

Examples#

Solution#

Method 1 - Binary Search#

Code#

Complexity#