LeetCode #561 Array Partition I

Easy

Problem

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].

Solution

It’s trivial if we’d like to make min(ai, bi) as large as possible, we have to make the smaller one of (ai,bi) as large as possible. The easiest way is to put (max, second_max) elements together so we can retrieve value of second_max. And for rest elements, we do the same approach for them, which means we put (third_max, forth_max) elements together so we can get value of forth_max.

For doing this approach, we can simply sort original list, group them two by two, take the smaller ones out and sum them up.

Complexity

Because we don’t know the domain values of input nums. We should use comparison-based sorting schema so it will take O(nlogn) time which n denotes to length of nums. And, sum each smaller element will take O(n/2) time. Therefore, total time complexity will be O(nlogn + n/2) = O(nlogn).

Fortunately, there exists in place comparison-based sorting algorithm (e.g. Heap Sort) so it only needs O(1) extra space.