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:

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

For each pair, we take the smaller number:

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

Example function shape:

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

Examples

Example 1:

nums = [1, 4, 3, 2]

Possible pairings include:

The best answer is:

4

Example 2:

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

Sort the numbers:

[1, 2, 2, 5, 6, 6]

Pair adjacent numbers:

(1, 2), (2, 5), (6, 6)

The minimums are:

1, 2, 6

So the answer is:

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:

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:

[1, 2, 3, 4]

The best pairs are:

(1, 2), (3, 4)

The sum is:

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:

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:

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:

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

So the optimal pairs are adjacent sorted pairs:

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

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

The algorithm computes exactly this sum.

Complexity

Let m = len(nums).

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

Implementation

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

Code Explanation

We first sort the array:

nums.sort()

Then we take every second number starting at index 0:

nums[::2]

These are the smaller values in the adjacent sorted pairs.

Finally, we sum them:

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.

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

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()