Domain 1EasyCORE

Array Partition I

The problem requires us to group an array of `2n` integers into `n` pairs such that the sum of the minimum values from each pair is maximized. The input is an integer array `nums`, and the output is a single integer representing the maximum possible sum.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

561. Array Partition I

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 73.5%


Problem Breakdown

The problem requires us to group an array of 2n integers into n pairs such that the sum of the minimum values from each pair is maximized. The input is an integer array nums, and the output is a single integer representing the maximum possible sum.

Inputs:

  • An integer array nums with length 2n.

Outputs:

  • An integer representing the maximum sum of the minimums of the pairs.

Implicit Constraints/Edge Cases:

  • The array length is always even (2n).
  • The array can contain negative numbers.
  • The array can have duplicate values.

Intuition

A brute-force approach would involve generating all possible pairings and calculating the sum of the minimums for each pairing. This approach is infeasible due to its factorial time complexity, which grows extremely fast with the size of n.

The key insight is that to maximize the sum of the minimum values, we should pair adjacent elements after sorting the array. Sorting ensures that the smallest numbers are paired together, maximizing the contribution of smaller numbers to the overall sum.

Approach

  1. Sort the Array: Sort the input array nums in non-decreasing order.
  2. Pair Adjacent Elements: Iterate through the sorted array and pair adjacent elements. Specifically, for each even index i, pair nums[i] with nums[i+1].
  3. Sum the Minimums: Sum up the values at the even indices (which represent the minimums of each pair).

This approach leverages sorting to ensure that we are always pairing the smallest available numbers together, which maximizes the sum of the minimums.

Complexity Analysis

  • Time Complexity: O(n log n) due to the sorting step. The subsequent iteration through the array is O(n), but this is dominated by the sorting time.
  • Space Complexity: O(1) if we sort the array in place. If we need to maintain the original array, it would be O(n).

Solution

def arrayPairSum(nums):
    # Sort the array
    nums.sort()
    
    # Sum up the elements at even indices
    max_sum = sum(nums[i] for i in range(0, len(nums), 2))
    
    return max_sum

Edge Cases Handled

  • Negative Numbers: The sorting approach naturally handles negative numbers by placing them in the correct order.
  • Duplicate Values: Sorting ensures that duplicates are paired together correctly, maximizing the sum of the minimums.
  • Single Element (n=1): Although not explicitly mentioned, if n=1, the array would have two elements, and the solution would correctly return their minimum.