LeetCode 2616 - Minimize the Maximum Difference of Pairs

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to select exactly p disjoint pairs from the array nums such that the largest difference among all chosen pairs is as small as possible.

For every pair (i, j), the pair difference is defined as:

$$|nums[i] - nums[j]|$$

The goal is not to minimize the sum of differences, but specifically to minimize the maximum difference across all selected pairs.

Each index can only belong to one pair, which means the chosen pairs must be disjoint.

The input consists of:

nums, an array of integers
p, the number of pairs we must form

The output is a single integer representing the minimum possible value of the largest pair difference.

The constraints are important:

nums.length can be as large as 10^5
Values inside nums can be up to 10^9

These limits immediately rule out exponential or quadratic pairing strategies. We need something close to O(n log n).

An important observation is that pair differences become easier to reason about after sorting the array. Once sorted, nearby elements tend to produce the smallest differences.

There are several edge cases worth considering:

p = 0, where we do not need any pairs at all. The answer must be 0.
Arrays containing duplicate values, where zero-difference pairs are possible.
Large gaps between numbers, which may force larger maximum differences.
Situations where choosing locally smallest pairs greedily could appear risky unless carefully justified.
Arrays with both odd and even lengths.

The problem guarantees:

0 <= p <= nums.length / 2
Therefore, it is always possible to form p disjoint pairs.

Approaches

Brute Force Approach

A brute-force solution would try every possible way to form p disjoint pairs, compute the maximum difference for each arrangement, and then take the minimum over all possibilities.

For example, if we have:

nums = [1,2,3,4]
p = 2

We would enumerate all valid pair combinations:

(1,2) and (3,4)
(1,3) and (2,4)
(1,4) and (2,3)

For each arrangement, we compute the largest pair difference and keep the minimum result.

This approach is correct because it exhaustively checks all possibilities.

However, the number of pair combinations grows exponentially. Even for moderate array sizes, this becomes computationally impossible. Since n can reach 100000, brute force is completely infeasible.

Key Insight

The crucial observation is that we do not need to directly construct the optimal pairing arrangement.

Instead, we can binary search the answer.

Suppose we guess a value maxDiff.

The question becomes:

Can we form at least p disjoint pairs such that every pair difference is at most maxDiff?

This transforms the optimization problem into a decision problem.

After sorting the array, the best way to maximize the number of valid pairs is to greedily pair adjacent elements whenever their difference is small enough.

Why adjacent elements?

Because in a sorted array, adjacent elements always produce the smallest possible differences. Pairing non-adjacent elements can only increase the difference and potentially waste smaller pairing opportunities.

This gives us:

Sort the array.
Binary search the minimum feasible maximum difference.
Use a greedy scan to check feasibility.

This combination yields an efficient solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries every possible pairing combination
Optimal	O(n log n + n log M)	O(1) or O(log n) depending on sort	Binary search on answer with greedy feasibility check

Here, M represents the range of values in the array.

Algorithm Walkthrough

Sort the array.

Sorting places close values next to each other. Since small differences are desirable, adjacent elements become natural pairing candidates. 2. Define the binary search range.

The smallest possible maximum difference is 0.

The largest possible maximum difference is:

nums[-1] - nums[0]

after sorting. 3. Perform binary search on the answer.

For each midpoint mid, treat it as a candidate maximum allowed difference. 4. Check feasibility greedily.

Traverse the sorted array from left to right.

Whenever:

nums[i + 1] - nums[i] <= mid

form a pair and skip both elements.

Otherwise, move to the next element. 5. Count how many pairs are formed.

If we can form at least p pairs, then mid is feasible.

Try to find an even smaller answer by moving the binary search left. 6. Otherwise, if fewer than p pairs are possible, increase the allowed difference. 7. Continue until binary search converges. 8. Return the smallest feasible maximum difference.

Why it works

The correctness relies on two properties.

First, binary search works because feasibility is monotonic. If we can form p pairs with maximum difference x, then we can also form p pairs with any value larger than x.

Second, the greedy pairing strategy is optimal after sorting. Pairing adjacent valid elements preserves as many future pairing opportunities as possible. Any alternative pairing with wider gaps cannot increase the number of achievable pairs.

Python Solution

