LeetCode 561 - Array Partition

The problem gives an array nums containing 2n integers. Our task is to divide these integers into exactly n pairs. For each pair (ai, bi), we take the smaller value, min(ai, bi). After computing the minimum value from every pair, we sum all of those minimums together.

leetcodeeasyarraygreedysortingcounting-sort

LeetCode Problem 561

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting, Counting Sort

Solution

Problem Understanding

The problem gives an array nums containing 2n integers. Our task is to divide these integers into exactly n pairs. For each pair (ai, bi), we take the smaller value, min(ai, bi). After computing the minimum value from every pair, we sum all of those minimums together.

The goal is to arrange the pairs so that this final sum is as large as possible.

For example, suppose we have:

[1, 4, 3, 2]

We need to form two pairs because the array length is 4 = 2 * 2.

One possible pairing is:

(1, 4), (2, 3)

The minimums are:

1 and 2

The total becomes:

1 + 2 = 3

However, if we instead pair:

(1, 2), (3, 4)

the minimums are:

1 and 3

which gives:

1 + 3 = 4

This is larger, so it is the optimal answer.

The constraints are important:

  • nums.length == 2 * n
  • 1 <= n <= 10^4
  • -10^4 <= nums[i] <= 10^4

The array can contain up to 20,000 elements, which is large enough that exponential or factorial solutions are completely impractical. Since the values are bounded between -10^4 and 10^4, a counting sort based solution is also possible, although standard sorting is already efficient enough.

The input guarantees that the array length is always even, so we never need to worry about an unmatched element. The array may contain:

  • Duplicate values
  • Negative numbers
  • All equal values
  • Very large or very small valid integers

A naive implementation can fail if it tries every possible pairing because the number of pair combinations grows extremely quickly.

Approaches

Brute Force Approach

The brute force idea is to generate every possible way to pair the numbers. For each pairing arrangement, we compute:

min(pair1) + min(pair2) + ...

and keep the maximum result.

This approach is correct because it explores every possible valid grouping, so the optimal answer must eventually be found.

However, the number of possible pairings is enormous. For an array of length 2n, the number of ways to partition into pairs grows factorially. Even for moderate input sizes, this becomes computationally impossible.

For example:

  • With 10 numbers, the number of pairings is already very large.
  • With 20,000 numbers, brute force is completely infeasible.

We need a more efficient observation.

Optimal Greedy Approach

The key insight is that after sorting the array, the optimal strategy is to pair adjacent elements.

Suppose the sorted array is:

a0 <= a1 <= a2 <= a3 <= ...

If we pair adjacent numbers:

(a0, a1), (a2, a3), ...

then the minimum of each pair is simply:

a0 + a2 + a4 + ...

Why is this optimal?

The smaller number in each pair determines the contribution to the sum. To maximize the total, we want the smaller numbers to be as large as possible. Pairing small numbers together prevents large numbers from being "wasted" as the larger element in a pair with a tiny number.

Sorting ensures numbers are ordered, and pairing neighbors minimizes the gap inside each pair, which maximizes the sum of the smaller elements.

Approach Time Complexity Space Complexity Notes
Brute Force O((2n)!) O(n) Tries every possible pairing arrangement
Optimal O(n log n) O(1) or O(log n) Sorts the array and sums every second element

Algorithm Walkthrough

Optimal Greedy Algorithm

  1. Sort the array in nondecreasing order.

Sorting places smaller numbers together and larger numbers together. This ordering is the foundation of the greedy strategy. 2. Initialize a variable total to 0.

This variable will store the sum of the minimum values from each pair. 3. Traverse the sorted array using a step size of 2.

Since adjacent elements form each pair, the first element of every pair appears at indices:

0, 2, 4, 6, ...
  1. Add the element at each even index to total.

In a sorted adjacent pair:

nums[i] <= nums[i + 1]

so the minimum of the pair is always nums[i]. 5. Return total.

After processing all pairs, total contains the maximum possible sum.

Why it works

After sorting, every adjacent pair has the smallest possible difference. If a small number were paired with a much larger number, the larger number would not contribute to the sum because only the minimum matters. Pairing adjacent elements prevents large values from being wasted and maximizes the contribution of each pair's smaller element.

This greedy arrangement guarantees the optimal result.

Python Solution

from typing import List

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()

        total = 0

        for i in range(0, len(nums), 2):
            total += nums[i]

        return total

