Array Partition

Difficulty: Easy | Acceptance: 81.70% | Paid: No Topics: Array, Greedy, Sorting, Counting Sort

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.

• Examples
• Constraints
• Approach 1: Brute Force (Permutations)
• Approach 2: Sorting (Greedy)
• Approach 3: Counting Sort

Examples

Example 1

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

1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
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 <= 10⁴
nums.length == 2n
-10⁴ <= nums[i] <= 10⁴

Approach 1: Brute Force (Permutations)

Intuition We can generate every possible permutation of the array to form pairs of adjacent elements, calculate the sum of minimums for each permutation, and keep track of the maximum sum found.

Steps

• Generate all permutations of the input array.
• For each permutation, iterate through the array with a step of 2 to form pairs.
• Calculate the sum of the minimum values of these pairs.
• Update the maximum sum if the current sum is greater.
• Return the maximum sum.

from typing import List
import itertools

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        n = len(nums)
        # Generate all permutations of indices to form pairs
        # Note: This is extremely inefficient and will TLE for large n
        for perm in itertools.permutations(nums):
            current_sum = 0
            for i in range(0, n, 2):
                current_sum += min(perm[i], perm[i+1])
            if current_sum > max_sum:
                max_sum = current_sum
        return max_sum

Complexity

• Time: O(n!) - Generating permutations is factorial time complexity.
• Space: O(n) - For recursion stack or storing permutations.
• Notes: This approach is conceptually simple but computationally infeasible for large inputs (Time Limit Exceeded).

Approach 2: Sorting (Greedy)

Intuition To maximize the sum of minimums of pairs, we should try to make the minimum values as large as possible. If we sort the array in ascending order, pairing adjacent elements (0th with 1st, 2nd with 3rd, etc.) ensures that the larger number in each pair “protects” the smaller number from being paired with an even smaller number elsewhere. The sum of elements at even indices (0, 2, 4…) gives the maximized sum.

Steps

• Sort the array in ascending order.
• Initialize a sum variable to 0.
• Iterate through the array, incrementing the index by 2 in each step.
• Add the element at the current index to the sum.
• Return the sum.

from typing import List

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

Complexity

• Time: O(n log n) - Dominated by the sorting step.
• Space: O(1) or O(n) - Depending on the sorting algorithm’s space complexity (e.g., heapsort uses O(1), Timsort uses O(n)).
• Notes: This is the most standard and practical approach for this problem.

Approach 3: Counting Sort

Intuition Since the range of numbers in the input is constrained (-10⁴ to 10⁴), we can use Counting Sort to achieve linear time complexity. We count the frequency of each number, then iterate through the range of possible numbers in ascending order. We simulate the pairing process: every time we encounter a number, we add it to the sum if it is the first element of a pair, and skip it if it is the second.

Steps

• Determine the offset (10,000) to handle negative numbers by shifting the range to 0-20,000.
• Initialize a count array of size 20,001 with zeros.
• Iterate through the input array and increment the count for each number (shifted by offset).
• Initialize a sum variable and a boolean flag pick to true.
• Iterate through the count array from 0 to 20,000:
  • While the count for the current number is greater than 0:
    • If pick is true, add the (current index - offset) to the sum.
    • Toggle pick.
    • Decrement the count.
• Return the sum.

from typing import List

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        OFFSET = 10000
        count = [0] * 20001
        for num in nums:
            count[num + OFFSET] += 1
        
        total = 0
        pick = True
        for i in range(20001):
            while count[i] > 0:
                if pick:
                    total += i - OFFSET
                pick = not pick
                count[i] -= 1
        return total

Complexity

• Time: O(n + k) - Where n is the number of elements and k is the range of values (20,001).
• Space: O(k) - For the count array.
• Notes: This is faster than sorting when n is large and k is small, but uses extra space proportional to the value range.