2616. Minimize the Maximum Difference of Pairs LeetCode Solution

In this guide, you will get 2616. Minimize the Maximum Difference of Pairs LeetCode Solution with the best time and space complexity. The solution to Minimize the Maximum Difference of Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimize the Maximum Difference of Pairs solution in C++
4. Minimize the Maximum Difference of Pairs solution in Java
5. Minimize the Maximum Difference of Pairs solution in Python
6. Additional Resources

Problem Statement of Minimize the Maximum Difference of Pairs

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

Complexity Analysis

• Time Complexity: O(\texttt{sort}) + O(n\log (\max(\texttt{nums}) – \min(\texttt{nums})))
• Space Complexity: O(\texttt{sort})

2616. Minimize the Maximum Difference of Pairs LeetCode Solution in C++

class Solution {
 public:
  int minimizeMax(vector<int>& nums, int p) {
    ranges::sort(nums);

    int l = 0;
    int r = nums.back() - nums.front();

    while (l < r) {
      const int m = (l + r) / 2;
      if (numPairs(nums, m) >= p)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  // Returns the number of pairs that can be obtained if the difference between
  // each pair <= `maxDiff`.
  int numPairs(const vector<int>& nums, int maxDiff) {
    int pairs = 0;
    for (int i = 1; i < nums.size(); ++i)
      // Greedily pair nums[i] with nums[i - 1].
      if (nums[i] - nums[i - 1] <= maxDiff) {
        ++pairs;
        ++i;
      }
    return pairs;
  }
};
/* code provided by PROGIEZ */

2616. Minimize the Maximum Difference of Pairs LeetCode Solution in Java

class Solution {
  public int minimizeMax(int[] nums, int p) {
    Arrays.sort(nums);

    int l = 0;
    int r = nums[nums.length - 1] - nums[0];

    while (l < r) {
      final int m = (l + r) / 2;
      if (numPairs(nums, m) >= p)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  // Returns the number of pairs that can be obtained if the difference between each
  // pair <= `maxDiff`.
  private int numPairs(int[] nums, int maxDiff) {
    int pairs = 0;
    for (int i = 1; i < nums.length; ++i)
      // Greedily pair nums[i] with nums[i - 1].
      if (nums[i] - nums[i - 1] <= maxDiff) {
        ++pairs;
        ++i;
      }
    return pairs;
  }
}
// code provided by PROGIEZ

2616. Minimize the Maximum Difference of Pairs LeetCode Solution in Python

class Solution:
  def minimizeMax(self, nums: list[int], p: int) -> int:
    nums.sort()

    def numPairs(maxDiff: int) -> int:
      """
      Returns the number of pairs that can be obtained if the difference between
      each pair <= `maxDiff`.
      """
      pairs = 0
      i = 1
      while i < len(nums):
        # Greedily pair nums[i] with nums[i - 1].
        if nums[i] - nums[i - 1] <= maxDiff:
          pairs += 1
          i += 2
        else:
          i += 1
      return pairs

    return bisect.bisect_left(range(nums[-1] - nums[0]), p, key=numPairs)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.