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] <= 104The key idea in Array Partition is to maximize the sum of the smaller element from each pair after dividing the array into pairs of two. A natural observation is that pairing numbers strategically affects the total contribution of the minimum values. To maximize the final sum, we should ensure that smaller numbers are paired in a way that avoids wasting large values.
A common strategy is to sort the array first. Once sorted, pairing adjacent elements ensures that the smaller element in each pair contributes optimally to the total sum. By iterating through the sorted list and considering every second element, we effectively accumulate the best possible minimum values from each pair.
Because the values fall within a limited range, another optimization uses counting sort instead of traditional sorting. This can reduce the sorting overhead and improve performance for large inputs. The overall idea relies on greedy pairing after ordering the numbers.
Time complexity depends on the sorting technique used, while space complexity varies between in-place sorting and frequency-based counting approaches.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Greedy Pairing | O(n log n) | O(1) or O(log n) depending on sorting implementation |
| Counting Sort Optimization | O(n + k) | O(k) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Obviously, brute force won't help here. Think of something else, take some example like 1,2,3,4.
How will you make pairs to get the result? There must be some pattern.
Did you observe that- Minimum element gets add into the result in sacrifice of maximum element.
Still won't able to find pairs? Sort the array and try to find the pattern.
The core idea of this approach is to pair up the elements after sorting the array to maximize the minimum sum of pairs. By sorting the array, the smallest values are naturally grouped together, maximizing your result. After sorting, pair the elements from the start with their consecutive neighbor. This guarantees maximal sum of mins in pairs.
Let us see how we can implement this in various programming languages:
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as no additional space is used except for input.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int arrayPairSum(std::vector<int>& nums) {
6 std::sort(nums.begin(), nums.end());
7 int sum = 0;
8 for (int i = 0; i < nums.size(); i += 2) {
9 sum += nums[i];
10 }
11 return sum;
12}
13
14int main() {
std::vector<int> nums = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums);
std::cout << result << std::endl;
return 0;
}In this C++ implementation, we sort the vector using std::sort(). By iterating through the array and summing up the values at even indices, we get the desired result.
Instead of using a traditional sorting method, we can optimize the sorting step with a counting sort. This is particularly useful given the constraints - limited range of numbers. This approach uses a counting array to sort, followed by picking elements at alternate indices in a manner similar to the previous approach.
Time Complexity: O(n + range) due to counting sort.
Space Complexity: O(range) for the count array.
1#include <vector>
#include <cstring>
int arrayPairSum(std::vector<int>& nums) {
const int RANGE = 20001;
int count[RANGE];
std::memset(count, 0, sizeof(count));
for (int num : nums) {
++count[num + 10000];
}
int sum = 0;
bool odd = false;
for (int i = 0; i < RANGE; ++i) {
while (count[i] > 0) {
if (!odd) {
sum += (i - 10000);
}
odd = !odd;
--count[i];
}
}
return sum;
}
int main() {
std::vector<int> nums = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums);
std::cout << result << std::endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting arranges numbers in ascending order so that pairing neighbors minimizes the loss of larger numbers. This ensures that each pair's minimum value is as large as possible overall. As a result, the total sum of minimum elements is maximized.
Yes, Array Partition or similar greedy and sorting-based problems are common in technical interviews. They test a candidate's ability to recognize patterns like pairing after sorting and applying greedy reasoning. Variations of this concept often appear in coding interviews.
Arrays are sufficient for this problem since the task mainly involves sorting and iteration. For optimized solutions, a counting array can be used to implement counting sort when the value range is limited. This helps achieve linear time complexity.
The optimal approach is to sort the array and pair adjacent elements. After sorting, the first element of every pair contributes to the final sum, which maximizes the total of minimum values. This greedy strategy works because sorting ensures the smallest values are grouped efficiently.
The C++ code implemented counting sort logic by tracking each number's count and using this information to reconstruct the nums sequence for optimal pairing and summation.