Minimize Maximum Pair Sum in Array: Sort and Pair

LeetCode 1877, Minimize Maximum Pair Sum in Array, is a clean example of how sorting unlocks a greedy strategy. The problem asks you to pair up elements so that the largest pair sum is as small as possible. Once you see the key insight, the code is short and the logic is satisfying. It combines sorting, two pointers, and a greedy argument into one tight package.

The problem

You are given an array nums of even length n. You must pair the elements into n / 2 pairs. The pair sum of a pair (a, b) is a + b. Your goal is to minimize the maximum pair sum across all pairs.

In other words, find a way to pair every element exactly once so that the largest sum among all pairs is as small as possible.

Example: nums = [3, 5, 2, 3]. After sorting we get [2, 3, 3, 5]. If we pair (2, 5) and (3, 3), the pair sums are 7 and 6. The maximum is 7.

Could we do better? Pairing (2, 3) and (3, 5) gives sums 5 and 8, with a maximum of 8. Pairing (2, 3) and (5, 3) is the same thing. Every alternative pairing produces a maximum that is 7 or worse. So 7 is the answer.

The brute force approach

The most direct approach is to try every possible way to pair the elements and track the minimum of the maximum pair sum. For an array of length n, the number of distinct pairings is:

(n-1) * (n-3) * (n-5) * ... * 1

That is a double factorial, which grows extremely fast. For n = 20, there are already over 654 million pairings. For n = 100000 (the upper bound in this problem), brute force is out of the question.

We need a smarter approach.

The key insight: pair extremes together

Sort the array. Then pair the smallest element with the largest, the second smallest with the second largest, and so on. This greedy pairing minimizes the maximum pair sum.

Why this greedy works

The intuition is about balance. If you pair two large values together, their sum is huge and becomes the bottleneck. If you pair the largest value with the smallest, you "use up" the big number in a pair that is as small as it can be.

Here is a more precise argument. Suppose the sorted array is a[0], a[1], ..., a[n-1] where a[0] is the smallest. Consider the largest element a[n-1]. It must be paired with something. No matter what you pair it with, that pair sum is at least a[0] + a[n-1] (since a[0] is the minimum possible partner). So the maximum pair sum is at least a[0] + a[n-1].

Now look at a[n-2], the second largest. After we commit a[n-1] to pair with a[0], the best partner for a[n-2] is the next smallest available element, a[1]. The pair sum a[1] + a[n-2] is the smallest possible sum involving a[n-2].

This argument applies recursively. At each level, the largest remaining element pairs with the smallest remaining element, producing the smallest possible pair sum for that large element. The result is that all pair sums are as balanced as possible, and the maximum is minimized.

You can also prove this by contradiction: if in some optimal pairing a large element a[j] is paired with some element a[k] where k is not the smallest available, you can swap partners and show the maximum pair sum does not increase.

Visual walkthrough

Let's trace the algorithm on nums = [3, 5, 4, 2, 4, 1, 2, 5]. After sorting: [1, 2, 2, 3, 4, 4, 5, 5]. L (orange) is the left pointer, R (green) is the right pointer.

Notice how every pair sum lands at either 6 or 7. The greedy pairing keeps the sums balanced. No single pair gets stuck with two large values, and the maximum pair sum (7) is as low as it can be.

The code

def min_pair_sum(nums):
    nums.sort()
    result = 0
    left, right = 0, len(nums) - 1

    while left < right:
        result = max(result, nums[left] + nums[right])
        left += 1
        right -= 1

    return result

A few things to note about the implementation:

• We sort in place and use two converging pointers. No extra arrays needed.
• result tracks the running maximum pair sum. Each iteration pairs nums[left] with nums[right] and checks if this pair sum beats the current maximum.
• The pointers move inward simultaneously. Every element gets paired exactly once.
• After the loop, result holds the answer: the minimized maximum pair sum.

Complexity analysis

Time: O(n log n). Sorting dominates. The two-pointer pass is O(n), so the total is O(n log n).

Space: O(1) extra. We sort in place and use only a few variables. (Some languages allocate O(n) for the sort itself, but no auxiliary data structures are needed beyond that.)

Edge cases to watch for

1. Array of length 2. The only possible pair is (nums[0], nums[1]). The answer is their sum. The algorithm handles this naturally since the while loop runs exactly once.

2. All elements are equal. If every value is the same (say, all 4s), every pair sum is 2 * 4 = 8 regardless of pairing. The greedy approach still works and returns the correct answer.

3. Already sorted input. No special handling needed. The sort is a no-op, and the two-pointer pass proceeds normally.

4. Large spread between min and max. For example, [1, 1, 1, 1000000]. After sorting, the pair (1, 1000000) has sum 1000001, and (1, 1) has sum 2. The maximum is 1000001. No pairing can do better because 1000000 must pair with something, and its smallest possible partner is 1.

The building blocks

This problem combines two reusable building blocks that appear across many LeetCode problems.

Sort then greedily assign

Many optimization problems over arrays become tractable once you sort. Sorting reveals structure: you know which elements are small, which are large, and you can make greedy choices with confidence. This same "sort first, then greedily assign" pattern appears in:

• Assign Cookies (sort both arrays, greedily match smallest cookie to smallest child)
• Array Partition (sort and take every other element)
• Boats to Save People (sort and pair lightest with heaviest)

Opposite-end two pointers

After sorting, pair from both ends and converge. The smallest available element pairs with the largest, then the pointers move inward. This is a specialization of the two-pointer technique where you process the extremes first. The same pointer movement shows up in Container With Most Water, Two Sum II, and 3Sum.

When you recognize both bricks, the solution assembles itself: sort, then walk two pointers from opposite ends, tracking whatever quantity the problem asks for.

From understanding to recall

The algorithm here is short. Sort, pair from the ends, track the max. But the part worth internalizing is the why: why pairing extremes is optimal, and why adjacent pairing fails. That reasoning transfers directly to problems like Boats to Save People and Array Partition, where the same greedy logic applies with minor variations.

If you can explain the contradiction argument (swapping a non-extreme partner never helps) and write the two-pointer loop from scratch, you have this building block locked in. The next time you see a "minimize the maximum" problem on a sorted array, the pattern will click immediately.

Related posts

• Two Sum - The foundational complement-lookup problem that introduces pairing elements from an array
• 3Sum Closest - Another sorting plus two-pointer problem with a tracking variable
• Container With Most Water - Opposite-end convergence with a greedy elimination argument