2616: Minimize-the-Maximum-Difference-of-Pairs
Medium

table of contents

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.

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 taken