Minimize Maximum Pair Sum in Array
Problem
You are given an array nums of even length n. Split its elements into exactly n/2 pairs so that every element belongs to exactly one pair. The pair sum of a pair (a, b) is a + b, and the maximum pair sum of a pairing is the largest pair sum among its n/2 pairs.
Choose the pairing so that this maximum pair sum is as small as possible, and return that minimized value.
nums = [3,5,4,2,4,6]8def min_pair_sum(nums):
nums.sort()
i, j = 0, len(nums) - 1
best = 0
while i < j:
s = nums[i] + nums[j]
best = max(best, s)
i += 1
j -= 1
return bestfunction minPairSum(nums) {
nums.sort((a, b) => a - b);
let i = 0, j = nums.length - 1;
let best = 0;
while (i < j) {
const s = nums[i] + nums[j];
best = Math.max(best, s);
i++;
j--;
}
return best;
}int minPairSum(int[] nums) {
Arrays.sort(nums);
int i = 0, j = nums.length - 1;
int best = 0;
while (i < j) {
int s = nums[i] + nums[j];
best = Math.max(best, s);
i++;
j--;
}
return best;
}int minPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int i = 0, j = nums.size() - 1;
int best = 0;
while (i < j) {
int s = nums[i] + nums[j];
best = max(best, s);
i++;
j--;
}
return best;
}Explanation
The key insight is a greedy one: the largest element of the array has to be paired with something, and whatever it gets, that pair's sum is at least the largest element. To keep that unavoidable big sum as small as possible, we should hand the largest element the smallest element. Repeating the argument on what remains pairs the second smallest with the second largest, and so on.
An exchange argument makes this rigorous. Suppose an optimal pairing matches the smallest value a with some x and the largest value b with some y (so a ≤ y and x ≤ b). Swapping partners to form (a, b) and (x, y) gives max(a+b, x+y) ≤ max(a+y, x+b), because a+b ≤ x+b and x+y ≤ x+b, and similarly both are bounded by the old maximum. So pairing extremes never makes the answer worse, and we can transform any optimal solution into the ends-inward pairing.
That turns the algorithm into sort + two pointers: sort nums, put i at the front and j at the back, and while i < j record the pair sum nums[i] + nums[j], keep the running maximum best, then move both pointers inward. When the pointers cross, every element has been used exactly once and best is the minimized maximum pair sum.
Walking through the default example nums = [3,5,4,2,4,6]: sorting gives [2,3,4,4,5,6]. The pointer pairs are 2+6 = 8, then 3+5 = 8, then 4+4 = 8. The running maximum stays 8, so the answer is 8 — and indeed no other pairing can keep every pair sum below 8, since 6 must be paired with a value of at least 2.
The sort dominates the running time at O(n log n); the pointer sweep afterwards is a single O(n) pass. Apart from the sort's recursion stack, we only keep a few scalar variables, so the extra space is O(log n) (or O(1) if the sort is counted as in-place).