# Minimize Maximum Pair Sum in Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-maximum-pair-sum-in-array)
Canonical: https://scaleengineer.com/dsa/problems/minimize-maximum-pair-sum-in-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [eBay](https://scaleengineer.com/companies/ebay)
---
## Problem
The **pair sum** of a pair `(a,b)` is equal to `a + b`. The **maximum pair sum** is the largest **pair sum** in a list of pairs.

* For example, if we have pairs `(1,5)`, `(2,3)`, and `(4,4)`, the **maximum pair sum** would be `max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8`.

Given an array `nums` of **even** length `n`, pair up the elements of `nums` into `n / 2` pairs such that:

* Each element of `nums` is in **exactly one** pair, and
* The **maximum pair sum** is **minimized**.

Return _the minimized **maximum pair sum** after optimally pairing up the elements_.

**Example 1:**

**Input:** nums = [3,5,2,3]
**Output:** 7
**Explanation:** The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

**Example 2:**

**Input:** nums = [3,5,4,2,4,6]
**Output:** 8
**Explanation:** The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

**Constraints:**

* `n == nums.length`
* `2 <= n <= 105`
* `n` is **even**.
* `1 <= nums[i] <= 105`

# Approaches
## Sorting and Two Pointers
This approach is based on the intuition that to minimize the maximum pair sum, we should balance the pairs by pairing the smallest elements with the largest ones. Sorting the array allows us to easily identify these elements.
**Time:** O(N log N). The dominant part of this algorithm is sorting the array, which typically takes `O(N log N)` time. The subsequent two-pointer scan to find the pair sums takes linear time, `O(N)`, which is overshadowed by the sorting time. · **Space:** O(log N) to O(N). The space complexity is determined by the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which requires `O(log N)` space on average for the recursion stack, but can take up to `O(N)` in the worst case.
**Pros:** The logic is straightforward and easy to implement.; It's a general solution that works regardless of the range of values in the input array.
**Cons:** The time complexity of `O(N log N)` is not optimal for this problem, given the constraints on the input values.; The space complexity depends on the sorting algorithm's implementation and can be `O(N)` in the worst case.
### Explanation
The core idea is that the optimal pairing strategy involves matching the smallest numbers with the largest numbers. To achieve this, we first sort the array `nums` in non-decreasing order. After sorting, the smallest element is at `nums[0]` and the largest is at `nums[n-1]`. The second smallest is at `nums[1]` and the second largest is at `nums[n-2]`, and so forth. We can then use a two-pointer technique. One pointer, `left`, starts at the beginning of the sorted array, and another pointer, `right`, starts at the end. We form a pair with the elements at these pointers, calculate their sum, and update our running maximum sum. Then, we move both pointers inwards (`left++`, `right--`) to consider the next pair of smallest and largest available elements. This process continues until the pointers meet or cross, ensuring all elements are paired up. The final result is the minimized maximum pair sum.

