Skip to content

2616. Minimize the Maximum Difference of Pairs

Description

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

Solutions

Solution 1: Binary Search + Greedy

We notice that the maximum difference has monotonicity: if a maximum difference \(x\) is feasible, then \(x-1\) is also feasible. Therefore, we can use binary search to find the minimal feasible maximum difference.

First, sort the array \(\textit{nums}\). Then, for a given maximum difference \(x\), check whether it is possible to form \(p\) pairs of indices such that the maximum difference in each pair does not exceed \(x\). If possible, we can try a smaller \(x\); otherwise, we need to increase \(x\).

To check whether \(p\) such pairs exist with maximum difference at most \(x\), we can use a greedy approach. Traverse the sorted array \(\textit{nums}\) from left to right. For the current index \(i\), if the difference between \(\textit{nums}[i+1]\) and \(\textit{nums}[i]\) does not exceed \(x\), we can form a pair with \(i\) and \(i+1\), increment the pair count \(cnt\), and increase \(i\) by \(2\). Otherwise, increase \(i\) by \(1\). After traversing, if \(cnt \geq p\), then such \(p\) pairs exist; otherwise, they do not.

The time complexity is \(O(n \times (\log n + \log m))\), where \(n\) is the length of \(\textit{nums}\) and \(m\) is the difference between the maximum and minimum values in \(\textit{nums}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        def check(diff: int) -> bool:
            cnt = i = 0
            while i < len(nums) - 1:
                if nums[i + 1] - nums[i] <= diff:
                    cnt += 1
                    i += 2
                else:
                    i += 1
            return cnt >= p

        nums.sort()
        return bisect_left(range(nums[-1] - nums[0] + 1), True, key=check)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int n = nums.length;
        int l = 0, r = nums[n - 1] - nums[0] + 1;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (count(nums, mid) >= p) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private int count(int[] nums, int diff) {
        int cnt = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            if (nums[i + 1] - nums[i] <= diff) {
                ++cnt;
                ++i;
            }
        }
        return cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int l = 0, r = nums[n - 1] - nums[0] + 1;
        auto check = [&](int diff) -> bool {
            int cnt = 0;
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i + 1] - nums[i] <= diff) {
                    ++cnt;
                    ++i;
                }
            }
            return cnt >= p;
        };
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func minimizeMax(nums []int, p int) int {
    sort.Ints(nums)
    n := len(nums)
    r := nums[n-1] - nums[0] + 1
    return sort.Search(r, func(diff int) bool {
        cnt := 0
        for i := 0; i < n-1; i++ {
            if nums[i+1]-nums[i] <= diff {
                cnt++
                i++
            }
        }
        return cnt >= p
    })
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function minimizeMax(nums: number[], p: number): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let l = 0,
        r = nums[n - 1] - nums[0] + 1;
    const check = (diff: number): boolean => {
        let cnt = 0;
        for (let i = 0; i < n - 1; ++i) {
            if (nums[i + 1] - nums[i] <= diff) {
                ++cnt;
                ++i;
            }
        }
        return cnt >= p;
    };
    while (l < r) {
        const mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
impl Solution {
    pub fn minimize_max(mut nums: Vec<i32>, p: i32) -> i32 {
        nums.sort();
        let n = nums.len();
        let (mut l, mut r) = (0, nums[n - 1] - nums[0] + 1);

        let check = |diff: i32| -> bool {
            let mut cnt = 0;
            let mut i = 0;
            while i < n - 1 {
                if nums[i + 1] - nums[i] <= diff {
                    cnt += 1;
                    i += 2;
                } else {
                    i += 1;
                }
            }
            cnt >= p
        };

        while l < r {
            let mid = (l + r) / 2;
            if check(mid) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        l
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int MinimizeMax(int[] nums, int p) {
        Array.Sort(nums);
        int n = nums.Length;
        int l = 0, r = nums[n - 1] - nums[0] + 1;

        bool check(int diff) {
            int cnt = 0;
            for (int i = 0; i < n - 1; ++i) {
                if (nums[i + 1] - nums[i] <= diff) {
                    ++cnt;
                    ++i;
                }
            }
            return cnt >= p;
        }

        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $p
     * @return Integer
     */
    function minimizeMax($nums, $p) {
        sort($nums);
        $n = count($nums);
        $l = 0;
        $r = $nums[$n - 1] - $nums[0] + 1;

        $check = function ($diff) use ($nums, $n, $p) {
            $cnt = 0;
            for ($i = 0; $i < $n - 1; ++$i) {
                if ($nums[$i + 1] - $nums[$i] <= $diff) {
                    ++$cnt;
                    ++$i;
                }
            }
            return $cnt >= $p;
        };

        while ($l < $r) {
            $mid = intdiv($l + $r, 2);
            if ($check($mid)) {
                $r = $mid;
            } else {
                $l = $mid + 1;
            }
        }

        return $l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    func minimizeMax(_ nums: [Int], _ p: Int) -> Int {
        var nums = nums.sorted()
        let n = nums.count
        var l = 0
        var r = nums[n - 1] - nums[0] + 1

        func check(_ diff: Int) -> Bool {
            var cnt = 0
            var i = 0
            while i < n - 1 {
                if nums[i + 1] - nums[i] <= diff {
                    cnt += 1
                    i += 2
                } else {
                    i += 1
                }
            }
            return cnt >= p
        }

        while l < r {
            let mid = (l + r) >> 1
            if check(mid) {
                r = mid
            } else {
                l = mid + 1
            }
        }

        return l
    }
}

Comments