MediumSortingTwo PointersGreedy

Minimize Maximum Pair Sum in Array

1 approach, code in every language

You are given an array with an even number of elements, and you must split every element into pairs so that each element belongs to exactly one pair. For any pairing, its cost is the largest sum found among all of its pairs. Different pairings can produce different largest sums.

Return the smallest possible value of that largest pair sum over all valid ways to pair the array. The intuition is to keep big values away from other big values by matching the largest element with the smallest, the second largest with the second smallest, and so on.

Example 1

Input: nums = [3,5,2,3]

Output: 7

Sorted the array is [2,3,3,5]. Pairing 2 with 5 and 3 with 3 gives sums 7 and 6, so the maximum is 7, and no pairing beats it.

Example 2

Input: nums = [3,5,4,2,4,6]

Output: 8

Sorted the array is [2,3,4,4,5,6]. The mirror pairs (2,6), (3,5), (4,4) all sum to 8, giving a maximum pair sum of 8.

Constraints

n == nums.length
2 <= n <= 10^5
n is even
1 <= nums[i] <= 10^5

Sort and Pair Ends

Sort the array, then pair each element from the front with its mirror element from the back, tracking the largest of those sums.

Loading animation…

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

1Sort the array in non-decreasing order.
2Place one pointer at the start and one at the end of the sorted array.
3Add the values at the two pointers to form a pair sum and update the running maximum.
4Move the pointers toward the center and repeat until they cross.
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

Time

O(n log n)

Space

O(1) beyond the sort

The cost is dominated by sorting; the pairing pass is a single linear scan over half the array.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free