561. Array Partition

Easy

Problem:

Output the largest number that can be made from the sum of min(a, b) using n pairs.

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.

https://leetcode.com/problems/array-partition/

Solutions:

Sort the array and try to find the pattern!

When adjacent element pairs are made in ascending order from the front in a sorted list, the largest pairs $a_1$ and $a_2$ can be made, and the sum of these pairs becomes the maximum sum that can be made.

The result is the same even if it is made in descending order from the end.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        max_sum = 0
        i = 0
        while i < len(nums) - 1:
            max_sum += min(nums[i], nums[i+1])
            i += 2
        return max_sum

Use sorting characteristics

In a sorted list, the smaller value always resides at an even index.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        max_sum = 0
        
        for i, n in enumerate(nums):
            if i % 2 == 0:
                max_sum += n
        return max_sum

Pythonic way

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])