1877. Minimize Maximum Pair Sum in Array #

Problem #

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 <= 105
n is even.
1 <= nums[i] <= 105

Problem Summary #

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

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

Given an array nums of even length n, please divide the elements in nums into n / 2 pairs such that:

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

Return the minimized maximum pair sum under the optimal pairing scheme.

Solution Approach #

To minimize the maximum pair sum, the largest element must be paired with the smallest element; otherwise, it definitely will not be minimal. After pairing the largest element with the smallest element, the remaining second-largest element should also be paired with the second-smallest element. Following this idea, first sort the array in ascending order, then take elements from the beginning and the end in order and pair them together. The maximum value among these pair sums is the answer.

Code #

package leetcode

import "sort"

func minPairSum(nums []int) int {
	sort.Ints(nums)
	n, res := len(nums), 0
	for i, val := range nums[:n/2] {
		res = max(res, val+nums[n-1-i])
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}