Array Partition
On this page 
Problem Statement
Given an integer array nums with 2n elements, your task is to group these integers into n pairs in such a way that the sum of the minimum values from each pair is maximized.
Each pair consists of two integers, and the goal is to find the maximum possible sum of the smallest integer in each pair.
For example, if the input is nums = [1, 4, 3, 2], the optimal pairing is (1, 2) and (3, 4), which yields a maximum sum of 1 + 3 = 4.
Implement a function that returns this maximum sum.
Example 1
Input: array = [1, 4, 3, 2]
Output: 4
Example 2
Input: array = [6, 2, 6, 5, 1, 2]
Output: 9
Solution 1: Sorting and Pairing
function maxSumOfPairs(numbers) {
numbers.sort((a, b) => a - b);
let total = 0;
for (let i = 0; i < numbers.length; i += 2) {
total += numbers[i];
}
return total;
}
const array1 = [1, 4, 3, 2];
maxSumOfPairs(array1); //output: 4
const array2 = [6, 2, 6, 5, 1, 2];
maxSumOfPairs(array2); //output: 9
This is the most straightforward approach: sort the array to maximize the sum of minimum values in pairs.
By sorting, you ensure that each pair is optimally composed of adjacent elements, allowing you to simply sum every second element in the sorted array.
This method is efficient and guarantees that you achieve the highest possible sum of the minimum values of each pair.
Solution 2: Divide and Conquer
function optimizedPairSum(values) {
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [], i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
values = mergeSort(values);
let total = 0;
for (let i = 0; i < values.length; i += 2) {
total += values[i];
}
return total;
}
const array1 = [1, 4, 3, 2];
optimizedPairSum(array1); //output: 4
const array2 = [6, 2, 6, 5, 1, 2];
optimizedPairSum(array2); //output: 9