2616. Minimize the Maximum Difference of Pairs
Problem Description
In this problem, you are given an array of integers nums
and an integer p
. Your task is to find p
pairs of indices (let's denote each pair as (i, j)
) in the array such that each index is used only once across all pairs and the maximum difference of the values at these indices is as small as possible. The difference for a pair (i, j)
is defined as the absolute value of nums[i] - nums[j]
. You need to determine the smallest maximum difference possible amongst all these p
pairs.
To summarize:
- Indices should not be used more than once.
- The maximum difference among the pairs should be minimized.
- The difference is calculated as the absolute difference of numbers at the given indices.
- The goal is to find the minimum of the maximum differences.
Intuition
The key to solving this problem lies in realizing that if a certain max difference x
can satisfy the conditions (allowing for the formation of p
pairs), any max difference larger than x
would also satisfy the conditions. This gives us a hint that binary search can be used, as we're dealing with a monotonically non-decreasing condition. We aim to find the smallest x
that allows us to form p
pairs with differences less than or equal to x
.
To simplify the search, we first sort the array nums
. Sorting allows us to consider pairs in a sequence where we can readily calculate differences between adjacent elements and check if the difference fits our current guess x
. We then apply binary search over the potential differences, starting from 0 up to the maximum possible difference in the sorted array, which is nums[-1] - nums[0]
.
We use a greedy approach to check if a certain maximum difference x
is possible: we iterate through the sorted array and greedily form pairs with a difference less than or equal to x
. If an adjacent pair fits the condition, we count it as one of the p
pairs and skip the next element since it's already paired. If the difference is too large, we move to the next element and try again. Our check passes if we can form at least p
pairs this way.
By combining binary search to find the minimum possible x
with the greedy pairing strategy, we efficiently arrive at the minimum maximum difference among all the p
pairs.
Learn more about Greedy and Binary Search patterns.
Solution Approach
The solution follows a binary search approach combined with a greedy strategy to determine the minimum maximum difference that allows for the existence of p
index pairs with that maximum difference.
Here are the steps of the implementation:
-
Sorting: First, we sort the array
nums
in non-decreasing order. This is done to simplify the process of finding pairs of elements with the smallest possible difference. -
Binary Search: We perform binary search on the range of possible differences, starting from
0
tonums[-1] - nums[0]
. We use binary search because the possibility of findingp
pairs is a monotonically non-decreasing function of the difference,x
. If we can findp
pairs for a givenx
, we can also findp
pairs for any larger value ofx
. We aim to find the smallest suchx
that works. -
Greedy Pairing: For a guess
x
in the binary search, we apply a greedy method to check if we can formp
pairs with differences less than or equal tox
. We iterate through the sortednums
and for the current indexi
, ifnums[i + 1] - nums[i]
is less than or equal tox
, we count this as a valid pair (nums[i]
,nums[i + 1]
) and increment our pairs count (cnt
). We then skip the next element by incrementingi
by 2, because we can't reuse indices. Ifnums[i + 1] - nums[i]
is greater thanx
, it doesn't form a valid pair, and we just incrementi
by 1 to try the next element with its adjacent one. -
Check Function: The
check
function is the core of this greedy application. It takes a differencediff
as its argument and returns a boolean, indicating whether it is possible to find at leastp
pairs with a maximum difference ofdiff
or less. -
Binary Search with Custom Checker: Using
bisect_left
from thebisect
module, we find the smallestx
that makes thecheck
function returnTrue
. Thebisect_left
function is given a range and a customkey
function, which is the aforementionedcheck
function. It effectively applies binary search to find the leftmost point in the range where thecheck
condition is met, returning the value ofx
that minimizes the maximum difference. -
Result: The result of the binary search gives us the minimum value of
x
, the maximum difference, that allows us to form at leastp
pairs, solving the problem.
Essentially, the binary search narrows down the search space for the maximum difference while the greedy approach checks its viability, ensuring an efficient and correct solution to the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach:
Suppose we have an array nums = [1, 3, 6, 19, 20]
and we need to find p = 2
pairs such that we minimize the maximum difference of the values at these index pairs.
Step 1: Sorting
We sort the array, although nums
is already sorted in this case: [1, 3, 6, 19, 20]
.
Step 2: Binary Search
We will perform a binary search for the smallest maximum difference on the range from 0
to nums[-1] - nums[0]
, which is 20 - 1 = 19
.
Step 3: Greedy Pairing Using the Check Function (Example)
Let's pick a mid-value from our binary search range, say x = 9
.
We start with the first index i = 0
:
nums[i + 1] - nums[i]
equals3 - 1 = 2
, which is less thanx
; we can form a pair (1, 3). We move toi = 2
.
Now at i = 2
:
nums[i + 1] - nums[i]
equals19 - 6 = 13
, which is greater thanx
; the pair (6, 19) does not work. We move toi = 3
.
At i = 3
, we cannot pair 19
because there are no more elements to compare with that can form a valid pair with a difference less than or equal to x
. We have only been able to form 1 pair.
Since we cannot form p = 2
pairs with x = 9
, the maximum difference x
must be higher. The binary search will continue adjusting the value of x
until we can find the minimum x
that allows forming p = 2
pairs.
Step 4: Binary Search Continues
Let's try with a larger x
, say x = 10
. Now we perform the greedy pairing check again:
- For
i = 0
: The difference is2 < x
; pair (1, 3). Incrementi
by 2 toi = 2
. - For
i = 2
: The difference is13 > x
; we cannot pair (6, 19). Incrementi
by 1 toi = 3
. - For
i = 3
: The difference is20 - 19 = 1 < x
; pair (19, 20). Incrementi
by 2 toi = 5
.
We formed p = 2
pairs with a max difference x = 10
, which are (1, 3) and (19, 20).
Since we can form the required p
pairs with x = 10
and we could not do so with x = 9
, the smallest possible maximum difference we could form the pairs with is 10
.
Step 5: Result
Through the greedy and binary search methods described, we have found the smallest maximum difference is 10
for forming p = 2
pairs given the array nums = [1, 3, 6, 19, 20]
.
The binary search determines that the correct value x
for the minimum maximum difference cannot be less than 10
if we are to form the required number of pairs, while the greedy strategy confirms the feasibility of x
by actually attempting to form the pairs. This example demonstrates both the complexity and the effectiveness of using binary search with a greedy pairing strategy in solving such problems.
Solution Implementation
1from bisect import bisect_left
2from typing import List
3
4class Solution:
5 def minimizeMax(self, nums: List[int], p: int) -> int:
6 # Helper function to check if it is possible to have 'diff' as the maximum difference
7 # of at least 'p' pairs after removing some pairs from 'nums'.
8 def is_possible(diff: int) -> bool:
9 pairs_count = 0 # Count of valid pairs
10 i = 0 # Index to iterate through 'nums'
11
12 # Loop through the numbers and determine if we can form enough pairs
13 while i < len(nums) - 1:
14 # If the difference between the current pair is less than or equal to 'diff'
15 if nums[i + 1] - nums[i] <= diff:
16 pairs_count += 1 # Acceptable pair, increment the count
17 i += 2 # Skip the next element as it has been paired up
18 else:
19 i += 1 # Move to the next element to find a pair
20
21 # Return True if we have enough pairs, otherwise False
22 return pairs_count >= p
23
24 # Sort the input array before running the binary search algorithm
25 nums.sort()
26
27 # Use binary search to find the minimum possible 'diff' such that at least 'p' pairs
28 # have a difference of 'diff' or less. The search range is from 0 to the maximum
29 # difference in the sorted array.
30 min_possible_diff = bisect_left(range(nums[-1] - nums[0] + 1), True, key=is_possible)
31
32 return min_possible_diff
33
1class Solution {
2 public int minimizeMax(int[] nums, int pairsToForm) {
3 // Sort the array to prepare for binary search
4 Arrays.sort(nums);
5 // Number of elements in the array
6 int arrayLength = nums.length;
7 // Initialize binary search bounds
8 int left = 0;
9 int right = nums[arrayLength - 1] - nums[0] + 1;
10
11 // Perform binary search to find the minimum maximum difference
12 while (left < right) {
13 int mid = (left + right) >>> 1; // Mid-point using unsigned bit-shift to avoid overflow
14 // If enough pairs can be formed with this difference, go to left half
15 if (countPairsWithDifference(nums, mid) >= pairsToForm) {
16 right = mid;
17 } else { // Otherwise, go to right half
18 left = mid + 1;
19 }
20 }
21 // Minimum maximum difference when the correct number of pairs are formed
22 return left;
23 }
24
25 private int countPairsWithDifference(int[] nums, int maxDifference) {
26 int pairCount = 0; // Count pairs with a difference less than or equal to maxDifference
27 for (int i = 0; i < nums.length - 1; ++i) {
28 // If a valid pair is found, increase count
29 if (nums[i + 1] - nums[i] <= maxDifference) {
30 pairCount++;
31 i++; // Skip the next element as it's already paired
32 }
33 }
34 return pairCount;
35 }
36}
37
1#include <vector>
2#include <algorithm> // to use sort function
3
4class Solution {
5public:
6 // Function to minimize the maximum difference between pairs after 'p' pairs have been removed
7 int minimizeMax(std::vector<int>& nums, int pairsToRemove) {
8 // First, sort the array to easily identify and remove pairs with minimal differences
9 std::sort(nums.begin(), nums.end());
10
11 // Store the number of elements in 'nums'
12 int numCount = nums.size();
13
14 // Initialize the binary search bounds for the minimal max difference
15 int leftBound = 0, rightBound = nums[numCount - 1] - nums[0] + 1;
16
17 // Lambda function to check if 'diff' is sufficient to remove 'pairsToRemove' pairs
18 auto check = [&](int diff) -> bool {
19 int pairsCount = 0; // Keep track of the number of pairs removed
20
21 // Iterate over the sorted numbers and attempt to remove pairs
22 for (int i = 0; i < numCount - 1; ++i) {
23 // If the difference between a pair is less than or equal to 'diff'
24 if (nums[i + 1] - nums[i] <= diff) {
25 pairsCount++; // Increment the count of removed pairs
26 i++; // Skip the next element as it's part of a removed pair
27 }
28 }
29
30 // True if enough pairs can be removed, false otherwise
31 return pairsCount >= pairsToRemove;
32 };
33
34 // Perform binary search to find the minimal max difference
35 while (leftBound < rightBound) {
36 int mid = (leftBound + rightBound) >> 1; // Equivalent to average of the bounds
37 if (check(mid)) {
38 // If 'mid' allows removing enough pairs, look for a potentially lower difference
39 rightBound = mid;
40 } else {
41 // Otherwise, increase 'mid' to allow for more pairs to be removed
42 leftBound = mid + 1;
43 }
44 }
45
46 // The left bound will be the minimal max difference after the binary search
47 return leftBound;
48 }
49};
50
1// Define the function to minimize the maximum difference between pairs after 'pairsToRemove' pairs have been removed
2function minimizeMax(nums: number[], pairsToRemove: number): number {
3 // Sort the array to easily identify and remove pairs with minimal differences
4 nums.sort((a, b) => a - b);
5
6 // Store the number of elements in 'nums'
7 let numCount: number = nums.length;
8
9 // Initialize the binary search bounds for the minimal max difference
10 let leftBound: number = 0, rightBound: number = nums[numCount - 1] - nums[0] + 1;
11
12 // Define a checker function to check if 'diff' is sufficient to remove 'pairsToRemove' pairs
13 const check = (diff: number): boolean => {
14 let pairsCount: number = 0; // Keep track of the number of pairs removed
15
16 // Iterate over the sorted numbers and attempt to remove pairs
17 for (let i = 0; i < numCount - 1; ++i) {
18 // If the difference between a pair is less than or equal to 'diff'
19 if (nums[i + 1] - nums[i] <= diff) {
20 pairsCount++; // Increment the count of removed pairs
21 i++; // Skip the next element as it's part of a removed pair
22 }
23 }
24
25 // Return true if enough pairs can be removed, false otherwise
26 return pairsCount >= pairsToRemove;
27 };
28
29 // Perform binary search to find the minimal max difference
30 while (leftBound < rightBound) {
31 const mid: number = leftBound + Math.floor((rightBound - leftBound) / 2); // Compute the average of the bounds
32
33 if (check(mid)) {
34 // If 'mid' allows removing enough pairs, look for a potentially lower difference
35 rightBound = mid;
36 } else {
37 // Otherwise, increase 'mid' for the possibility to remove more pairs
38 leftBound = mid + 1;
39 }
40 }
41
42 // Return the left bound as the minimal max difference after the binary search completes
43 return leftBound;
44}
45
Time and Space Complexity
The given code snippet is designed to minimize the maximum difference between consecutive elements in the array after performing certain operations. It uses a binary search mechanism on the range of possible differences and a greedy approach to check for the validity of a specific difference.
The time complexity of the code is O(n * (log n + log m))
, where n
is the length of the array nums
, and m
is the difference between the maximum and minimum values in the array nums
. The sorting operation contributes O(n log n)
, whereas the binary search contributes O(log m)
. During each step of the binary search, the check
function is called, which takes O(n)
.
The space complexity of the code is O(1)
, which indicates that the space required does not depend on the size of the input array nums
. Aside from the input and the sorted array in place, the algorithm uses a fixed amount of additional space.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we