1877. Minimize Maximum Pair Sum in Array

MediumGreedyArrayTwo PointersSorting
Leetcode Link

Problem Description

In this problem, we are given an array nums with an even number of elements. Our task is to form pairs of elements from this array. Each pair is a combination of two items from the array (a, b), and the pair sum is defined as a + b. After pairing all the elements, there will be many pair sums, and we want to find the pair with the maximum sum, which we'll call the maximum pair sum.

However, the twist is that we have to pair the elements in such a way that this maximum pair sum is as small as possible compared to all different pairings. That is, we are trying to minimize the maximum. The output of the function will be this minimized maximum pair sum.

For example, if the array is [3, 5, 2, 3], there are multiple ways to form pairs, but if we pair 3 with 5 and 2 with 3, we get pairs (3,5) and (2,3), which results in pair sums 8 and 5. Here, 8 is the maximum pair sum, and there is no way to pair these elements to get a lower maximum pair sum, so the output will be 8.

Intuition

To arrive at the solution, we need to use a greedy approach. The greedy insight for minimizing the maximum pair sum is to pair the smallest elements available with the largest ones. If we were to pair large elements with other large elements, it would definitely increase the maximum pair sum more than necessary.

To implement this strategy, we first sort the array. By sorting, we can easily access the smallest and the largest elements and pair them together. Specifically, we pair the first element (the smallest after sorting) with the last element (the largest), the second element with the second to last, and so on.

Once we have paired the numbers in this way, all that remains is to find the maximum pair sum from these optimal pairs. This can be done by looking at the pair sums resulting from each first half element and its corresponding second half partner. We take the maximum of these sums to get the minimized maximum pair sum.

The intuition for the solution can be summarized as follows:

  • Sort the array to efficiently pair smallest and largest elements.
  • Pair elements from the start of the array with elements from the end.
  • The maximum pair sum from these pairs will be the minimized maximum.

By following this approach, we ensure that we do not have any unnecessarily large pair sums, while still adhering to the constraints of the problem.

Learn more about Greedy, Two Pointers and Sorting patterns.

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

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

Solution Approach

The provided solution approach leverages two well-known concepts: sorting and the greedy method.

Here's the step-by-step implementation of the solution:

  1. Sort the Array: We begin by sorting the array nums in ascending order. This puts the smallest numbers at the start of the array and the largest numbers at the end.

    1nums.sort()

    Sorting is essential because it allows us to directly access the smallest and largest numbers without having to search for them, thereby enabling the next steps of the greedy approach. The built-in .sort() method in Python is utilized, which sorts the list in-place.

  2. Pair Smallest with Largest: Once the array is sorted, we iterate through the first half of the array. For each element x in the first half, we find its optimal pair by selecting the element at the symmetrical position in the second half of the array (nums[n - i - 1], where i is the index of x and n is the total number of elements in the array).

    Using the greedy insight, the smallest element is paired with the largest, the second smallest with the second largest, and so on. This is achieved by iterating over the first half of the sorted array and finding the corresponding element in the second half.

  3. Compute and Return Maximum Pair Sum: For each such pair, we compute the pair sum and find the maximum among all these sums. This maximum is the minimized maximum pair sum we want to return.

    1return max(x + nums[n - i - 1] for i, x in enumerate(nums[: n >> 1]))

    Here, the use of n >> 1 is a bit manipulation trick that is equivalent to integer division by 2, effectively finding the midpoint of the array. The enumerate function is used in a loop to get both the index i and the value x of the elements from the first half of nums. With these, we calculate the pair sums and pass them to the max() function which finds the maximum pair sum, fulfilling our original goal.

This approach is incredibly efficient because by sorting the array only once, we are then able to pair elements in a single pass without extra loops or complex logic. The overall time complexity is dominated by the sorting step, which is typically O(n log n) where n is the length of the array, making this solution scalable and effective for large inputs.

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

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the array [4, 1, 2, 7].

  1. Sort the Array: As a first step, we sort the array nums in ascending order. This will arrange the numbers so that we have the smallest elements at the start and the largest at the end.

    1Original array: [4, 1, 2, 7]
2Sorted array: [1, 2, 4, 7]

  2. Pair Smallest with Largest: After sorting, we pair the first element in the array with the last, and the second element with the second to last, and so on. This is done using the greedy approach, to minimize the maximum pair sum.

    Pairs are as follows:

    1Pair 1: (1, 7)
2Pair 2: (2, 4)

    These pairs are made by pairing the first half of the sorted array [1, 2] with the reversed second half [7, 4].

  3. Compute and Return Maximum Pair Sum: We compute the pair sum for each pair and identify the maximum of those sums.

    1Pair sum 1: 1 + 7 = 8
2Pair sum 2: 2 + 4 = 6

    The maximum of these sums is 8, which is the answer.

