Array Partition

Problem Statement

The challenge involves an integer array nums consisting of 2n integers. Your task is to pair up these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) in such a way that the total sum of the minimum values of each pair (min(ai, bi)) is as large as possible. The objective is to determine and return this maximized sum from the possible pairings. This problem essentially examines how optimally pairs can be formed from the array elements to maximize a specific combined value from the pairs.

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.

Constraints

• 1 <= n <= 104
• nums.length == 2 * n
• -104 <= nums[i] <= 104

Approach and Intuition

To solve the problem of maximizing the sum of the minimum values from n pairs formed from 2n elements, consider the following strategy, inspired by the provided examples:

1. Sorting the array: Initially, sort the array nums. Sorting helps in easily accessing and forming pairs where larger elements are grouped with relatively smaller counterparts but are not the smallest possible, which can push the minimum values up.

2. Pairing strategy: Post sorting, the idea is to pair the first element (smallest in the sorted order) with the element right in the middle of the array. This is basically the (n+1)th element when the array index starts from 1. Pairing in such a method ensures that the elements that contribute to the minimum of each pair are not the smallest of the remaining set, which helps in maximizing the sum of these minimums.

3. Sum Calculation: Calculate the sum of all such minimums. In accordance with the pairing mentioned, the pairs would be (nums[0], nums[n]), (nums[1], nums[n+1]), ..., (nums[n-1], nums[2n-1]). The minimized values for each pair formed this way will, combined, give a larger sum.

This logic hinges mainly on the balancing act between the smallest and slightly larger values that allows each selected minimum to be relatively high compared to a random or an unsorted pairing strategy. Given the constraints, this approach is efficient and straightforward, since the primary computational effort involves sorting the array, which can be done in O(n log n) time. This sorted approach directly leads to the optimal pairing configuration.

Solutions

class Solution {
public:
    const static int OFFSET = 10000;
            
    int pairSum(vector<int>& data) {
        int histogram[2 * OFFSET + 1] = {0};
        for (int num : data) {
            histogram[num + OFFSET]++;
        }
            
        int pairSumResult = 0;
        bool evenPosition = true;
        for (int index = 0; index <= 2 * OFFSET; index++) {
            while (histogram[index]) {
                if (evenPosition) pairSumResult += index - OFFSET;
                evenPosition = !evenPosition;
                histogram[index]--;
            }
        }
        return pairSumResult;
    }
};