#561

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Array Partition

Maximize the sum of minimums of n pairs in a 2n integer array using a greedy pairing strategy efficiently.

Problem Statement

You are given an integer array nums consisting of 2n integers. Your task is to divide these integers into n pairs such that the sum of the minimum of each pair is maximized. Return the highest possible sum of these minimum values.

For example, given nums = [1,4,3,2], pairing the elements as (1,2) and (3,4) yields min(1,2) + min(3,4) = 1 + 3 = 4, which is the maximum sum achievable. Another example: nums = [6,2,6,5,1,2], the optimal pairs are (1,2), (2,5), and (6,6), producing a sum of 9.

Examples

Example 1

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

Output: 4

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

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

Solution Approach

Sort and Pair Consecutively

Sort the array in ascending order and pair each element with its immediate neighbor. Sum the first element of each pair to maximize the sum of minimums. This leverages the greedy choice and invariant property directly.

Validate Greedy Invariant

After sorting, the greedy invariant ensures that selecting consecutive elements maintains the highest possible minimums across all pairs. Skipping elements or choosing non-consecutive pairs risks reducing the sum.

Optimize for Time and Space

A standard sort yields O(n log n) time and O(1) extra space beyond input. For bounded integer ranges, counting sort can reduce time to O(n) while still respecting the greedy invariant, improving efficiency for large arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting-based solution runs in O(n log n) time and O(1) space for in-place operations. Using counting sort for limited ranges reduces time to O(n). The space complexity depends on whether a standard sort or counting sort is used.

What Interviewers Usually Probe

Ask about greedy strategy versus brute force to test understanding of invariant validation.
Expect reasoning on why pairing sorted consecutive elements maximizes the sum of minimums.
Look for discussion of time-space trade-offs, such as using counting sort for bounded integer arrays.

Common Pitfalls or Variants

Common pitfalls

Attempting all possible pair combinations leads to exponential time complexity.
Pairing without sorting may violate the greedy invariant and produce suboptimal sums.
Misunderstanding that the sum of maximums in each pair is not the goal; the minimums drive the result.

Follow-up variants

Compute the maximum sum if elements can be negative and positive, emphasizing the same greedy principle.
Adapt the problem to k-sized groups instead of pairs, testing generalization of invariant reasoning.
Determine the minimum sum of maximums of pairs, which flips the greedy selection logic.

FAQ

What is the best strategy to solve Array Partition efficiently?

Sort the array and sum every other element starting from the first. This guarantees maximum sum of minimums due to the greedy invariant.

Can negative numbers affect the greedy pairing approach?

No, the greedy invariant still holds for negative numbers; pairing consecutive sorted elements ensures the sum of minimums is maximized.

Is brute force ever feasible for Array Partition?

No, trying all pair combinations has exponential complexity and becomes impractical even for small n.

How does counting sort optimize this problem?

For arrays with elements in a limited range, counting sort sorts in O(n) time, preserving the greedy consecutive pairing strategy.

Why do we sum the first element of each sorted pair?

Summing the first element captures the minimum of each pair while respecting the greedy invariant that maximizes the total sum.

terminal

Solution

Solution 1: Sorting

For a pair of numbers $(a, b)$, we can assume $a \leq b$, then $\min(a, b) = a$. In order to make the sum as large as possible, the $b$ we choose should be as close to $a$ as possible, so as to retain a larger number.

1

2

3

4

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

Continue Practicing

#581 shortest unsorted continuous subarray #611 valid triangle number #502 ipo