2616. Minimize the Maximum Difference of Pairs

Problem Statement

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

Intuition

Here we have to maximum difference between two pairs

So, instead we take the maximum difference in the entire array after sorting
And with binary search find out if that gives us the p pairs

So, If for a max diff, we get p pairs our job is done

1 2 3 4 5 6
Lowest diff = 0
highest diff = 6-1 = 5

0 to 5 apply BS and check which highest difference gives you those p pairs

Links

https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/description/

Video Links

https://www.youtube.com/watch?v=kvEVrnNuIUc&t=585s&ab_channel=C0deSutra

Approach 1:

Binary Search

C++

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        int low = 0;
        int high = nums[n-1] - nums[0];
        //Max difference

        while(low < high){
            int mid = low + (high-low)/2;
            // Having difference as mid
            int countPairs = 0;

            for(int i=1; i<n and countPairs<p; i++){
                if(nums[i] - nums[i-1] <= mid){
                    // Once that index is taken, it cannot be used again
                    i++;
                    countPairs++;
                }
            }
            // If we get the required number of pairs for a particular difference
            // Then we try to find for more lower difference 
            if(countPairs>=p)
            // As mid can be a potential answer as it given required pairs
                high = mid;

            else
            // If pairs are less than p no need of that mid , so low = mid+1
                low = mid+1;

        }

        return low;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems