2616. Minimize the Maximum Difference of Pairs

MediumGreedyArrayBinary Search
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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:

  1. 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.

  2. Binary Search: We perform binary search on the range of possible differences, starting from 0 to nums[-1] - nums[0]. We use binary search because the possibility of finding p pairs is a monotonically non-decreasing function of the difference, x. If we can find p pairs for a given x, we can also find p pairs for any larger value of x. We aim to find the smallest such x that works.

  3. Greedy Pairing: For a guess x in the binary search, we apply a greedy method to check if we can form p pairs with differences less than or equal to x. We iterate through the sorted nums and for the current index i, if nums[i + 1] - nums[i] is less than or equal to x, 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 incrementing i by 2, because we can't reuse indices. If nums[i + 1] - nums[i] is greater than x, it doesn't form a valid pair, and we just increment i by 1 to try the next element with its adjacent one.

  4. Check Function: The check function is the core of this greedy application. It takes a difference diff as its argument and returns a boolean, indicating whether it is possible to find at least p pairs with a maximum difference of diff or less.

  5. Binary Search with Custom Checker: Using bisect_left from the bisect module, we find the smallest x that makes the check function return True. The bisect_left function is given a range and a custom key function, which is the aforementioned check function. It effectively applies binary search to find the leftmost point in the range where the check condition is met, returning the value of x that minimizes the maximum difference.

  6. Result: The result of the binary search gives us the minimum value of x, the maximum difference, that allows us to form at least p 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example 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] equals 3 - 1 = 2, which is less than x; we can form a pair (1, 3). We move to i = 2.

Now at i = 2:

  • nums[i + 1] - nums[i] equals 19 - 6 = 13, which is greater than x; the pair (6, 19) does not work. We move to i = 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 is 2 < x; pair (1, 3). Increment i by 2 to i = 2.
  • For i = 2: The difference is 13 > x; we cannot pair (6, 19). Increment i by 1 to i = 3.
  • For i = 3: The difference is 20 - 19 = 1 < x; pair (19, 20). Increment i by 2 to i = 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
Not Sure What to Study? Take the 2-min Quiz：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Binary Search Speedrun

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