Pair up all numbers so that the largest pair sum is as small as possible.
Given an array of even length, divide its elements into disjoint pairs. Each element must belong to exactly one pair. For every pair, compute the sum of the two values. Your task is to choose the pairing that minimizes the maximum pair sum across all pairs.
A common way to think about the problem is: if one pair is forced to contain a very large number, what value should it be matched with to keep the overall maximum as small as possible?
Input Format
- An integer array
numsof even lengthm. - Each element is an integer.
Output Format
- Return the minimum possible value of the maximum pair sum after pairing up all elements.
Constraints
- The array length is even.
- Every element must be used in exactly one pair.
- The exact numeric limits are not provided here; assume standard interview-scale integer inputs.
Example 1
Input
nums = [3,5,2,3]
Output
7
Explanation
One optimal pairing is (3,3) and (2,5). The pair sums are 6 and 7, so the maximum is 7. No pairing can make the maximum smaller.
Example 2
Input
nums = [3,5,4,2,4,6]
Output
8
Explanation
After sorting, an optimal pairing is (2,6), (3,5), and (4,4). The pair sums are 8, 8, and 8, so the maximum pair sum is 8.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.