Minimize the maximum difference of pairs

Array Binary Search Dynamic Programming Greedy Sorting

50.9% acceptance

Feb 25, 2026

2920

328

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]|. Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimize_max(nums: Vec<i32>, p: i32) -> i32 {
    if p == 0 {
      return 0;
    }
    let mut nums = nums;
    nums.sort_unstable();
    let n = nums.len();

    // Binary search on the answer
    let can_achieve = |max_diff: i32| -> bool {
      let mut count = 0;
      let mut i = 0;
      while i + 1 < n {
        if nums[i + 1] - nums[i] <= max_diff {
          count += 1;
          i += 2; // consume both, skip to next
        } else {
          i += 1;
        }
      }
      count >= p as usize
    };

    let mut lo = 0i32;
    let mut hi = nums[n - 1] - nums[0];
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if can_achieve(mid) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}