Description:
Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.
Examples:
Example 1:
Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.
Example 2:
Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.Solution in Python:
To solve this problem efficiently, we can follow a strategy based on sorting the array. The key observation is that to maximize the sum of the minimums of pairs, we should pair elements that are close to each other in value. By sorting the array and pairing consecutive elements, we ensure that we get the largest possible minimum values.
Python
from typing import List
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
# Step 1: Sort the array
nums.sort()
# Step 2: Initialize the sum
max_sum = 0
# Step 3: Sum up the minimum of each pair
# Since the array is sorted, the minimum of each pair (i, i+1) is nums[i]
for i in range(0, len(nums), 2):
max_sum += nums[i]
# Step 4: Return the calculated sum
return max_sum
# Example usage:
sol = Solution()
print(sol.arrayPairSum([1,4,3,2])) # Output: 4
print(sol.arrayPairSum([6,2,6,5,1,2])) # Output: 9Explanation:
- Sorting the array:
nums.sort()arranges the elements in non-decreasing order. - Initial sum: We initialize
max_sumto 0 to keep track of the sum of the minimums of the pairs. - Summing the minimums: We iterate over the sorted array with a step of 2 (
range(0, len(nums), 2)), which allows us to consider every pair. The minimum of each pair(nums[i], nums[i+1])in the sorted array is alwaysnums[i]. - Returning the result: Finally, we return
max_sum, which contains the sum of the minimums of the pairs.
This approach has a time complexity of O(n log n) due to the sorting step, where nnn is the length of the input array. This is efficient and works within the given constraints.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var arrayPairSum = function(nums) {
// Step 1: Sort the array in non-decreasing order
nums.sort((a, b) => a - b);
// Step 2: Initialize the sum
let maxSum = 0;
// Step 3: Sum up the minimum of each pair
// Since the array is sorted, the minimum of each pair (i, i+1) is nums[i]
for (let i = 0; i < nums.length; i += 2) {
maxSum += nums[i];
}
// Step 4: Return the calculated sum
return maxSum;
};
// Example usage:
console.log(arrayPairSum([1, 4, 3, 2])); // Output: 4
console.log(arrayPairSum([6, 2, 6, 5, 1, 2])); // Output: 9Solution in Java:
Java
class Solution {
public int arrayPairSum(int[] nums) {
// Step 1: Sort the array in non-decreasing order
Arrays.sort(nums);
// Step 2: Initialize the sum
int maxSum = 0;
// Step 3: Sum up the minimum of each pair
// Since the array is sorted, the minimum of each pair (i, i+1) is nums[i]
for (int i = 0; i < nums.length; i += 2) {
maxSum += nums[i];
}
// Step 4: Return the calculated sum
return maxSum;
}
}
// Example usage:
class Main {
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums1 = {1, 4, 3, 2};
System.out.println(sol.arrayPairSum(nums1)); // Output: 4
int[] nums2 = {6, 2, 6, 5, 1, 2};
System.out.println(sol.arrayPairSum(nums2)); // Output: 9
}
}Solution in C#:
C#
public class Solution {
public int ArrayPairSum(int[] nums) {
// Step 1: Sort the array in non-decreasing order
Array.Sort(nums);
// Step 2: Initialize the sum
int maxSum = 0;
// Step 3: Sum up the minimum of each pair
// Since the array is sorted, the minimum of each pair (i, i+1) is nums[i]
for (int i = 0; i < nums.Length; i += 2) {
maxSum += nums[i];
}
// Step 4: Return the calculated sum
return maxSum;
}
}