Minimize Maximum Pair Sum in Array — Problem & Solution
Minimize Maximum Pair Sum in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimize Maximum Pair Sum in Array is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of even length n. Split its elements into n / 2 pairs so that every element is in exactly one pair. The pair sum of (a, b) is a + b.
Return the smallest possible value of the largest pair sum.
Example 1
Input: nums = [1,9,4,6]
Output: 10
Explanation: Pairs `(1,9)` and `(4,6)` both sum to 10.
Example 2
Input: nums = [2,8,3,5,1,9]
Output: 10
Explanation: Pairs `(1,9)`, `(2,8)` and `(3,5)`.
Example 3
Input: nums = [7,7]
Output: 14
Constraints
n == nums.length2 <= n <= 10^5n is even1 <= nums[i] <= 10^5
Hints for Minimize Maximum Pair Sum in Array
Hint 1
The largest element has to be paired with something. Which partner keeps its pair sum smallest?
Hint 2
Pair the largest with the smallest, then the second largest with the second smallest, and so on.
Hint 3
Sort the array and take the maximum of
nums[i] + nums[n - 1 - i].
How to solve Minimize Maximum Pair Sum in Array
Sort the array and pair the smallest with the largest, the second smallest with the second largest, and so on. The answer is the largest of these sums.
Approach
- Sort
numsascending. - For
ifrom 0 ton/2 - 1, computenums[i] + nums[n - 1 - i]. - Return the maximum of these sums.
Why it works
Exchange argument: if the largest element M is paired with x while the smallest m is paired with y, swapping partners to (M, m) and (x, y) gives sums M + m <= M + x and x + y <= M + x, so the maximum does not grow. Repeating on the remaining elements yields the sorted pairing.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Pairing neighbours after sorting (
nums[0]withnums[1], …) maximises the largest sum instead of minimising it. - Only half the indices need to be visited — each pair is counted once.
- Pair sums reach at most
2 · 10^5, so there is no overflow.
Reference solution
Python
from typing import List
def minPairSum(nums: List[int]) -> int:
a = sorted(nums)
n = len(a)
return max(a[i] + a[n - 1 - i] for i in range(n // 2))Java
public static int minPairSum(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length, best = 0;
for (int i = 0; i < n / 2; i++) best = Math.max(best, a[i] + a[n - 1 - i]);
return best;
}C++
int minPairSum(vector<int>& nums) {
vector<int> a(nums);
sort(a.begin(), a.end());
int n = a.size(), best = 0;
for (int i = 0; i < n / 2; i++) best = max(best, a[i] + a[n - 1 - i]);
return best;
}JavaScript
var minPairSum = function(nums) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var n = a.length, best = 0;
for (var i = 0; i < n / 2; i++) best = Math.max(best, a[i] + a[n - 1 - i]);
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms