Array Partition

Easy

#0544Time: 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)`.

Patterns

Greedy

Algorithms

Sorting Counting Sort

Data structures

Array

Prompt

Given an integer array nums of 2n integers, group these integers into n pairs (a₁, b₁), (a₂, b₂), ..., (a_n, b_n) such that the sum of min(a_i, b_i) 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 <= 10⁴
nums.length == 2 * n
-10⁴ <= nums[i] <= 10⁴

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

1. Sort the input array nums in non-decreasing order.
1. Initialize a variable sum to 0.
1. Loop through the sorted array from index 0 to nums.length - 1 with a step of 2.
1. In each iteration, add the element nums[i] to sum.
1. After the loop finishes, return sum.

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.

1import java.util.Arrays;2 3class Solution {4    public int arrayPairSum(int[] nums) {5        // Sort the array in non-decreasing order.6        Arrays.sort(nums);7        8        int maxSum = 0;9        // Iterate through the sorted array, taking every second element.10        // These are the smaller elements of each optimal pair.11        for (int i = 0; i < nums.length; i += 2) {12            maxSum += nums[i];13        }14        15        return maxSum;16    }17}

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.

Given that the values in the input array are within a fixed and relatively small range (-10^4 to 10^4), we can use a more efficient sorting technique than comparison-based sorting. A counting sort or a similar frequency-counting method can sort the elements in linear time. This approach avoids the O(N log N) bottleneck of general-purpose sorting algorithms.

Algorithm

1. Define a constant OFFSET = 10000 and create an integer array counts of size 2 * OFFSET + 1.
1. Iterate through the input nums array. For each num, increment counts[num + OFFSET].
1. Initialize maxSum = 0 and a boolean isFirstInPair = true.
1. Iterate from i = 0 to counts.length - 1.
1. Inside this loop, have a while loop that runs as long as counts[i] > 0.
1. Inside the while loop:
- If isFirstInPair is true, add the current number (i - OFFSET) to maxSum.
- Flip the value of isFirstInPair.
- Decrement counts[i].
1. After the loops complete, return maxSum.

Walkthrough

The strategy is the same as the first approach: sum the elements that would be at even indices in a sorted version of the array. However, instead of explicitly sorting, we generate the sorted sequence on the fly using a frequency map.

Create a frequency array, let's call it counts, to store the number of occurrences of each integer. Since the numbers can be negative, we use an offset. The range is [-10000, 10000], so we can use an array of size 20001 and an offset of 10000. counts[num + 10000] will store the frequency of num.
Populate the counts array by iterating through the input nums.
Iterate through the numbers from -10000 to 10000. For each number, we process its occurrences.
We need to simulate pairing. We can use a boolean flag, say isFirstInPair, which starts as true. When we encounter a number, we add it to the sum if isFirstInPair is true, then flip the flag. We do this for each occurrence of the number.
This process effectively walks through the sorted sequence of numbers and picks every other one to add to the sum.

1class Solution {2    public int arrayPairSum(int[] nums) {3        // The range of numbers is [-10000, 10000].4        // We create a frequency array to count occurrences.5        // The size is 20001 to cover the range.6        // An offset of 10000 is used to map numbers to non-negative indices.7        // index = num + 100008        int[] counts = new int[20001];9        for (int num : nums) {10            counts[num + 10000]++;11        }12        13        int maxSum = 0;14        // This flag helps us pick every other element from the sorted sequence.15        // 'true' means we are at an even-indexed position (0, 2, 4...) in the sorted list.16        boolean isFirstInPair = true; 17        18        // Iterate through the possible numbers from -10000 to 10000.19        for (int i = 0; i < counts.length; i++) {20            // While there are occurrences of the number `i - 10000`21            while (counts[i] > 0) {22                if (isFirstInPair) {23                    // This number is at an even position in the sorted list.24                    // Add it to the sum.25                    maxSum += (i - 10000);26                }27                // Toggle the flag for the next number in the sorted sequence.28                isFirstInPair = !isFirstInPair;29                // Decrement the count for this number.30                counts[i]--;31            }32        }33        34        return maxSum;35    }36}

Complexity

Time

O(N + K), where N is the number of elements in `nums` and K is the range of possible values (`20001`). The first loop to populate the `counts` array takes `O(N)`. The second nested loop structure might look complex, but the inner `while` loop altogether runs exactly `N` times across all iterations of the outer `for` loop. So, the second part is `O(N + K)`. Since K is a constant, the overall complexity is `O(N)`.

Space

O(K), where K is the range of values. We use an auxiliary array of size `20001` to store frequencies. Since K is constant based on the problem constraints, this can be considered O(1) space.

Trade-offs

Pros

More efficient than the comparison-based sorting approach with a linear time complexity.

Cons

The space complexity depends on the range of numbers. If the range were much larger, this approach would become impractical due to memory constraints.
Slightly more complex to implement than the direct sorting approach.

Solutions

Solution

1class 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 ; } }

1/** * @param {number[]} nums * @return {number} */ var arrayPairSum = function (2  nums,3) {4  nums.sort((a, b) => a - b);5  let ans = 0;6  for (let i = 0; i < nums.length; i += 2) {7    ans += nums[i];8  }9  return ans;10};

1class Solution { public: int arrayPairSum ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int ans = 0 ; for ( int i = 0 ; i < nums . size (); i += 2 ) ans += nums [ i ]; return ans ; } };

1class Solution : def arrayPairSum ( self , nums : List [ int ]) -> int : return sum ( sorted ( nums )[:: 2 ])

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.

← Previous

Previous problem

Next problem