Problem Statement in English

You’re 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.

Approach

To have the least possible sum for the maximum element in the list, we need to pair the smallest element with the largest element, the second smallest with the second largest, and so on. This way, we can ensure that the sums of the pairs are balanced and the maximum pair sum is minimized.

So that’s what we do!

We first sort the array. Then, we use two pointers: one starting at the beginning (the smallest element) and the other at the end (the largest element). We calculate the sum of the elements at these two pointers, update our result if this sum is greater than our current maximum pair sum, and then move the pointers inward. We repeat this process until all elements are paired.

Then we return the maximum pair sum we found.

And we’re done!

Solution in Python


class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()

        res = 0

        r = len(nums) - 1

        for l in range(len(nums)):
            res = max(res, nums[l] + nums[r])
            r -= 1

        return res

Complexity

  • Time: $O(n \log n)$
    Since we sort the array of size n.

  • Space: $O(1)$
    Since we use only constant extra space.

And we are done.