Array Partition I Problem


Description

LeetCode Problem 561.

Given an integer array nums of 2n integers, group these integers into n pairs (a_1, b_1), (a_2, b_2), …, (a_n, b_n) such that the sum of min(a_i, b_i) for all i is maximized. Return the maximized sum.

Example 1:

1
2
3
4
5
6
7
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:

1
2
3
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 <= 10^4
  • nums.length == 2 * n
  • -10^4 <= nums[i] <= 10^4


Sample C++ Code

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 result = 0;
        for (int itr = 0; itr < nums.size(); itr += 2) {
            result += nums[itr];
        }
        return result;
    }
};




Related Posts

Sum Of Subsequence Widths Problem

LeetCode 891. The width of a sequence is the difference...

Sort An Array Problem

LeetCode 912. Given an array of integers nums, sort the...

Smallest Range II Problem

LeetCode 910. You are given an integer array nums and...

Reordered Power Of 2 Problem

LeetCode 869. You are given an integer n. We reorder...

Reorder Data In Log Files Problem

LeetCode 937. You are given an array of logs. Each...

Minimum Increment To Make Array Unique Problem

LeetCode 945. You are given an integer array nums. In...