Editorial Series - LeetCode 561. Array Partition I

Problem Description

In this problem, you are given an integer array nums that contains 2n integers. You have to form n pairs using all of these integers and then sum all the minimum integers taken from each of the pairs. Finally, your task is to determine the maximum sum that can be achieved.

Solution Description

• Case# n = 1
  You have 2 integers. The smaller integer between the 2 integers contributes to the sum.

• Case# n = 2
  You have 4 integers. Surely, the smallest integer among these 4 integers is going to contribute to the sum. Since you do not want to lose the opportunity to utilize a bigger number to be considered as part of the sum, you should pair the smallest integer with the next smallest integer. Now, there remain 2 more integers to evaluate and you can simply follow the logic for Case# n = 1.

To generalize, you are pairing up:

• 1^st smallest integer with the 2^nd smallest integer
• 3^rd smallest integer with the 4^th smallest integer
  and so on.

This can be easily achieved by sorting the nums array in ascending order.

Your next task is, to sum all the integers present in even indices of the array (0-based index) since these integers are the minimum integers in their pairs.

Solution Code

If you are stuck with the solution of this problem, check the codes below:

C++

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        int n = nums.size(), answer = 0;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < n; i += 2)
            answer += nums[i];
        
        return answer;
    }
};

Java

class Solution {
    public int arrayPairSum(int[] nums) {
        int n = nums.length, answer = 0;
        Arrays.sort(nums);
        
        for (int i = 0; i < n; i += 2)
            answer += nums[i];
        
        return answer;
    }
}

Python

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return sum([i for i in nums[::2]])

C#

public class Solution {
    public int ArrayPairSum(int[] nums) {
        int n = nums.Length, answer = 0;
        Array.Sort(nums);
        
        for (int i = 0; i < n; i += 2)
            answer += nums[i];
        
        return answer;
    }
}

Ruby

# @param {Integer[]} nums
# @return {Integer}
def array_pair_sum(nums)
    nums.sort!
    (nums.select!.with_index { |_,i| i.even? }).sum
end