Minimize the Maximum Difference of Pairs - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given an integer array and a number p. The task is to create p disjoint pairs such that the maximum absolute difference among those pairs is minimized. Each element can be used at most once, so the challenge is choosing pairs carefully to keep the worst difference as small as possible.
Approach 1: Sorting with Greedy Pairing (Binary Search Optimization) (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
The key idea is that once the array is sorted, close numbers naturally produce smaller differences. After sorting, use binary search on the answer — the maximum allowed difference. For a candidate difference d, greedily scan the array and pair adjacent elements whenever their difference is ≤ d. Each time a valid pair is formed, skip both indices and continue. If you can form at least p pairs, the difference d is feasible, so search for a smaller value.
This works because feasibility is monotonic: if a maximum difference d works, any larger value also works. Sorting the array ensures the greedy step always picks the smallest possible differences first, which maximizes the number of valid pairs. Binary search narrows the optimal maximum difference efficiently.
Approach 2: Priority Queue to Manage Differences (Time: O(n log n), Space: O(n))
Another strategy computes candidate pair differences and processes them using a greedy strategy backed by a priority queue. After sorting the array, push adjacent pair differences into a min-heap. Repeatedly extract the smallest difference and select the pair if neither index has been used yet. Continue until p pairs are formed.
The heap ensures the smallest differences are processed first, which tends to minimize the maximum difference among selected pairs. However, managing index conflicts and maintaining the heap introduces additional overhead compared with the binary-search feasibility check. While still valid, this approach is usually less efficient in practice.
Recommended for interviews: The sorting + binary search approach is what interviewers typically expect. It demonstrates strong understanding of monotonic search space reduction and greedy validation. A brute-force pairing idea shows initial reasoning, but the optimized solution proves you can combine binary search with a greedy feasibility check to reach an optimal O(n log n) solution.
Approach 1: Approach 1: Sorting with Greedy Pairing
The primary idea of this approach is to first sort the array so that elements which are closer in value are positioned adjacent to each other. This can help in reducing the maximum difference within selected pairs when paired greedily. Once sorted, the greedy approach looks to form pairs consecutively and calculate the differences. By doing so repetitively and minimizing the maximum difference, an optimal solution is achieved.
This C code uses quicksort to sort the input array, followed by a binary search to find the minimal maximum difference possible. The binary search checks for possible maximum differences by counting how many pairs can be formed with that maximum difference.
Complexity
Time Complexity: O(n log n), dominated by the sorting step.
Space Complexity: O(1), if we ignore the space used by the sorting algorithm.
Approach 2: Approach 2: Priority Queue to Manage Differences
This approach also begins by sorting the input array, but tackles the problem by employing a min-heap (priority queue). The idea is to manage the smallest differences available and decide pairs greedily based on this. The heap helps efficiently remove and manage differences, ensuring that the maximum difference in the formed pairs remains minimal.
In this Python code, we sort the array and then push all possible adjacent differences into a min-heap. We then pop the smallest difference and form pairs while keeping track of used elements until the required number of pairs is formed.
Complexity
Time Complexity: O(n log n) due to the heap operations.
Space Complexity: O(n) for holding the differences.
Approach 3: 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 geq p, then such p pairs exist; otherwise, they do not.
The time complexity is O(n times (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).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting with Greedy Pairing | Time Complexity: O(n log n), dominated by the sorting step. |
| Approach 2: Priority Queue to Manage Differences | Time Complexity: O(n log n) due to the heap operations. |
| Binary Search + Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Greedy Pairing with Binary Search | O(n log n) | O(1) auxiliary | Best general solution; minimizes maximum difference efficiently using monotonic feasibility |
| Priority Queue on Pair Differences | O(n log n) | O(n) | Useful when exploring smallest pair differences first or demonstrating heap-based greedy selection |
Video Solution
Minimize the Maximum Difference of Pairs - Leetcode 2616 - Python • NeetCodeIO • 23,442 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimize the Maximum Difference of Pairs easy or hard?
Minimize the Maximum Difference of Pairs Python or Java solution
How to solve Minimize the Maximum Difference of Pairs in O(n log n)?
What is the best approach for Minimize the Maximum Difference of Pairs?
What data structure is used in Minimize the Maximum Difference of Pairs?
What is the time complexity of Minimize the Maximum Difference of Pairs?
Is Minimize the Maximum Difference of Pairs asked at Google or Amazon interviews?
Ready to solve this problem?
Practice Minimize the Maximum Difference of Pairs with our built-in code editor and test cases.
Practice on FleetCode