Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a proposed maximum difference, ask whether at least p disjoint pairs can be formed. In sorted order, pairing the first available adjacent values whenever they qualify maximizes the number of pairs. If they do not qualify, the smaller value cannot pair with any later one.

Approach

Sort the array and binary-search a difference between zero and the full value range. For each candidate, scan left to right: take an adjacent pair when its difference fits and skip both entries, otherwise skip only the first. If the pair count reaches p, try a smaller threshold; otherwise increase it. Return the smallest feasible threshold. Requiring disjoint indices is enforced by skipping both matched entries, and p = 0 yields zero.

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        n = len(nums)
        nums.sort()

        def pairs(x):
            i = 0
            count = 0
            while i < n - 1:
                if nums[i + 1] - nums[i] <= x:
                    i += 1
                    count += 1
                i += 1
            return count

        l = 0
        h = nums[-1] - nums[0]

        while l < h:
            mid = l + (h - l) // 2
            if pairs(mid) >= p:
                h = mid
            else:
                l = mid + 1

        return l

Complexity analysis

Let n = nums.length and V = max(nums) - min(nums). Time: O(n log n + n log(V + 1)) for sorting and answer binary search with a linear greedy feasibility check. Auxiliary space: up to O(n) for sorting workspace.