Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Pair the largest remaining value with the smallest to limit its sum. This is safe by exchange: if the smallest and largest were in separate pairs, pairing them together and pairing their former partners cannot increase the larger of those two pair sums. Repeating the exchange yields the greedy pairing.

Approach

Sort the even-length array. Pair the first value with the last, the second with the second-last, and so on. Track the maximum sum among these pairs and return it. Every element is used once, and the exchange argument shows no other pairing can achieve a lower maximum.

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        res = -inf

        for i in range(n // 2):
            res = max(res, nums[i] + nums[-i -1])

        return res

Complexity analysis

Let n = nums.length. Time: O(n log n) for sorting, followed by a linear pairing scan. Auxiliary space: up to O(n) for the language runtime's sort workspace.