Skip to content

← leetcode

Minimize the Maximum Difference of Pairs

· Medium

LeetCode problem 2616

This question is classic binary search.

Just realise that depending on the max difference we select, there will be a difference in the choices that we make for the pairs that we choose.

In fact, it is optimal to take a greedy approach; by sorting nums from smallest to largest and checking if the adjacent value is a viable pair or not given the chosen max difference constraint.

  • e.g. 1, 5, 5, 7
    • for a difference of 2, we will end up choosing (5, 5)
    • for a difference of 4, we will end up choosing (1, 5) and (5, 7)

Then, the easiest approach we can do to find the minimal max difference, is to use binary search to search through all the possible differences and find the ones that are viable.

code

class Solution {
public:
    int binarySearch(int target, vector<int>&nums, int p) {
        int counter = 0;
        for (int i = 0; i < nums.size()-1; ++i) {
            if (nums[i+1]-nums[i] <= target) {
                ++counter;
                if (counter == p) {
                    return true;
                }
                ++i;
            }
        }
        return false;
    }
    int minimizeMax(vector<int>& nums, int p) {
        if (p == 0 or nums.size() == 0) return 0;

        sort(nums.begin(), nums.end());
        int left = 0, right = 0;
        for (int num : nums) {
            right = max(right, num);
        }

        while (left < right) {
            int middle = left + (right-left)/2;

            if (binarySearch(middle, nums, p)) {
                right = middle;
            } else {
                left = middle+1;
            }
        }
        return right;
    }
};

complexity

  • Time: O(n log(largestNum) + n log(n) ), where n is the size of nums and largestNum is the largest number in nums
  • Space: O(1)

time taken

  • 14 minutes and 28 seconds