Binary Search: LC 2616 Minimize the Maximum Difference of Pairs

LC 2616 Minimize the Maximum Difference of Pairs

This is the 3rd question of the weekly contest 340.

It has two main ideas:

1. Binary search.
2. Greedy.

Binary search

Using the binary search is not trivial, as usually the binary search has to have a continuous searching space. It means if we have a vaild region, such as [low, high], then all the continuous values between low and high must be valid.

For this problem, it is continuous as shown in below example:

1, 2, 2, 4, 4, 8

If the maximum difference is 2, we have qualified pairs of:

(1, 2) and (2, 4)

or (2, 2) and (4, 4)

If the maximum difference is 4, we have

(1, 2) and (2, 4) and (4, 8)

From 2 to 4, the number of qualified pairs are continuous, which are:

max difference is 2: 2 pairs

max difference is 3: 2 pairs

max difference is 4: 3 pairs

Based on those example, a more general description will be:

Suppose we have a function f, the input is max_difference, the output is number of qualified pairs, the value of f(max_difference) is continuous.

so we can use binary search to find the best smallest max_difference.

Greedy

A example

1, 2, 2, 4, 4, 8

For above example, why

case 1: (1, 2) and (2, 4)

‘s performance should be ≥

case2: (2, 2) and (4, 4)?

Which means that for the sorted nums, we should pick up the earliest qualified pair. The reason is:

suppose we use the function f(mums, max_val) to represent the maximum qualified pairs that we can have, then:

case1: f([1, 2, 2, 4, 4, 8], 2) = 1 + f([2, 4, 4, 8], 2)

case 2: f([1, 2, 2, 4, 4, 8], 2) = 1 + f([4, 4, 8], 2)

Since f([2, 4, 4, 8], 2) has a longer nums than f([4, 4, 8], 2), so we can easily say that f([2, 4, 4, 8], 2) ≥ f([4, 4, 8], 2).

More formally proof

More formally, suppose we have a list of:

nums = [a, b] + rest

Then:

if (a, b) is a good pair:

• case1: f([a, b] + rest, max_val) = 1 + f(rest, max_val)
• case2: f([a, b] + rest, max_val) = f([b] + rest, max_val) ≤ f([b] + rest[:1], max_val) + f(rest[1:], max_val)

case1 ≥ case2

if (a, b) is a not a good pair:

• case1: f([a, b] + rest, max_val) = f([b] + rest, max_val)
• case2: f([a, b] + rest, max_val) = f([b] + rest, max_val)

case 1 == case2

From above, we show that picking up the earliest qualified pair are optimal.

C++ code

class Solution {
public:
    bool good(vector<int>& nums, int max_diff, int p){
        int cnt = 0;
        for (int i = 0; i < nums.size() - 1; ++i){
            if (nums[i + 1] - nums[i] <= max_diff){
                cnt++;
                if (cnt >= p)return true;
                i++;
            }
        }
        return false;
    }
    int minimizeMax(vector<int>& nums, int p) {
        if (p == 0)return 0;
        sort(nums.begin(), nums.end());
        int lo = 0, hi = nums.back() - nums[0];
        while (lo < hi){
            int mid = (lo + hi) / 2;
            if (good(nums, mid, p)){
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
};

Python Code (naive recursive one which will get TLE)

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        if p == 0:return 0;
        nums.sort()
       
        def num_of_qualified_pair(nums, max_val):
            f = num_of_qualified_pair
            if len(nums) <= 1:return 0
            return 1 + f(nums[2:], max_val) if nums[1] - nums[0] <= max_val else f(nums[1:], max_val)

        lo, hi = 0, nums[-1] - nums[0]   
        while lo < hi:
            mid = (lo + hi) // 2
            if num_of_qualified_pair(nums, mid) >= p:
                hi = mid
            else:
                lo = mid + 1
        return lo

Python Code (Optimized AC one)

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        if p == 0:return 0
        nums.sort()
       
        def num_of_qualified_pair(begin_idx, max_val):
            f = num_of_qualified_pair
            i = begin_idx
            if len(nums) - i <= 1:return 0
            return 1 + f(i + 2, max_val) if nums[i+1] - nums[i] <= max_val else f(i + 1, max_val)

        lo, hi = 0, nums[-1] - nums[0]   
        while lo < hi:
            mid = (lo + hi) // 2
            if num_of_qualified_pair(0, mid) >= p:
                hi = mid
            else:
                lo = mid + 1
        return lo