Minimize the Maximum Difference of Pairs - Video Solutions
Minimize the Maximum Difference of Pairs - Leetcode 2616 - Python
Minimize the Maximum Difference of Pairs - Video Solution
Watch 10 video solutions for Minimize the Maximum Difference of Pairs, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by NeetCodeIO has 23,442 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |