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] <= 104Problem Overview: You receive an array of 2n integers. The task is to form n pairs so that the sum of the minimum value in each pair is maximized. The trick is realizing that pairing decisions affect which numbers become the minimums contributing to the final sum.
Approach 1: Sorting and Pairing Strategy (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
The simplest and most reliable strategy is to sort the array first. Once sorted, pair adjacent elements: (nums[0], nums[1]), (nums[2], nums[3]), and so on. The key insight is that in each pair, the smaller element contributes to the sum. Sorting ensures that small numbers are grouped together instead of being wasted as the minimum in pairs with very large numbers. After sorting, iterate through the array and add every element at an even index (0, 2, 4...) to the result. Sorting dominates the runtime at O(n log n), while the pairing scan is linear. This approach uses concepts from Sorting and a simple Greedy strategy.
Approach 2: Greedy Pairing with Counting Sort Optimization (Time: O(n + k), Space: O(k))
The constraints guarantee that numbers fall within a limited range (typically -10000 to 10000). Instead of sorting with comparison-based algorithms, build a frequency array and simulate a Counting Sort. Iterate through the frequency array in increasing order and track whether the current number should be included in the sum or skipped. Every second element encountered becomes the minimum of a pair and is added to the result. This effectively recreates the sorted order without performing an explicit sort. The complexity becomes O(n + k), where k is the numeric range. This method leverages Counting Sort and still follows the same greedy observation: maximize the contribution of smaller numbers by pairing them early.
Recommended for interviews: The sorting approach is the expected solution in most interviews. It is easy to reason about and clearly demonstrates the greedy insight that pairing adjacent numbers in sorted order maximizes the sum of pair minimums. The counting sort optimization shows deeper awareness of constraints and can reduce runtime to linear when the value range is bounded. Mentioning both approaches shows strong algorithmic judgment.
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:
The C code starts by sorting the array using the built-in qsort() function. Once sorted, we iterate over the array taking sum of every alternate element starting from index 0, because these represent the minimum in every pair if paired in sorted order.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as no additional space is used except for input.
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.
This C implementation utilizes counting sort for the defined range of input values. We update a count array and adjust it for each occurrence shifting values. The iteration through the count array allows us to easily compute the required sum by alternating over counts.
Time Complexity: O(n + range) due to counting sort.
Space Complexity: O(range) for the count array.
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.
Therefore, we can sort the array nums, then divide every two adjacent numbers into a group, and add the first number of each group.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Sorting and Pairing Strategy | Time Complexity: O(n log n) due to sorting. |
| Greedy Pairing Strategy with Counting Sort Optimization | Time Complexity: O(n + range) due to counting sort. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Pairing Strategy | O(n log n) | O(1) to O(log n) | General case. Most common interview solution and easiest to implement. |
| Greedy with Counting Sort Optimization | O(n + k) | O(k) | When the integer range is bounded. Avoids comparison sorting for linear performance. |
LeetCode Array Partition I Solution Explained - Java • Nick White • 15,418 views views
Watch 9 more video solutions →Practice Array Partition with our built-in code editor and test cases.
Practice on FleetCode