Array Partition
EasyPrompt
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.
Example 1:
Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) 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 <= 104nums.length == 2 * n-104 <= nums[i] <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
The core idea is based on the realization that to maximize the sum of minimums, we should pair smaller numbers with other smaller numbers. Specifically, if we pair the smallest number with the second smallest, the third smallest with the fourth smallest, and so on, we achieve the maximum possible sum. This is because any other pairing would force a smaller number to be paired with a much larger number, effectively "wasting" the potential of that larger number, as only the smaller one contributes to the sum.
Algorithm
-
- Sort the input array
numsin non-decreasing order.
- Sort the input array
-
- Initialize a variable
sumto 0.
- Initialize a variable
-
- Loop through the sorted array from index 0 to
nums.length - 1with a step of 2.
- Loop through the sorted array from index 0 to
-
- In each iteration, add the element
nums[i]tosum.
- In each iteration, add the element
-
- After the loop finishes, return
sum.
- After the loop finishes, return
Walkthrough
The algorithm first sorts the input array nums in ascending order. After sorting, the array nums will be [s_1, s_2, s_3, s_4, ..., s_{2n-1}, s_{2n}], where s_i <= s_{i+1}. The optimal pairs are (s_1, s_2), (s_3, s_4), ..., (s_{2n-1}, s_{2n}). The sum of minimums for these pairs is min(s_1, s_2) + min(s_3, s_4) + ... + min(s_{2n-1}, s_{2n}). Since the array is sorted, min(s_{2i-1}, s_{2i}) is always s_{2i-1}. Therefore, the maximum sum is the sum of all elements at even indices (0, 2, 4, ...) in the sorted array. We can iterate through the sorted array with a step of 2 and accumulate these elements.
import java.util.Arrays; class Solution { public int arrayPairSum(int[] nums) { // Sort the array in non-decreasing order. Arrays.sort(nums); int maxSum = 0; // Iterate through the sorted array, taking every second element. // These are the smaller elements of each optimal pair. for (int i = 0; i < nums.length; i += 2) { maxSum += nums[i]; } return maxSum; }}Complexity
Time
O(N log N), where N is the number of elements in the array (`2n`). The `Arrays.sort()` method in Java for primitive types uses a dual-pivot quicksort, which has an average time complexity of `O(N log N)`. The subsequent loop takes `O(N)` time. Thus, the sorting step dominates.
Space
O(log N) or O(N). The space complexity of `Arrays.sort()` in Java depends on the implementation. For primitive types, it's an in-place quicksort which requires `O(log N)` space for the recursion stack. In the worst case, it can be `O(N)`.
Trade-offs
Pros
Simple to understand and implement.
Works for any range of integer values, not just the constrained one.
Cons
Not the most efficient solution possible due to the
O(N log N)sorting time.
Solutions
Solution
class Solution { public int arrayPairSum ( int [] nums ) { Arrays . sort ( nums ); int ans = 0 ; for ( int i = 0 ; i < nums . length ; i += 2 ) { ans += nums [ i ]; } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.