The outcome of this approach is that the array [1, 2, 4, 7] yields a minimized maximum pair sum of 8. By using this greedy method and sorting beforehand, we ensured that we didn't unnecessarily increase the maximum pair sum and met our goal in an efficient manner.

Solution Implementation

1class Solution:
2    def minPairSum(self, nums: List[int]) -> int:
3        # Sort the list in non-decreasing order
4        nums.sort()
5
6        # Get the length of the list
7        n = len(nums)
8
9        # Calculate the maximum pair sum. 
10        # The ith smallest number is paired with the ith largest number to minimize the maximum pair sum.
11        # This is done for the first half of the sorted list, then the maximum of these sums is found.
12        max_pair_sum = max(x + nums[n - i - 1] for i, x in enumerate(nums[: n // 2]))
13
14        # Return the maximum pair sum
15        return max_pair_sum
16
1class Solution {
2    public int minPairSum(int[] nums) {
3        // Sort the array to have numbers in ascending order.
4        Arrays.sort(nums);
5
6        // Initialize a variable to store the maximum pair sum found so far.
7        int maxPairSum = 0;
8
9        // Calculate the number of pairs - half the length of the array
10        int numPairs = nums.length / 2; 
11
12        // Iterate over the first half of the sorted array to form pairs with elements from both ends
13        for (int i = 0; i < numPairs; i++) {
14            // Calculate the sum of the current pair
15            int currentPairSum = nums[i] + nums[nums.length - i - 1];
16          
17            // Update maxPairSum if the current pair sum is greater than the maxPairSum found so far
18            maxPairSum = Math.max(maxPairSum, currentPairSum);
19        }
20
21        // Return the maximum pair sum found
22        return maxPairSum;
23    }
24}
25
1#include <vector>  // Required for using the vector container.
2#include <algorithm>  // Required for the sort() and max() functions.
3
4class Solution {
5public:
6    // Function to find the minimum possible maximum pair sum in an array.
7    int minPairSum(vector<int>& nums) {
8        // Sort the array in non-decreasing order.
9        sort(nums.begin(), nums.end());
10
11        // Initialize the variable that will store the minimum possible maximum pair sum.
12        int minMaxPairSum = 0;
13
14        // Calculate the size of the array.
15        int n = nums.size();
16
17        // Iterate over the first half of the array.
18        for (int i = 0; i < n / 2; ++i) {
19            // For each element in the first half, pair it with the corresponding
20            // element in the second half, and then update minMaxPairSum with the maximum 
21            // sum of these pairs seen so far.
22            minMaxPairSum = max(minMaxPairSum, nums[i] + nums[n - i - 1]);
23        }
24
25        // Return the minimum possible maximum pair sum found.
26        return minMaxPairSum;
27    }
28};
29
1/**
2 * Calculates the min pair sum of an array when paired optimally.
3 * Pairs are formed such that the largest and smallest numbers are paired
4 * and the resulting max pair sum is the smallest possible.
5 * 
6 * @param {number[]} nums - The input array of numbers.
7 * @return {number} - The minimum possible maximum pair sum.
8 */
9function minPairSum(nums: number[]): number {
10    // Sort the array in non-decreasing order.
11    nums.sort((a, b) => a - b);
12
13    let maxPairSum = 0; // Initialize the maximum pair sum as 0.
14    const arrayLength = nums.length; // Get the length of the array.
15
16    // Loop over the first half of the array to create pairs.
17    for (let i = 0; i < arrayLength >> 1; ++i) {
18        // Calculate the current pair sum.
19        const currentPairSum = nums[i] + nums[arrayLength - 1 - i];
20
21        // Update the maximum pair sum if current is larger.
22        maxPairSum = Math.max(maxPairSum, currentPairSum);
23    }
24
25    // Return the maximum pair sum after pairing all elements optimally.
26    return maxPairSum;
27}
28
29// Example usage:
30// const nums = [3, 5, 2, 3];
31// const result = minPairSum(nums);
32// console.log(result); // Output would be 7.
33
Not Sure What to Study? Take the 2-min Quiz๏ผš

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

Time and Space Complexity

Time Complexity:

The main operations in the code include:

  1. Sorting the list: nums.sort(), which usually has a time complexity of O(n log n), where n is the length of the list.
  2. A list comprehension to calculate the pair sums and find the maximum: This operation goes through roughly half of the sorted list, leading to a complexity of O(n/2), which simplifies to O(n).

Combining these, the overall time complexity is dominated by the sort operation, thus it is O(n log n).

Space Complexity:

The space complexity is determined by:

  1. The sorted nums list does not require additional space as the sort is done in-place.
  2. The list comprehension creates a generator, which doesn't create a new list; it just iterates through the existing items.

Therefore, aside from the input list, the code uses a fixed amount of space, giving us a space complexity of O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

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

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

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 ๐Ÿ‘จโ€๐Ÿซ