LeetCode 561: Array Partition

Problem Description

LeetCode Problem 561

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), …, (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Example 1:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:

(1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
(1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
(1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Example 2:

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Constraints:

• 1 <= n <= 104
• nums.length == 2 * n
• -104 <= nums[i] <= 104

Difficulty: Easy

Tags: array, greedy, sorting, counting sort

Rating: 88.45%

Solution Approaches

1. Sorting Approach (O(n log n))

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

How it works:

1. Sort the array in ascending order
2. Take the first element of each pair (elements at even indices)
3. Sum these elements to get the maximum possible sum

Time Complexity: $O(n log n)$ due to sorting

Space Complexity: $O(1)$ as we sort in-place

2. Counting Sort Approach (O(n + k))

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        minv, maxv = min(nums), max(nums)
        r = maxv - minv + 1
        count = [0] * r
        
        # Count frequency of each number
        for n in nums:
            count[n - minv] += 1
            
        s = 0
        need_pair = False

        # Process numbers in ascending order
        for i in range(r):
            while count[i] > 0:
                if not need_pair:
                    s += i + minv
                need_pair = not need_pair
                count[i] -= 1
        
        return s

How it works:

1. Find the range of numbers in the input
2. Create a counting array to store frequency of each number
3. Process numbers in ascending order:
   • Add a number to sum when it starts a new pair
   • Skip a number when it completes a pair
   • Toggle between starting/completing pairs

Time Complexity: $O(n + k)$ where k is the range of numbers

Space Complexity: $O(k)$ for the counting array

When to Use Each Approach

• Use Sorting Approach when:

  • The range of numbers (k) is large
  • Memory is constrained
  • Code simplicity is preferred

• Use Counting Sort when:

  • The range of numbers (k) is small
  • Numbers are densely distributed
  • Maximum performance is needed for small ranges