Minimize Maximum Pair Sum in Array

Intuition

If a large value is paired with another large value, their sum spikes the maximum. To flatten the peaks, each large value should absorb a small partner. Sorting lets us pair the smallest with the largest, the next smallest with the next largest, and so on. This balancing act pushes every pair sum toward the average, and the maximum among these balanced pairs is provably the smallest achievable maximum.

Algorithm walkthrough

1. 1Sort the array in non-decreasing order.
2. 2Place one pointer at the start and one at the end of the sorted array.
3. 3Add the values at the two pointers to form a pair sum and update the running maximum.
4. 4Move the pointers toward the center and repeat until they cross.
5. 5The running maximum is the minimized maximum pair sum.

Implementation

from typing import List

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        best = 0
        for i in range(n // 2):
            best = max(best, nums[i] + nums[n - 1 - i])
        return best