The implementation begins by sorting the array. Once sorted, every pair of adjacent elements represents the optimal pairing arrangement.

The variable total accumulates the answer. The loop increments by 2 because each iteration processes one pair. Since the array is sorted, the element at index i is always the smaller value in the pair (nums[i], nums[i + 1]).

Finally, the method returns the accumulated sum.

Go Solution

package main

import "sort"

func arrayPairSum(nums []int) int {
	sort.Ints(nums)

	total := 0

	for i := 0; i < len(nums); i += 2 {
		total += nums[i]
	}

	return total
}

The Go implementation follows the same logic as the Python version. The sort.Ints() function sorts the slice in ascending order.

Go slices are dynamic views over arrays, so sorting modifies the original slice directly. Integer overflow is not a concern here because the maximum possible answer fits comfortably within Go's int range.

The loop increments by 2 so that only the first element of each adjacent pair is added to the result.

Worked Examples

Example 1

Input:

nums = [1,4,3,2]

Step 1: Sort the array

[1,2,3,4]

Step 2: Form adjacent pairs

Pair Minimum Running Total
(1, 2) 1 1
(3, 4) 3 4

Final answer:

4

Example 2

Input:

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

Step 1: Sort the array

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

Step 2: Form adjacent pairs

Pair Minimum Running Total
(1, 2) 1 1
(2, 5) 2 3
(6, 6) 6 9

Final answer:

9

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Depends on the sorting implementation

The main cost comes from sorting the array. After sorting, the traversal is linear.

In Python, Timsort may use additional space internally. In Go, the sorting implementation also uses some stack space for recursion. Aside from sorting overhead, the algorithm itself only uses a few variables.

Test Cases

from typing import List

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()

        total = 0

        for i in range(0, len(nums), 2):
            total += nums[i]

        return total

solution = Solution()

assert solution.arrayPairSum([1, 4, 3, 2]) == 4  # basic example
assert solution.arrayPairSum([6, 2, 6, 5, 1, 2]) == 9  # duplicate values
assert solution.arrayPairSum([1, 1]) == 1  # smallest valid input
assert solution.arrayPairSum([0, 0, 0, 0]) == 0  # all zeros
assert solution.arrayPairSum([-1, -2, -3, -4]) == -6  # all negative numbers
assert solution.arrayPairSum([-1, 0, 1, 2]) == 0  # mix of negative and positive
assert solution.arrayPairSum([5, 5, 5, 5]) == 10  # all equal values
assert solution.arrayPairSum([10000, -10000]) == -10000  # extreme constraint values
assert solution.arrayPairSum([1, 2, 3, 4, 5, 6]) == 9  # already sorted
assert solution.arrayPairSum([6, 5, 4, 3, 2, 1]) == 9  # reverse sorted
Test Why
[1,4,3,2] Validates the primary example
[6,2,6,5,1,2] Tests duplicates and unsorted input
[1,1] Smallest valid array
[0,0,0,0] Ensures zeros are handled correctly
[-1,-2,-3,-4] Verifies negative number handling
[-1,0,1,2] Tests mixed sign values
[5,5,5,5] Confirms behavior with identical values
[10000,-10000] Tests constraint extremes
[1,2,3,4,5,6] Already sorted input
[6,5,4,3,2,1] Reverse sorted input

Edge Cases

One important edge case is the minimum valid input size. When the array contains only two elements, there is exactly one possible pair. Some implementations incorrectly assume multiple iterations or attempt unnecessary logic. This solution handles the case naturally because the loop executes exactly once.

Another important case involves negative numbers. Since the goal is still to maximize the sum of minimums, sorting remains correct even when values are negative. For example:

[-4, -3, -2, -1]

becomes:

(-4, -3), (-2, -1)

which produces:

-4 + -2 = -6

The implementation works correctly because sorting preserves the optimal adjacency property regardless of sign.

A third important edge case is duplicate values. Arrays like:

[5,5,5,5]

can sometimes expose pairing assumptions or indexing bugs. Since every pair has identical elements, every arrangement produces the same answer. The algorithm still works correctly because adjacent pairing remains valid.

Another subtle case is already sorted or reverse sorted input. Some implementations accidentally rely on original ordering or perform incorrect swaps. Because this solution explicitly sorts first, the initial arrangement of the input does not matter.