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 <= 1050 <= nums[i] <= 1090 <= 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 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 nums from left to right. For the current index i, if the difference between nums[i+1] and 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 ≥ p, then such p pairs exist; otherwise, they do not.
The time complexity is O(n × (log n + log m)), where n is the length of nums and m is the difference between the maximum and minimum values in nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustC#PHPSwift
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)(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
})
}(code-box)
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;
}(code-box)
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
}
}(code-box)
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;
}
}(code-box)
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;
}
}(code-box)
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
}
}(code-box)
