DDSA Solutions

2616. Minimize the Maximum Difference of Pairs

HardView on LeetCode
ArrayBinary SearchGreedy
Time: O(n log n)
Space: O(1)

Problem Overview

Minimize maximum difference of pairs.

Intuition

Minimize maximum difference of pairs. Sort array. Binary search on max diff, greedily pair adjacent elements.

Algorithm

  1. 1Sort. Binary search on diff d. Feasibility: greedy scan pairs: if nums[i+1]-nums[i] <= d: count pair, skip both.
  2. 2Return minimum d where count >= p.

Common Pitfalls

  • •Greedy pairing: after sorting, pair adjacent if within diff. Binary search on the diff value.
2616.cs
C#
// Approach: Sort; binary search on max difference; greedy consecutive-pair validation.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int MinimizeMax(int[] nums, int p)
    {
        Array.Sort(nums);

        int n = nums.Length;

        int low = 0;
        int high = nums[n - 1] - nums[0];

        while (low < high)
        {
            int mid = (low + high) / 2;
            if (cntNumPairs(mid, nums) >= p)
                high = mid;
            else
                low = mid + 1;
        }

        return low;
    }

    private int cntNumPairs(int diff, int[] nums)
    {
        int pairs = 0;

        for (int i = 1; i < nums.Length; i++)
        {
            if (nums[i] - nums[i - 1] <= diff)
            {
                pairs++;
                i++;
            }
        }

        return pairs;
    }
}
Was this solution helpful?

Related Problems