Minimize Maximum Pair Sum in Array

Medium

Asked by:

+1

18 views

Topics:

ArraysTwo PointersGreedy Algorithms

The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.

Return the minimized maximum pair sum after optimally pairing up the elements.

Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

Example 2:

Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

Constraints:

n == nums.length
2 <= n <= 10⁵
n is even.
1 <= nums[i] <= 10⁵

Minimize Maximum Pair Sum in Array

Medium

Asked by:

18 views

Topics:

ArraysTwo PointersGreedy Algorithms

The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.

Return the minimized maximum pair sum after optimally pairing up the elements.

Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

Example 2:

Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

Constraints:

n == nums.length
2 <= n <= 10⁵
n is even.
1 <= nums[i] <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values (range and data type) of the integers in the input array?
Can the input array be empty or contain an odd number of elements?
Are there any constraints on the length of the input array `nums`?
If there are multiple ways to minimize the maximum pair sum, is any valid pairing acceptable?
By 'pair sum' do you mean the sum of two elements at different indices, or could an element be paired with itself?

Brute Force Solution

Approach

The goal is to pair up numbers from a collection so that the largest sum from any of the pairs is as small as possible. The brute force method involves considering every single possible pairing of the numbers, no matter how inefficient it might be.

Here's how the algorithm would work step-by-step:

Take the collection of numbers and start by picking any two numbers to form the first pair.
Then, from the remaining numbers, pick any two to form the second pair.
Continue this process of picking pairs until all numbers have been assigned to a pair.
Calculate the sum of each pair you've created.
Find the largest sum among all the pairs you've created in this particular pairing arrangement.
Repeat this entire process of pairing the numbers in a different way.
Do this until you have tried every possible way to group the numbers into pairs.
Finally, compare the largest sum from each of the pairing arrangements you tried, and choose the arrangement where the largest sum is the smallest.

Code Implementation

def minimize_maximum_pair_sum_brute_force(numbers):
    import itertools

    number_of_elements = len(numbers)
    if number_of_elements % 2 != 0:
        return -1

    minimum_maximum_pair_sum = float('inf')

    # Generate all possible permutations
    for permutation in itertools.permutations(numbers):
        maximum_pair_sum_for_permutation = 0
        
        # Iterate through the permutation to form pairs and calculate sums
        for i in range(0, number_of_elements, 2):
            pair_sum = permutation[i] + permutation[i+1]

            # Keep track of the maximum pair sum for this permutation
            maximum_pair_sum_for_permutation = max(maximum_pair_sum_for_permutation, pair_sum)

        # Compare with overall minimum maximum pair sum
        minimum_maximum_pair_sum = min(minimum_maximum_pair_sum, maximum_pair_sum_for_permutation)

    return minimum_maximum_pair_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n!) – The described brute force approach considers all possible pairings of n numbers. Generating all possible pairings involves considering all permutations and then accounting for the fact that the order within a pair and the order of the pairs themselves don't matter. This is related to factorials. The dominant factor in the complexity arises from the number of ways to arrange the n elements for pairing which is related to n!. The complete analysis is significantly more complex involving divisions by 2 for pair ordering and factorial(n/2) for pair arrangement ordering but is still bounded by O(n!).

Space Complexity

O(1) – The plain English explanation describes a brute-force approach that explores every possible pairing. Although the process is computationally intensive, the space complexity is dominated by the variables needed to track the current pairing and the maximum pair sum found so far. The algorithm doesn't create additional data structures that grow with the input size N. Therefore, the auxiliary space used remains constant, resulting in O(1) space complexity.

Optimal Solution

Approach

The best way to solve this is to pair the smallest number with the largest number, the second smallest with the second largest, and so on. This strategy ensures we minimize the largest sum among all the pairs. By intelligently pairing the extremes, we avoid unnecessarily large individual pair sums that would otherwise increase the maximum value we are trying to minimize.

Here's how the algorithm would work step-by-step:

First, arrange the numbers from smallest to largest.
Then, create pairs by combining the smallest number with the largest number.
Continue pairing the next smallest with the next largest until all numbers are paired.
For each pair, calculate the sum.
Identify the largest sum among all the pairs. This largest sum is the answer you are looking for.

Code Implementation

def minimize_maximum_pair_sum(numbers):
    numbers.sort()

    left_index = 0
    right_index = len(numbers) - 1
    maximum_pair_sum = 0

    # Iterate until all numbers are paired
    while left_index < right_index:
        # Pair smallest and largest remaining numbers
        current_pair_sum = numbers[left_index] + numbers[right_index]

        # Update maximum_pair_sum if current pair's sum is larger
        maximum_pair_sum = max(maximum_pair_sum, current_pair_sum)

        left_index += 1
        right_index -= 1

    # The maximum pair sum among all pairs
    return maximum_pair_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input array of size n, which typically takes O(n log n) time using efficient algorithms like merge sort or quicksort. The subsequent pairing and sum calculation involves iterating through the sorted array once, which takes O(n) time. Since O(n log n) grows faster than O(n) as n increases, the overall time complexity is determined by the sorting step. Therefore, the time complexity of the provided solution is O(n log n).

Space Complexity

O(1) – The algorithm primarily sorts the input array in place. While the sorting algorithm itself might use auxiliary space depending on the specific sorting implementation (e.g., merge sort would use O(N)), the explanation doesn't specify the sorting algorithm. Apart from sorting, the steps only involve calculating sums and comparing them, which can be done using a few constant space variables to keep track of the current pair sum and the maximum pair sum encountered so far. Therefore, the auxiliary space complexity is O(1), assuming the sorting is done in-place or its auxiliary space is not considered within the scope of the provided plain english instructions.

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 or throw an exception to indicate invalid input as no pairs can be formed.
Array with exactly two elements	Return the sum of the two elements directly, as it's the only possible pair sum.
Array with all identical values	The sorting approach will group identical values together, correctly pairing them to minimize the maximum pair sum.
Array containing negative numbers	The sorting approach will handle negative numbers correctly by placing them in the appropriate order.
Array containing zero	The sorting algorithm will handle zero correctly.
Integer overflow in sum calculation	Use a data type with a larger range (e.g., long) to store the sum if there is a possibility of integer overflow.
Large input array	Ensure the sorting algorithm used has a time complexity of O(n log n) to maintain efficiency.
Array contains maximum and minimum integer values	The sorting algorithm must handle both the largest and smallest possible integers in the programming language.