Minimize the Maximum Difference of pairs

Question

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 minimim maximum difference among all p pairs. We define the maximum of an emprty 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.

Understanding: §

This question is asking about finding the pairs of numbers (x, ,y) such that the difference between them is minimum. And should return the maximum value from the pairs nums = [3,4,2,3,2,1,2] and p = 3 here the pairs can be 2 - 2 = 0 3 - 3 = 0 4 - 3 = 1 Maximum value of which is 1

Process: §

Let’s first sort the array

• Sort(nums) — Ascending order After that we need two numbers from this let’s call them nums[i] and nums[j] where these numbers must be the lowest Objective Function But what is the objective function is ?

If the array is nums = [1,1,2,3,7,10]

What needs to be kept in mind is that max(pair1, pair2, pair3 . . .pairN) has to have pair that will have least values ! The way finding that minimum maximum would be possible Let’s assume the minimum to be x After which we check if there are that many pairs or more with the same or less difference than x

• nums = [a,b,c,d,e,f]
• no_of_pairs_with_diff <= x ?
  • If no_of_pairs_with_diff >= p Then we still haven’t found the minimum

%%🖋 Edit in Excalidraw, and the dark exported image%%

Algorithm §

• Sort nums in Ascending Order
  • Find floor mid difference of the array
• Make binary_search:
  • Left = 0, Right = nums[first] - nums[last]
  • Make Loop while Left < Right
    • If (no_Of_Pair with (diff <= mid) ) < p
      • left = mid + 1
    • else
      • right = mid
  • return Left

Code In JS §

var minimizeMax = function(nums, p) {
        nums.sort((a,b)=>{return a - b})
    let left = 0
    let right = nums[nums.length - 1] - nums [0]
    while (left < right){
        mid = Math.floor((left + right)/2)
        if (canPair(mid, nums) < p){
            left = mid  + 1
        } else {
            right = mid
        }
    }; return left
};
 
function canPair(mid, nums){
    let count = 0
    for (let i = 0; i <= nums.length - 1;){
            let diff = nums[i+1] - nums[i]
            if (diff <= mid){
                count++
                i += 2
            } else {
                i++
            }
    }
    return count
}