Skip to content

561. Array Partition

Description

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

 

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

Solutions

Solution 1: Sorting

Thinking

Pair numbers and sum the smaller of each pair; maximize that sum. The larger value in a pair is discarded, so it should be as small as possible — pair close values.

Sort and pair adjacent elements; the sum of every other number is optimal. Any crossing pair can be uncrossed without decreasing the sum.

For a pair of numbers \((a, b)\), we can assume \(a \leq b\), then \(\min(a, b) = a\). In order to make the sum as large as possible, the \(b\) we choose should be as close to \(a\) as possible, so as to retain a larger number.

Therefore, we can sort the array \(nums\), then divide every two adjacent numbers into a group, and add the first number of each group.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Where \(n\) is the length of the array \(nums\).

1
2
3
4
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < nums.length; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            ans += nums[i];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
func arrayPairSum(nums []int) (ans int) {
    sort.Ints(nums)
    for i := 0; i < len(nums); i += 2 {
        ans += nums[i]
    }
    return
}

1
2
3
4
5
6
impl Solution {
    pub fn array_pair_sum(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        nums.iter().step_by(2).sum()
    }
}

1
2
3
4
5
6
7
8
/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function (nums) {
    nums.sort((a, b) => a - b);
    return nums.reduce((acc, cur, i) => (i % 2 === 0 ? acc + cur : acc), 0);
};

Comments