Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input:
 [1,4,3,2]


Output:
 4

Explanation:
 n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

Brainstorm

It is worthwhile to look at why the given example had such a solution. Why is the partition (1,2) (3,4) and not something else like (1,3) (2,4)? Because interestingly, some number will always need to be grouped with 1. However we don't want to group the maximum number, 4, with it, because this will result in min(1,4) = 1, and 4 is sacrificed. Same goes for grouping 3 with 1. So the best choice is to group the second least number, 2, with 1, so that 1 is still inevitably selected, but the "sacrifice" is not as bad.

Therefore, we see that:

1. The least integer in the array will always be _included _in the calculation (because no matter what, it will be selected from a comparison of minimums), and similarly:
2. The greatest integer in the array will always be _excluded _from the calculation (because it will never be selected since there is always a smaller number)

To minimize the "loss" of needing to include the least integer, it's probably best if we grouped it with the second least integer. Similarly, grouping the greatest integer with the second greatest integer will result in the former being "sacrificed" for the latter - which is not a bad tradeoff, and probably the best we can do. We can apply a similar logic to the integers in the middle, such that integers are grouped with their next greatest neighbor, so that the "sacrifices" are reduced as much as possible.

Now that we have this basic idea set down, the question is how do we know which integer is the least/greatest? The answer is, obviously, sorting.

Approach #1: Sorting

We can use the sort() function from C++'s STL. Then, we add up the mins of each partition of size n to our result, and return it.

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

Time complexity: $$O(n log n)$$

Sorting the array will be O(n log n). Iterating through the array and summing up the integers is O(n), but that will be dominated by the sorting complexity.

Space complexity: $$O(n)$$

Using C++'s STL sort requires O(n) space.

There is a great proof to this solution as provided here: https://discuss.leetcode.com/topic/87206/java-solution-sorting-and-rough-proof-of-algorithm