Code Implementation

class Solution:
    def arrayPairSum(self, nums):
        nums.sort()
        return sum(nums[::2])
      

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            sum += nums[i];
        }
        return sum;
    }
};
      

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}
      

var arrayPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    let sum = 0;
    for (let i = 0; i < nums.length; i += 2) {
        sum += nums[i];
    }
    return sum;
};
      

Problem Description

Given an array nums of 2n integers, your task is to pair these integers into n pairs such that the sum of the minimum value in each pair is maximized. In other words, you should:

• Form n pairs from 2n elements, using each element exactly once (no reuse).
• For each pair, consider the smaller of the two numbers.
• Sum all these minimum values, and return the largest possible sum you can achieve.

Constraints:

• Each element in nums is an integer.
• nums.length is always even.
• Each element must be used in exactly one pair.
• There is only one valid solution for the maximum sum.

Thought Process

At first glance, it might seem that we need to try all possible ways to pair up the numbers and check which combination gives the highest sum of minimums. This brute-force approach would quickly become infeasible as the array grows, due to the sheer number of ways to pair elements.

To optimize, we need to observe a pattern or property that lets us find the answer without checking every possibility. By analyzing small examples, we can see that pairing the smallest numbers together and the next smallest together, and so on, gives the best result. This is because pairing a small number with a much larger number "wastes" the larger number (since only the minimum counts), whereas pairing similar numbers keeps more of the larger numbers available for other pairs.

Thus, sorting the array and taking every other element (starting from the smallest) for the sum is the optimal strategy.

Solution Approach

Here’s how we solve the problem step by step:

1. Sort the array nums in ascending order.
   • This groups similar numbers together and ensures that the difference between numbers in a pair is minimized.
2. Pair up consecutive elements.
   • After sorting, pair the first and second elements, third and fourth, and so on.
3. Sum the first element of every pair.
   • Since the array is sorted, the first element in each pair is always the smaller one (the minimum).
   • This is equivalent to summing every element at an even index (0, 2, 4, ...).
4. Return the total sum.
   • This sum is guaranteed to be the maximum possible according to the problem constraints.

We use sorting (which is efficient and easy to implement) and then a simple loop to compute the sum.

Example Walkthrough

Let’s walk through an example with nums = [1, 4, 3, 2]:

1. Sort the array: [1, 2, 3, 4]
2. Pair up elements:
   • First pair: 1 and 2 (minimum is 1)
   • Second pair: 3 and 4 (minimum is 3)
3. Sum the minimums: 1 + 3 = 4
4. Result: The maximum sum of minimums is 4.

If we tried any other pairing (for example, (1, 3) and (2, 4)), the sum of minimums would be 1 + 2 = 3, which is less than 4. This confirms that the sorted-pairing approach is optimal.

Time and Space Complexity

• Brute-force approach:
  • Would require generating all possible pairings, which is factorial time complexity: O((2n)! / (n! * 2^n)). This is completely impractical for even moderate values of n.
• Optimized approach (sorting):
  • Sorting the array takes O(n \log n) time.
  • Summing every other element is O(n) time.
  • Total time complexity: O(n \log n)
  • Space complexity: O(1) extra space (if sorting in-place), or O(n) if the language's sort creates a copy.

Summary

The key insight for solving the Array Partition problem is realizing that pairing numbers in sorted order (smallest with next smallest) maximizes the sum of the minimums. This avoids "wasting" large numbers by pairing them with much smaller ones. By sorting the array and summing every other element, we get an efficient and elegant solution with O(n \log n) time complexity and minimal space usage. This approach is both intuitive and optimal for the problem constraints.