LeetCode 561: Array Partition Solution in Python – A Step-by-Step Guide

What Is LeetCode 561: Array Partition?

In LeetCode 561: Array Partition, you’re given an integer array nums of even length, and your task is to pair up all elements into n/2 pairs and return the maximum possible sum of the minimum values in each pair. For example, with nums = [1, 4, 3, 2], pairing [1, 2] and [3, 4] gives min(1, 2) + min(3, 4) = 1 + 3 = 4, which is optimal. This problem builds on LeetCode 414: Third Maximum Number for array sorting but focuses on pairing to maximize a specific sum.

Problem Statement

• Input: nums (List[int])—array of integers with even length.
• Output: Integer—maximum sum of minimum values from n/2 pairs.
• Rules: Pair all elements into n/2 pairs; sum the minimum of each pair; maximize the total.

Constraints

• 1 <= n <= 10⁴ (n is even, so array length = 2 * n)
• -10⁴ <= nums[i] <= 10⁴

Examples

• Input: nums = [1,4,3,2]
• Output: 4
• Pairs: [1, 2], [3, 4]; Sum: min(1, 2) + min(3, 4) = 1 + 3 = 4.
• Input: nums = [6,2,6,5,1,2]
• Output: 9
• Pairs: [1, 2], [2, 5], [6, 6]; Sum: 1 + 2 + 6 = 9.
• Input: nums = [1,1]
• Output: 1
• Pair: [1, 1]; Sum: min(1, 1) = 1.

Understanding the Problem: Maximizing Pair Sums

To solve LeetCode 561: Array Partition in Python, we need to pair up all elements in an array of even length n into n/2 pairs and maximize the sum of the minimum values in each pair. With array lengths up to 2 * 10⁴, a brute-force approach checking all pairings (exponential) is impractical. The key insight is that sorting the array and pairing adjacent elements minimizes the loss from larger numbers, maximizing the sum of the smaller ones. We’ll explore:

• Best Solution (Sorting with Pair Summation): O(n log n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute-Force Pair Enumeration): O(n!) time, O(n) space—thorough but slow.

Let’s dive into the sorting solution with a friendly breakdown!

Best Solution: Sorting with Pair Summation

Why Sorting Wins

The sorting with pair summation solution is the best for LeetCode 561 because it achieves the maximum sum in O(n log n) time and O(1) extra space (excluding input) by sorting the array and pairing adjacent elements, ensuring the smallest numbers are paired together to contribute their maximum possible value to the sum. It’s like organizing a buddy system where the closest numbers team up to boost the total!

How It Works

Think of this as a pairing optimizer:

• Step 1: Sort the Array:
• Arrange nums in ascending order.
• Step 2: Pair Adjacent Elements:
• Take pairs from sorted array: (0, 1), (2, 3), etc.
• Step 3: Sum Minimums:
• For each pair, add the smaller number (first of pair after sorting).
• Step 4: Return Total:
• Sum of all pair minimums.
• Why It Works:
• Sorting minimizes the difference between paired numbers.
• Pairing adjacent elements ensures smallest numbers contribute, maximizing sum.

It’s like a pair-sum maximizer!

Step-by-Step Example

Example: nums = [1, 4, 3, 2]

• Step 1: Sort: [1, 2, 3, 4].
• Step 2: Pairs: [1, 2], [3, 4].
• Step 3: Sum minimums:
• min(1, 2) = 1.
• min(3, 4) = 3.
• Total = 1 + 3 = 4.
• Result: 4.

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

• Step 1: Sort: [1, 2, 2, 5, 6, 6].
• Step 2: Pairs: [1, 2], [2, 5], [6, 6].
• Step 3: Sum:
• min(1, 2) = 1.
• min(2, 5) = 2.
• min(6, 6) = 6.
• Total = 1 + 2 + 6 = 9.
• Result: 9.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # Step 1: Sort the array
        nums.sort()

        # Step 2: Initialize sum
        total = 0

        # Step 3: Sum every other element (minimums of pairs)
        for i in range(0, len(nums), 2):
            total += nums[i]  # Add first element of each pair

        # Step 4: Return total sum
        return total

• Line 4: Sort array in ascending order.
• Line 7: Start total sum at 0.
• Lines 10-11: Iterate with step 2, add every first element (minimum of pair).
• Line 14: Return final sum.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—no extra space (in-place sort).

It’s like a pair-sum organizer!

Alternative Solution: Brute-Force Pair Enumeration

Why an Alternative Approach?

The brute-force pair enumeration generates all possible ways to pair the elements, computes the sum of minimums for each, and finds the maximum, running in O(n!) time and O(n) space. It’s exhaustive but impractical for larger arrays, making it a good baseline for small inputs or understanding the problem fully.

How It Works

Picture this as a pair-shuffling tester:

• Step 1: Generate all possible pairings.
• Step 2: For each pairing, sum the minimums.
• Step 3: Track maximum sum.
• Step 4: Return max sum.

It’s like a pair-sum explorer!

Step-by-Step Example

Example: nums = [1, 2, 3, 4]

• Step 1: Pairings:
• [1, 2], [3, 4]: 1 + 3 = 4.
• [1, 3], [2, 4]: 1 + 2 = 3.
• [1, 4], [2, 3]: 1 + 2 = 3.
• Step 2: Max = 4.
• Result: 4.

Code for Brute-Force Approach

Copy codefrom itertools import permutations

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        def get_pair_sum(pairs):
            return sum(min(pairs[i], pairs[i + 1]) for i in range(0, len(pairs), 2))

        max_sum = 0
        n = len(nums)
        # Generate all permutations and pair them
        for perm in permutations(nums):
            pairs = list(perm)
            curr_sum = get_pair_sum(pairs)
            max_sum = max(max_sum, curr_sum)

        return max_sum

• Line 5: Helper computes sum of pair minimums.
• Lines 9-13: Generate permutations, compute sum, track max.
• Line 15: Return maximum sum.
• Time Complexity: O(n!)—permutation generation.
• Space Complexity: O(n)—permutation storage.

It’s a brute-force pair tester!

Comparing the Two Solutions

• Sorting (Best):
• Pros: O(n log n), O(1), fast.
• Cons: Insight-based.
• Brute-Force (Alternative):
• Pros: O(n!), O(n), exhaustive.
• Cons: Impractical for large n.

Sorting wins for efficiency!

Additional Examples and Edge Cases

• [1, 1]: 1.
• [2, 1, 4, 3]: 4.
• [-1, -2, -3, -4]: -7.

Sorting handles them all!

Complexity Recap

• Sorting: Time O(n log n), Space O(1).
• Brute-Force: Time O(n!), Space O(n).

Sorting’s the speed champ!

Key Takeaways

• Sorting: Pairing wisdom—learn at Python Basics!
• Brute-Force: Full enumeration.
• Arrays: Pairs are fun.
• Python: Sort or brute, your pick!

Final Thoughts: Maximize That Sum!

LeetCode 561: Array Partition in Python is a delightful array challenge. Sorting with pair summation is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 414: Third Maximum Number or LeetCode 88: Merge Sorted Array. Ready to pair? Head to Solve LeetCode 561 on LeetCode and maximize that sum today!