Array Partition
Problem
Given an integer array of length 2n, group it into n pairs so that the sum of min(a, b) over all pairs is maximised; return that sum.
nums = [1,4,3,2]4def array_pair_sum(nums):
nums.sort()
return sum(nums[::2])function arrayPairSum(nums) {
nums.sort((a, b) => a - b);
let s = 0;
for (let i = 0; i < nums.length; i += 2) s += nums[i];
return s;
}class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int s = 0;
for (int i = 0; i < nums.length; i += 2) s += nums[i];
return s;
}
}int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int s = 0;
for (int i = 0; i < (int)nums.size(); i += 2) s += nums[i];
return s;
}Explanation
In every pair, only the smaller number counts toward the sum. To make that total as big as possible, we want each pair's loser to be as large as it can be — so we should never waste a big number by pairing it with a much bigger one.
The trick is to sort the array and pair neighbors: 1st with 2nd, 3rd with 4th, and so on. In each adjacent pair the smaller element is the one at the even index, which is exactly what nums[::2] grabs.
Why pairing neighbors is optimal: a number only ever helps the sum when it is the minimum of its pair, and after sorting, putting each number next to its closest larger neighbor loses the least. Spreading them apart would force a larger number to be "wasted" as a maximum.
So the whole solution is two lines: nums.sort() then sum(nums[::2]).
Example: nums=[1,4,3,2] sorts to [1,2,3,4]. The even-index elements are 1 and 3, so the answer is 1 + 3 = 4.