Problem Description

You are given an integer array nums containing 2n integers. Your task is to group these integers into n pairs: (a₁, b₁), (a₂, b₂), ..., (aₙ, bₙ).

For each pair (aᵢ, bᵢ), you need to take the minimum value min(aᵢ, bᵢ). Your goal is to maximize the sum of all these minimum values.

Return the maximum possible sum.

For example, if you have nums = [1, 4, 3, 2], you need to form 2 pairs. If you pair them as (1, 4) and (2, 3), the sum would be min(1, 4) + min(2, 3) = 1 + 2 = 3. But if you pair them as (1, 2) and (3, 4), the sum would be min(1, 2) + min(3, 4) = 1 + 3 = 4, which is larger.

The solution works by sorting the array first. After sorting, pairing adjacent elements gives the optimal result. This is because for each pair, we want the two numbers to be as close as possible in value - this way, when we take the minimum, we're "wasting" the least amount from the larger number. By taking every other element from the sorted array (elements at even indices), we get the sum of all the minimum values from the optimal pairing.

Intuition

To understand why we should pair adjacent elements after sorting, let's think about what happens when we form pairs.

When we pick two numbers to form a pair, we only get to add the smaller one to our sum - the larger one is essentially "wasted". So the key insight is: we want to minimize the waste.

Consider having numbers like [1, 2, 5, 6]. If we pair (1, 6) and (2, 5), we get min(1, 6) + min(2, 5) = 1 + 2 = 3. Here, we're wasting 6 - 1 = 5 from the first pair and 5 - 2 = 3 from the second pair, total waste = 8.

But if we pair (1, 2) and (5, 6), we get min(1, 2) + min(5, 6) = 1 + 5 = 6. Now we're only wasting 2 - 1 = 1 from the first pair and 6 - 5 = 1 from the second pair, total waste = 2.

This reveals the pattern: to minimize waste, pair numbers that are close to each other in value. And the closest numbers to each other are adjacent numbers in a sorted array!

Once sorted, we take every alternate element starting from index 0 (i.e., elements at positions 0, 2, 4, ...). These represent the smaller element from each adjacent pair, and their sum gives us the maximum possible result.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a straightforward greedy approach based on our intuition about pairing adjacent elements after sorting.

Step 1: Sort the array

First, we sort the entire array nums in ascending order using nums.sort(). This arranges all elements from smallest to largest, ensuring that adjacent elements have the minimum difference in value.

Step 2: Sum alternate elements

After sorting, we need to sum up the smaller element from each adjacent pair. Since we've arranged the array in ascending order, for any adjacent pair (nums[i], nums[i+1]), the element at index i (where i is even) will always be the minimum.

The Python slice notation nums[::2] elegantly extracts all elements at even indices (0, 2, 4, ...). This gives us exactly the minimum element from each adjacent pair.

Step 3: Return the sum

Finally, we use Python's built-in sum() function to calculate the total of all these minimum values and return it.

Time Complexity: O(n log n) where n is the length of the array, dominated by the sorting operation.

Space Complexity: O(1) if we consider the sorting to be in-place (though technically Python's sort uses O(n) auxiliary space).

The beauty of this solution lies in its simplicity - by recognizing that we need to pair adjacent elements after sorting, the entire problem reduces to just two lines of code: sort and sum alternate elements.

Example Walkthrough

Let's walk through the solution with nums = [6, 2, 6, 5, 1, 2].

Step 1: Sort the array After sorting: [1, 2, 2, 5, 6, 6]

Step 2: Form pairs from adjacent elements The pairs would be:

• Pair 1: (1, 2) → minimum = 1
• Pair 2: (2, 5) → minimum = 2
• Pair 3: (6, 6) → minimum = 6

Step 3: Extract elements at even indices Elements at even indices (0, 2, 4): [1, 2, 6]

These are exactly the minimum values from each pair!

Step 4: Calculate the sum Sum = 1 + 2 + 6 = 9

Let's verify this is optimal by trying a different pairing:

• If we paired (1, 6), (2, 6), (2, 5): sum = 1 + 2 + 2 = 5 (worse)
• If we paired (1, 5), (2, 2), (6, 6): sum = 1 + 2 + 6 = 9 (same, but notice (2, 2) is still adjacent in sorted order)

The key insight: by pairing adjacent sorted elements, we minimize the "waste" (difference between paired numbers). In our optimal pairing, we waste only (2-1) + (5-2) + (6-6) = 4 total, whereas other pairings waste much more.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums. This is dominated by the sorting operation nums.sort(), which uses Timsort algorithm in Python with O(n × log n) time complexity in the average and worst cases. The subsequent slicing and summation operation sum(nums[::2]) takes O(n/2) = O(n) time, which is absorbed by the larger sorting complexity.

The space complexity is O(log n). While the sorting operation in Python's Timsort is an in-place sort that modifies the original array, it still requires O(log n) auxiliary space for the recursion stack during the merge sort phase. The slicing operation nums[::2] creates a new list containing half the elements, which would typically require O(n) space, but since this is passed directly to sum() and Python can optimize this as a generator expression in some implementations, the dominant space complexity remains O(log n) from the sorting algorithm's recursion stack.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Generate All Possible Pairings

A common mistake is trying to generate all possible pairings and then finding the one with maximum sum. This leads to an exponential time complexity solution that's unnecessarily complex.

Incorrect Approach:

def arrayPairSum(self, nums: List[int]) -> int:
    # Wrong: Trying to generate all permutations and pairings
    from itertools import permutations
    max_sum = float('-inf')
    for perm in permutations(nums):
        current_sum = 0
        for i in range(0, len(perm), 2):
            current_sum += min(perm[i], perm[i+1])
        max_sum = max(max_sum, current_sum)
    return max_sum

Why it's wrong: This has O((2n)!) time complexity and will time out for large inputs.

2. Misunderstanding the Pairing After Sorting

Some might think that after sorting, we should pair the smallest with the largest, second smallest with second largest, etc.

Incorrect Approach:

def arrayPairSum(self, nums: List[int]) -> int:
    # Wrong: Pairing smallest with largest
    nums.sort()
    total = 0
    left, right = 0, len(nums) - 1
    while left < right:
        total += min(nums[left], nums[right])  # This will always be nums[left]
        left += 1
        right -= 1
    return total

Why it's wrong: This approach always picks the smaller half of the sorted array, which gives us the minimum possible sum, not the maximum. When you pair the smallest with the largest, you "waste" the largest values completely.

3. Off-by-One Errors in Manual Iteration

When manually iterating through pairs instead of using slicing, it's easy to make indexing mistakes.

Incorrect Approach:

def arrayPairSum(self, nums: List[int]) -> int:
    nums.sort()
    total = 0
    # Wrong: Should be range(0, len(nums), 2) not range(0, len(nums)-1, 2)
    for i in range(0, len(nums)-1, 2):
        total += nums[i]
    return total

Why it's wrong: If the array has an even length (which it always does in this problem), using len(nums)-1 as the stop value will miss the last pair.

4. Forgetting to Sort In-Place vs Creating New Array

While not incorrect, creating a new sorted array instead of sorting in-place uses unnecessary extra space.

Less Optimal:

def arrayPairSum(self, nums: List[int]) -> int:
    # Creates a new sorted list (uses extra O(n) space)
    sorted_nums = sorted(nums)
    return sum(sorted_nums[::2])

Better Solution:

def arrayPairSum(self, nums: List[int]) -> int:
    # Sorts in-place (modifies original array)
    nums.sort()
    return sum(nums[::2])

The in-place sort is more memory-efficient, though both approaches are correct.