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
numswith length2n.
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
- Sort the Array: Sort the input array
numsin non-decreasing order. - Pair Adjacent Elements: Iterate through the sorted array and pair adjacent elements. Specifically, for each even index
i, pairnums[i]withnums[i+1]. - 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.