Array Partition

Problem

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.

Constraints

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

Solution

The problem Array Partition can be solved by sorting the given array and creating pairs of 2 from consecutive elements starting from the smallest one.

Implementation

class Solution
{
  public:
    int arrayPairSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());

        int ret = 0;
        for (int i = 0; i < nums.size(); i += 2)
            ret += nums[i];

        return ret;
    }
};