```java
import java.util.Arrays;

class Solution {
    public int minPairSum(int[] nums) {
        // Step 1: Sort the array
        Arrays.sort(nums);
        
        int maxSum = 0;
        // Step 3: Initialize two pointers
        int left = 0;
        int right = nums.length - 1;
        
        // Step 4-7: Iterate and find pair sums
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            maxSum = Math.max(maxSum, currentSum);
            left++;
            right--;
        }
        
        // Step 8: Return the result
        return maxSum;
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. Initialize a variable `maxSum` to store the maximum pair sum, setting it to 0 initially.
3. Initialize two pointers: `left` at the beginning of the array (index 0) and `right` at the end of the array (index `n-1`).
4. Iterate with a `while` loop as long as `left` is less than `right`.
5. Inside the loop, calculate the sum of the elements pointed to by `left` and `right`: `currentSum = nums[left] + nums[right]`.
6. Update `maxSum` to be the maximum of its current value and `currentSum`.
7. Move the pointers closer to the center: increment `left` and decrement `right`.
8. After the loop finishes, return `maxSum`.

## Counting Sort and Two Pointers
This approach leverages the problem's constraint on the range of input values to achieve a linear time solution. By using a frequency array (similar to Counting Sort), we can efficiently find the smallest and largest available numbers to pair up without performing a full comparison-based sort.
**Time:** O(N + K), where `N` is the length of `nums` and `K` is the range of values. Populating the `counts` array takes `O(N)`. The two-pointer scan on the `counts` array takes `O(K)` time because the `low` and `high` pointers each traverse the range of values at most once. Thus, the total time complexity is linear. · **Space:** O(K), where `K` is the maximum possible value in `nums`. We need an auxiliary array `counts` of size `K+1` to store the frequencies of the numbers. Given the constraint `nums[i] <= 10^5`, this is a fixed amount of extra space.
**Pros:** Achieves linear time complexity, which is more efficient than the sorting-based approach for the given constraints.; The logic remains intuitive: pair the smallest with the largest.
**Cons:** This approach is only efficient when the range of values (`K`) is manageable. If `K` were very large, the space complexity would become a problem.; It is less general than the sorting approach as it relies on the values being non-negative integers within a specific range.
### Explanation
Instead of sorting the array, we can use a more direct method to find the smallest and largest available elements by taking advantage of the value constraints (`1 <= nums[i] <= 10^5`). We can create a frequency array, `counts`, to store how many times each number appears in the input `nums`. The size of this array will be based on the maximum possible value (100001).

After populating the `counts` array in a single pass over `nums`, we use two pointers, `low` and `high`, initialized to the start (1) and end (100000) of our value range. We move `low` forward until we find a number with a count greater than zero (the smallest available number). Similarly, we move `high` backward to find the largest available number. We then pair these two numbers, update our maximum sum, and decrement their counts in the frequency array. This process is repeated until all numbers are paired. This avoids the `O(N log N)` cost of sorting, leading to a more efficient `O(N + K)` solution, where `K` is the range of values.

```java
class Solution {
    public int minPairSum(int[] nums) {
        // The maximum value is constrained to 100000
        int maxVal = 100000;
        int[] counts = new int[maxVal + 1];
        
        // Populate the frequency array
        for (int num : nums) {
            counts[num]++;
        }
        
        int maxSum = 0;
        int low = 1;
        int high = maxVal;
        
        // Use two pointers on the frequency array
        while (low <= high) {
            // Find the smallest available number
            if (counts[low] == 0) {
                low++;
                continue;
            }
            // Find the largest available number
            if (counts[high] == 0) {
                high--;
                continue;
            }
            
            // Form a pair and update maxSum
            maxSum = Math.max(maxSum, low + high);
            
            // Decrement counts for the used numbers
            counts[low]--;
            counts[high]--;
        }
        
        return maxSum;
    }
}
```
### Algorithm
1. Determine the maximum possible value `K` from the input constraints (e.g., 100000).
2. Create a frequency array `counts` of size `K+1` to store the count of each number.
3. Iterate through the input array `nums` and populate the `counts` array. For each `num` in `nums`, increment `counts[num]`.
4. Initialize `maxSum = 0`.
5. Initialize two pointers: `low` starting at 1 and `high` starting at `K`.
6. Loop while `low <= high`:
   a. If `counts[low]` is 0, it means the number `low` is not present or has been used up. Increment `low` and continue.
   b. If `counts[high]` is 0, decrement `high` and continue.
   c. If both `counts[low]` and `counts[high]` are greater than 0, we have found the current smallest and largest available numbers.
   d. Calculate their sum `low + high` and update `maxSum = Math.max(maxSum, low + high)`.
   e. Decrement `counts[low]` and `counts[high]` to mark them as used.
7. Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int minPairSum(int[] nums) {
    Arrays.sort(nums);
    int ans = 0, n = nums.length;
    for (int i = 0; i < n >> 1; ++i) {
      ans = Math.max(ans, nums[i] + nums[n - i - 1]);
    }
    return ans;
  }
}

```

### JavaScript

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

```

### CSharp

```csharp
public class Solution {
    public int MinPairSum(int[] nums) {
        Array.Sort(nums);
        int ans = 0, n = nums.Length;
        for (int i = 0; i < n >> 1; ++i) {
            ans = Math.Max(ans, nums[i] + nums[n - i - 1]);
        }
        return ans;
    }
}
```

### CPP

```cpp
class Solution {
public:
  int minPairSum(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int ans = 0, n = nums.size();
    for (int i = 0; i < n >> 1; ++i) {
      ans = max(ans, nums[i] + nums[n - i - 1]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minPairSum(self, nums: List[int]) -> int: nums . sort() n = len(nums) return max(x + nums[n - i - 1] for i, x in enumerate(nums[: n >> 1]))

```