Minimize Maximum Pair Sum

Patrick Leaton
Published: Dec. 20, 2021, 10 p.m.
Problem Description

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^5
  • n is even.
  • 1 <= nums[i] <= 10^5

 

The description was taken from https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/.

Problem Solution

#O(N(Log(N))) Time, O(1) Space
class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        max_pair = 0
       
        while left < right:
            max_pair = max(max_pair, nums[left] + nums[right])
            left += 1
            right -= 1
       
        return max_pair
 

Problem Explanation

The problem description is a bit confusing, but that's probably because the author didn't want to give the solution away.

Basically, we are to sum pairs of elements from the input array, but the maximum pair sum should be minimized and we should minimize each maximum pair sum thereafter.  This means that we shouldn't be looking to pair the two maximum numbers within each iteration, but instead, the maximum number that hasn't been paired yet with the minimum one that also hasn't been paired yet.

To achieve this, we can sort the array then utilize two pointers by setting a left pointer at the leftmost position of the array and a right one at the rightmost position.  We'll take the sum of this pair, compare that to the maximum so far, then move the pointers inward.

This pairing technique is the same as Boats to Save People.

Let's start by sorting the input array.

        nums.sort()

 

Next, we'll set our two pointers.

        left, right = 0, len(nums) - 1

 

Then we'll initialize our max pair at zero.

We could also choose to set this to negative infinity but we can also ensure that zero will be overwritten since the minimum element value from any test case will be a one, according to the problem description.

        max_pair = 0

 

While our pointers haven't overlapped, we still have values to pair.

        while left < right:

 

We'll take the sum pair of the elements at the two pointers and compare that to the maximum pair so far, updating it if greater.

            max_pair = max(max_pair, nums[left] + nums[right])

 

Next, we'll move our pointers inward.

            left += 1
            right -= 1

 

When we have our maximum, minimized pair sum, we will return it.

        return max_pair