Efficiency often comes down to balance. In this problem, we explore how to pair numbers strategically to keep the overall sum as low as possible: a technique that is fundamental to optimization problems in computer science.
Problem Summary
You’re given:
An array of integers called nums with an even length .
Your goal: Group every number into pairs so that the largest sum among all pairs is as small as possible.
Intuition
To minimize the maximum sum, we need to balance the "weight" of our pairs. If we pair the largest number with another large number, the sum will be massive. Conversely, if we pair the smallest numbers together, we leave the large numbers to be paired with each other later, which again creates a huge sum.
The optimal strategy is a Greedy Approach: pair the smallest available number with the largest available number. This "spreads" the value evenly across all pairs. To do this efficiently, we sort the array first. Once sorted, the smallest value is at the start and the largest is at the end. We use two pointers to move inward, calculating each pair sum and keeping track of the highest one we encounter.
Walkthrough: Understanding the Examples
Example 1: `nums = [3, 5, 2, 3]`
- Sort the array:
[2, 3, 3, 5] - Pair 1: Smallest (2) + Largest (5) = 7.
- Pair 2: Next Smallest (3) + Next Largest (3) = 6.
- Find Maximum: The maximum of is 7.
Example 2: `nums = [3, 5, 4, 2, 4, 6]`
- Sort the array:
[2, 3, 4, 4, 5, 6] - Pair 1: 2 + 6 = 8.
- Pair 2: 3 + 5 = 8.
- Pair 3: 4 + 4 = 8.
- Find Maximum: The maximum of is 8.
Code Blocks
C++
class Solution {
public:
int minPairSum(vector<int>& nums) {
// Sort the array to easily pick the smallest and largest elements
sort(nums.begin(), nums.end());
int l = 0;
int r = nums.size() - 1;
int res = 0;
// Use two pointers to pair elements from both ends
while (l < r) {
res = max(res, nums[l] + nums[r]);
l++;
r--;
}
return res;
}
};
Python
class Solution:
def minPairSum(self, nums: List[int]) -> int:
# Sort the list to enable the greedy two-pointer approach
nums.sort()
l, r = 0, len(nums) - 1
max_sum = 0
while l < r:
# Calculate current pair sum and update the result if it's larger
current_pair_sum = nums[l] + nums[r]
if current_pair_sum > max_sum:
max_sum = current_pair_sum
l += 1
r -= 1
return max_sum
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var minPairSum = function(nums) {
// Sort numbers in ascending order
nums.sort((a, b) => a - b);
let l = 0;
let r = nums.length - 1;
let res = 0;
while (l < r) {
// Calculate the sum of the current pair
let currentSum = nums[l] + nums[r];
// Track the maximum sum found so far
res = Math.max(res, currentSum);
l++;
r--;
}
return res;
};