# LeetCode 561: Array Partition

## Problem Restatement

We are given an integer array `nums` containing `2n` integers.

We need to divide all numbers into `n` pairs:

```python
(a1, b1), (a2, b2), ..., (an, bn)
```

For each pair, we take the smaller number:

```python
min(ai, bi)
```

Return the maximum possible sum of these minimum values.

The constraints are `1 <= n <= 10^4`, `nums.length == 2 * n`, and `-10^4 <= nums[i] <= 10^4`. The examples include `nums = [1,4,3,2]`, output `4`, and `nums = [6,2,6,5,1,2]`, output `9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` of even length |
| Output | Maximum possible sum of pair minimums |
| Pair count | `len(nums) / 2` |
| Rule | Every number must be used exactly once |

Example function shape:

```python
def arrayPairSum(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 4, 3, 2]
```

Possible pairings include:

| Pairing | Sum of minimums |
|---|---|
| `(1, 4), (2, 3)` | `1 + 2 = 3` |
| `(1, 3), (2, 4)` | `1 + 2 = 3` |
| `(1, 2), (3, 4)` | `1 + 3 = 4` |

The best answer is:

```python
4
```

Example 2:

```python
nums = [6, 2, 6, 5, 1, 2]
```

Sort the numbers:

```python
[1, 2, 2, 5, 6, 6]
```

Pair adjacent numbers:

```python
(1, 2), (2, 5), (6, 6)
```

The minimums are:

```python
1, 2, 6
```

So the answer is:

```python
1 + 2 + 6 = 9
```

## First Thought: Try All Pairings

A direct solution is to generate every possible way to pair the numbers.

For each pairing, compute:

```python
sum(min(a, b) for each pair)
```

Then return the largest sum.

This is correct, but the number of possible pairings grows very quickly. We need a greedy rule.

## Key Insight

Sort the array.

After sorting, pair adjacent numbers.

For example:

```python
[1, 2, 3, 4]
```

The best pairs are:

```python
(1, 2), (3, 4)
```

The sum is:

```python
1 + 3 = 4
```

The reason is simple: in each pair, the smaller number is the one that contributes to the answer. The larger number is consumed but does not contribute.

So we want to avoid pairing a small number with a very large number, because that wastes the large number.

Sorting and pairing neighbors keeps each smaller number with the closest possible larger number.

After sorting, the contributing values are exactly the elements at even indices:

```python
nums[0], nums[2], nums[4], ...
```

## Algorithm

1. Sort `nums`.
2. Initialize `ans = 0`.
3. Add every element at an even index.
4. Return `ans`.

## Correctness

After sorting, write the numbers as:

```python
x0 <= x1 <= x2 <= x3 <= ... <= x(2n - 1)
```

In any pair, only the smaller element contributes to the sum.

The smallest number `x0` must be paired with some other number. No matter which number it pairs with, `x0` contributes as the minimum. Pairing `x0` with anything larger consumes that larger number without increasing the contribution from this pair.

To preserve larger numbers for future pair minimums, the best choice is to pair `x0` with the smallest remaining number, `x1`.

Then the same argument applies to the remaining sorted numbers:

```python
x2, x3, ..., x(2n - 1)
```

So the optimal pairs are adjacent sorted pairs:

```python
(x0, x1), (x2, x3), ..., (x(2n - 2), x(2n - 1))
```

The contribution from each pair is the first element of the pair, so the maximum sum is:

```python
x0 + x2 + x4 + ... + x(2n - 2)
```

The algorithm computes exactly this sum.

## Complexity

Let `m = len(nums)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(m log m)` | Sorting dominates the runtime |
| Space | `O(1)` or `O(m)` | Depends on the sorting implementation |

In Python, `list.sort()` sorts in place, but it may use temporary memory internally.

## Implementation

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

## Code Explanation

We first sort the array:

```python
nums.sort()
```

Then we take every second number starting at index `0`:

```python
nums[::2]
```

These are the smaller values in the adjacent sorted pairs.

Finally, we sum them:

```python
return sum(nums[::2])
```

## Counting Sort Version

Because the values are bounded between `-10^4` and `10^4`, we can also use counting sort.

This avoids comparison sorting and runs in linear time relative to the input size plus value range.

```python
class Solution:
    def arrayPairSum(self, nums: list[int]) -> int:
        offset = 10000
        count = [0] * 20001

        for num in nums:
            count[num + offset] += 1

        ans = 0
        take = True

        for value in range(-10000, 10001):
            freq = count[value + offset]

            while freq > 0:
                if take:
                    ans += value

                take = not take
                freq -= 1

        return ans
```

The variable `take` marks whether the current sorted position is even.

When `take` is `True`, the value is the smaller element of the next adjacent pair, so it contributes to the answer.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.arrayPairSum([1, 4, 3, 2]) == 4
    assert s.arrayPairSum([6, 2, 6, 5, 1, 2]) == 9
    assert s.arrayPairSum([1, 2]) == 1
    assert s.arrayPairSum([-1, -2, -3, -4]) == -6
    assert s.arrayPairSum([0, 0, 0, 0]) == 0
    assert s.arrayPairSum([-10000, 10000]) == -10000

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1, 4, 3, 2]` | Main sample |
| `[6, 2, 6, 5, 1, 2]` | Larger sample with duplicates |
| `[1, 2]` | Smallest valid pair |
| `[-1, -2, -3, -4]` | Negative numbers |
| `[0, 0, 0, 0]` | Duplicate zero values |
| `[-10000, 10000]` | Constraint boundary |