LeetCode 2616: Minimize the Maximum Difference of Pairs Solution

Master LeetCode problem 2616 (Minimize the Maximum Difference of Pairs), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2616. Minimize the Maximum Difference of Pairs

Medium

Array Binary Search Greedy

Problem Explanation

Explanation

To solve this problem, we can use binary search to find the minimum maximum difference. We first sort the given array nums, then use binary search to find the optimal value for the maximum difference. For each value we choose in the binary search, we try to form p pairs of indices such that the maximum difference among the pairs is less than or equal to this chosen value. We can use a greedy approach to form these pairs.

We start by fixing the first pair's index at 0 and then try to find an index for the second pair such that the difference is less than or equal to the chosen value. We continue this process for all pairs. If at any point we can't find p valid pairs, we increase the chosen value for maximum difference in the binary search. If we can find p valid pairs for a chosen value, we try to minimize this value by moving to the left in the binary search.

At the end of binary search, the minimum maximum difference we found is the answer.

Time Complexity: The time complexity of this approach is O(n log(max-min)), where n is the length of the array nums, and max-min is the range of numbers in the array.

Space Complexity: The space complexity is O(1) as we are not using any additional data structures other than a few variables.

Solution Code

class Solution {
    public int minimumDifference(int[] nums, int p) {
        Arrays.sort(nums);
        
        int left = 0, right = Integer.MAX_VALUE;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(nums, p, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private boolean check(int[] nums, int p, int maxDiff) {
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i + p - 1 < n; i++) {
            if (nums[i + p - 1] - nums[i] <= maxDiff) {
                count = p;
                break;
            }
        }
        
        for (int i = 0; i < n - p && count < p; i++) {
            int diff = nums[i + p] - nums[i];
            if (diff <= maxDiff) {
                count++;
            }
        }
        
        return count == p;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2616 (Minimize the Maximum Difference of Pairs)?

This page provides optimized solutions for LeetCode problem 2616 (Minimize the Maximum Difference of Pairs) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2616 (Minimize the Maximum Difference of Pairs)?

The time complexity for LeetCode 2616 (Minimize the Maximum Difference of Pairs) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2616 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2616 in Java, C++, or Python.

Back to LeetCode Solutions