# 561. Array Partition

## 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:

{% hint style="info" %}
Sort the array and try to find the pattern!
{% endhint %}

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.

```python
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.

```python
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

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