from typing import List

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        if p == 0:
            return 0

        nums.sort()

        def can_form_pairs(max_diff: int) -> bool:
            pair_count = 0
            index = 0

            while index < len(nums) - 1:
                if nums[index + 1] - nums[index] <= max_diff:
                    pair_count += 1
                    index += 2
                else:
                    index += 1

                if pair_count >= p:
                    return True

            return False

        left = 0
        right = nums[-1] - nums[0]

        while left < right:
            mid = (left + right) // 2

            if can_form_pairs(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation begins with an early return for p == 0. Since no pairs are needed, the maximum difference of an empty set is defined as zero.

The array is then sorted so that nearby elements can be efficiently paired.

The helper function can_form_pairs checks whether a given maximum difference is feasible. It greedily scans the array and pairs adjacent elements whenever their difference does not exceed max_diff.

When a pair is formed, both indices are skipped because indices cannot be reused.

Binary search is then applied over the range of possible answers. If a candidate difference is feasible, we attempt to reduce it further. Otherwise, we increase the allowed difference.

Eventually, left converges to the smallest feasible maximum difference.

Go Solution

package main

import "sort"

func minimizeMax(nums []int, p int) int {
	if p == 0 {
		return 0
	}

	sort.Ints(nums)

	canFormPairs := func(maxDiff int) bool {
		pairCount := 0
		index := 0

		for index < len(nums)-1 {
			if nums[index+1]-nums[index] <= maxDiff {
				pairCount++
				index += 2
			} else {
				index++
			}

			if pairCount >= p {
				return true
			}
		}

		return false
	}

	left := 0
	right := nums[len(nums)-1] - nums[0]

	for left < right {
		mid := left + (right-left)/2

		if canFormPairs(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

The Go implementation follows the same logic as the Python version.

The main difference is the use of Go closures for the feasibility function. Go also uses sort.Ints(nums) for sorting.

The binary search midpoint is computed as:

mid := left + (right-left)/2

which avoids potential integer overflow in languages where integer ranges are fixed.

Slices in Go behave similarly to dynamic arrays, so no additional memory handling is required.

Worked Examples

Example 1

Input:

nums = [10,1,2,7,1,3]
p = 2

Step 1: Sort the array

[1,1,2,3,7,10]

Binary Search Iterations

right	mid	Feasible?
9	4	Yes
4	2	Yes
2	1	Yes
1	0	No

Answer becomes 1.

Feasibility Check for `mid = 1`

Index	Pair Checked	Difference	Pair Formed?	Pair Count
0	(1,1)	0	Yes	1
2	(2,3)	1	Yes	2

We successfully form 2 pairs.

Maximum difference is 1.

Example 2

Input:

nums = [4,2,1,2]
p = 1

Step 1: Sort the array

[1,2,2,4]

Binary Search

left	right	mid	Feasible?
0	3	1	Yes
0	1	0	Yes

Answer becomes 0.

Feasibility Check for `mid = 0`

Index	Pair Checked	Difference	Pair Formed?	Pair Count
0	(1,2)	1	No	0
1	(2,2)	0	Yes	1

We successfully form one pair with difference 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + n log M)	Sorting plus binary search with linear feasibility checks
Space	O(1) or O(log n)	Extra space excluding sorting implementation details

The sorting step costs O(n log n).

The binary search operates over the numeric difference range. For each binary search step, we perform a linear scan through the array.

If M is the maximum possible difference, binary search requires O(log M) iterations.

Therefore, total complexity is:

O(n log n + n log M)

Since log M is at most around 31 for integer constraints, the solution is highly efficient for n = 100000.

Test Cases

sol = Solution()

# Provided examples
assert sol.minimizeMax([10,1,2,7,1,3], 2) == 1  # example 1
assert sol.minimizeMax([4,2,1,2], 1) == 0  # example 2

# No pairs needed
assert sol.minimizeMax([1,2,3,4], 0) == 0  # empty pairing set

# Already identical values
assert sol.minimizeMax([5,5,5,5], 2) == 0  # all zero differences

# Single possible pair
assert sol.minimizeMax([1,100], 1) == 99  # only one pair available

# Sorted input
assert sol.minimizeMax([1,2,3,4,5,6], 2) == 1  # optimal adjacent pairing

# Large gaps
assert sol.minimizeMax([1,10,20,30], 1) == 9  # smallest achievable gap

# Multiple duplicate values
assert sol.minimizeMax([1,1,1,2,2,2], 3) == 1  # forced to include one larger pair

# Odd length array
assert sol.minimizeMax([1,3,6,19,20], 2) == 2  # careful pair selection required

# Maximum pairing count
assert sol.minimizeMax([1,2,3,4], 2) == 1  # every element used

# Large repeated blocks
assert sol.minimizeMax([1,1,1,100,100,100], 3) == 99  # unavoidable large pair

Test	Why
`[10,1,2,7,1,3], p=2`	Validates the main example
`[4,2,1,2], p=1`	Tests zero-difference pairing
`[1,2,3,4], p=0`	Ensures empty pairing returns zero
`[5,5,5,5], p=2`	Tests all duplicate values
`[1,100], p=1`	Smallest nontrivial input
`[1,2,3,4,5,6], p=2`	Confirms adjacent greedy pairing
`[1,10,20,30], p=1`	Tests sparse distributions
`[1,1,1,2,2,2], p=3`	Forces use of larger differences
`[1,3,6,19,20], p=2`	Tests non-obvious optimal choices
`[1,2,3,4], p=2`	Uses all elements
`[1,1,1,100,100,100], p=3`	Demonstrates unavoidable large maximum

Edge Cases

One important edge case occurs when p = 0. In this situation, no pairs are required, so the maximum difference over an empty set is defined as zero. A careless implementation might still attempt binary search or pairing logic unnecessarily. The implementation handles this immediately with an early return.

Another critical case involves duplicate values. Arrays like:

[2,2,2,2]

allow zero-difference pairs. Some implementations accidentally skip optimal duplicate pairings or mishandle equality comparisons. The greedy feasibility check correctly uses <= max_diff, ensuring equal values are paired when allowed.

A third important edge case occurs when the array contains large gaps between values. For example:

[1,100,200,300]

Choosing pairs incorrectly can quickly produce unnecessarily large maximum differences. Sorting and adjacent greedy pairing ensure the smallest possible local differences are always prioritized.

A subtle edge case appears when the array length is odd. Since not every element must be used, the algorithm must correctly skip elements when beneficial. The greedy scan naturally handles this because it only forms a pair when doing so satisfies the current maximum difference constraint.

Finally, arrays with maximum constraints require efficiency. Since n can be 100000, quadratic dynamic programming or exhaustive pairing would time out. The binary search plus greedy feasibility strategy guarantees acceptable performance even at the largest input sizes.

LeetCode 2616 - Minimize the Maximum Difference of Pairs

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Sort the array

Binary Search Iterations

Feasibility Check for mid = 1

Example 2

Step 1: Sort the array

Binary Search

Feasibility Check for mid = 0

Complexity Analysis

Test Cases

Edge Cases

Feasibility Check for `mid = 1`

Feasibility Check for `mid = 0`