# Array Partition
**Difficulty:** EASY
[External](https://leetcode.com/problems/array-partition)
Canonical: https://scaleengineer.com/dsa/problems/array-partition
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array
---
## Problem
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 <= 104`
* `nums.length == 2 * n`
* `-104 <= nums[i] <= 104`

# Approaches
## Sorting Approach
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.
**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)`.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- 1. Sort the input array `nums` in non-decreasing order.
- 2. Initialize a variable `sum` to 0.
- 3. Loop through the sorted array from index 0 to `nums.length - 1` with a step of 2.
- 4. In each iteration, add the element `nums[i]` to `sum`.
- 5. After the loop finishes, return `sum`.

## Counting Sort Approach
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.
**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.
**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.
### Explanation
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.
1. 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`.
2. Populate the `counts` array by iterating through the input `nums`.
3. Iterate through the numbers from `-10000` to `10000`. For each number, we process its occurrences.
4. 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.
5. This process effectively walks through the sorted sequence of numbers and picks every other one to add to the sum.

```java
class Solution {
    public int arrayPairSum(int[] nums) {
        // The range of numbers is [-10000, 10000].
        // We create a frequency array to count occurrences.
        // The size is 20001 to cover the range.
        // An offset of 10000 is used to map numbers to non-negative indices.
        // index = num + 10000
        int[] counts = new int[20001];
        for (int num : nums) {
            counts[num + 10000]++;
        }
        
        int maxSum = 0;
        // This flag helps us pick every other element from the sorted sequence.
        // 'true' means we are at an even-indexed position (0, 2, 4...) in the sorted list.
        boolean isFirstInPair = true; 
        
        // Iterate through the possible numbers from -10000 to 10000.
        for (int i = 0; i < counts.length; i++) {
            // While there are occurrences of the number `i - 10000`
            while (counts[i] > 0) {
                if (isFirstInPair) {
                    // This number is at an even position in the sorted list.
                    // Add it to the sum.
                    maxSum += (i - 10000);
                }
                // Toggle the flag for the next number in the sorted sequence.
                isFirstInPair = !isFirstInPair;
                // Decrement the count for this number.
                counts[i]--;
            }
        }
        
        return maxSum;
    }
}
```
### Algorithm
- 1. Define a constant `OFFSET = 10000` and create an integer array `counts` of size `2 * OFFSET + 1`.
- 2. Iterate through the input `nums` array. For each `num`, increment `counts[num + OFFSET]`.
- 3. Initialize `maxSum = 0` and a boolean `isFirstInPair = true`.
- 4. Iterate from `i = 0` to `counts.length - 1`.
- 5. Inside this loop, have a `while` loop that runs as long as `counts[i] > 0`.
- 6. Inside the `while` loop:
    - If `isFirstInPair` is true, add the current number (`i - OFFSET`) to `maxSum`.
    - Flip the value of `isFirstInPair`.
    - Decrement `counts[i]`.
- 7. After the loops complete, return `maxSum`.

# Solutions
### Java

```java
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 ; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var arrayPairSum = function (
  nums,
) {
  nums.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 0; i < nums.length; i += 2) {
    ans += nums[i];
  }
  return ans;
};

```

### CPP

```cpp
class 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 ; } };
```

### Python

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