Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

An even-length array must be divided into pairs, with every element used exactly once. Each pair has a sum, and the score of a complete pairing is its largest pair sum. The goal is to make that worst pair as small as possible.

This is a bottleneck problem: improving already-small pair sums does not matter if one large pair still determines the answer. The right strategy is therefore to keep the largest values from being paired together.

Deriving the optimal solution

Sort the values. Pair the smallest value with the largest, the second-smallest with the second-largest, and continue inward. The answer is the largest sum among those pairs.

The greedy choice can be justified with a simple exchange argument. Let a be the smallest remaining value and d the largest. Suppose a proposed solution pairs d with b and a with c instead of pairing the two extremes together. Because d >= c and b >= a, the worse of those original pairs is d + b.

Now replace the two pairs with (a, d) and (b, c). Their sums satisfy

$$ a + d \le b + d $$

and

$$ b + c \le b + d. $$

Neither replacement pair is worse than the old maximum b + d. Therefore, some optimal solution always pairs the current smallest and largest values. Removing that pair leaves the same problem on a smaller sorted array, so repeating the choice is optimal for every pair.

For [3, 5, 4, 2, 4, 6], sorting gives [2, 3, 4, 4, 5, 6]. Pairing inward produces (2, 6), (3, 5), and (4, 4). Every pair sums to 8, so the minimized maximum is 8.

Sorting takes $O(n \log n)$ time. The two-pointer scan takes $O(n)$ time. The implementation below sorts a copy so that it does not surprise callers by changing their input, which makes its extra space usage $O(n)$.

Python solution

from collections.abc import Sequence


class Solution:
    """Minimize the largest sum produced by pairing every input value."""

    def minPairSum(self, nums: list[int]) -> int:
        """Return the smallest achievable maximum pair sum.

        A sorted copy is used deliberately so the caller's list is preserved.
        LeetCode guarantees a positive, even number of input elements; the
        validation keeps the helper safe if it is reused outside that contract.
        """
        self._validate_pairable(nums)
        sorted_values = sorted(nums)
        return self._maximum_extreme_pair_sum(sorted_values)

    @staticmethod
    def _validate_pairable(values: Sequence[int]) -> None:
        """Reject collections that cannot be divided into nonempty pairs."""
        if len(values) < 2 or len(values) % 2 != 0:
            raise ValueError("values must contain a positive, even number of items")

    @staticmethod
    def _maximum_extreme_pair_sum(sorted_values: Sequence[int]) -> int:
        """Pair opposite ends of an ascending sequence and return the bottleneck."""
        pair_count = len(sorted_values) // 2
        maximum_pair_sum = sorted_values[0] + sorted_values[-1]

        for left_index in range(1, pair_count):
            right_index = len(sorted_values) - left_index - 1
            current_pair_sum = (
                sorted_values[left_index] + sorted_values[right_index]
            )
            maximum_pair_sum = max(maximum_pair_sum, current_pair_sum)

        return maximum_pair_sum

Interview follow-ups

How would the solution return the actual pairs and their original indices?

Decorate every value with its original index, sort the (value, index) records by value, and pair records from opposite ends. Return those index pairs along with the largest pair sum. Duplicate values remain distinguishable because each record carries its own index.

The same exchange argument applies because only the values determine the objective; attaching indices does not change any sum. Sorting still costs $O(n \log n)$ time, building the pairs costs $O(n)$ time, and the decorated records plus returned pairs use $O(n)$ space.

Can the extra copy be avoided?

If the caller permits mutation, sort nums in place and run the same inward scan. This removes the explicit $O(n)$ copy and is often the simplest memory optimization. The greedy proof and $O(n \log n)$ time bound are unchanged.

The exact auxiliary-space bound then depends on the sorting implementation. An in-place heap sort can provide $O(1)$ auxiliary space, while Python’s list.sort() may use $O(n)$ temporary memory in the worst case. In production code, preserving the input is often worth the predictable copy unless memory pressure or an ownership contract makes mutation acceptable.

Can bounded integer values beat comparison sorting?

Yes. If every value lies in a reasonably small range from 0 through U, build a frequency array. Maintain one pointer at the smallest value with remaining count and another at the largest. Repeatedly consume one occurrence from each end and update the maximum pair sum, taking special care to consume two occurrences when both pointers meet.

This exactly simulates the sorted extreme-pairing order, so it inherits the same correctness proof. It takes $O(n + U)$ time and $O(U)$ space. That improves on $O(n \log n)$ when U is small, but it is unattractive when the value range is huge and sparse.

Could binary search be used on the answer?

After sorting, test a proposed limit T by pairing the largest remaining value with the smallest. If their sum exceeds T, the largest value cannot be paired legally with anything, so T is impossible. Otherwise consume that pair and continue inward. Passing every pair proves that a pairing bounded by T exists.

Binary-searching T therefore gives a valid $O(n \log V)$ feasibility phase after sorting, where V is the range of possible sums. It is unnecessary for the original problem because the direct greedy scan already reveals the exact answer in $O(n)$. The feasibility view becomes useful when an interviewer adds constraints that remove the closed-form extreme pairing but preserve a monotone yes-or-no test.

What changes if the objective is to minimize the largest absolute difference within a pair?

Sort the values and pair adjacent elements: the smallest with the second-smallest, the third-smallest with the fourth-smallest, and so on. Pairing across a larger gap can be uncrossed into closer adjacent pairs without increasing the worst difference, so an optimal solution exists with adjacent pairs.

The implementation again takes $O(n \log n)$ time for sorting and $O(n)$ time for the scan. This variation is a useful warning that greedy rules depend on the objective: pairing opposite ends balances sums, while pairing neighbors controls distances.