### Problem statement

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, andThe

**maximum pair sum**is**minimized**.

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

Problem statement taken from: https://leetcode.com/problems/minimize-maximum-pair-sum-in-array

**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 <= 10^5
- n is even
- 1 <= nums[i] <= 10^5
```

### Explanation

#### Sorting

We sort the array first and then iterate over the loop to form pairs (i, j). i will start from index 0, and j will begin from the last index.

We increment and decrement i and j, respectively, to form the next pairs till i < j.

Let's check the algorithm first.

```
- sort(nums.begin(), nums.end())
maxSum = 0
i = 0
j = nums.size() - 1
- loop while i < j
- if nums[i] + nums[j] > maxSum
- maxSum = nums[i] + nums[j]
- i++
j--
- while end
- return maxSum
```

The time complexity of the above approach is **O(n * log(n))**, and the space complexity is **O(1)**.

Let's check our algorithm in **C++**, **Golang**, and **JavaScript**.

#### C++ solution

```
class Solution {
public:
int minPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int maxSum = 0, i = 0, j = nums.size() - 1;
while(i < j) {
if(nums[i] + nums[j] > maxSum) {
maxSum = nums[i] + nums[j];
}
i++;
j--;
}
return maxSum;
}
};
```

#### Golang solution

```
func minPairSum(nums []int) int {
sort.Ints(nums)
i, j := 0, len(nums) - 1
maxSum := 0
for i < j {
if nums[i] + nums[j] > maxSum {
maxSum = nums[i] + nums[j]
}
i++
j--
}
return maxSum
}
```

#### JavaScript solution

```
var minPairSum = function(nums) {
nums.sort((a, b) => a - b);
let i = 0, j = nums.length - 1;
let maxSum = 0;
while(i < j) {
maxSum = Math.max(nums[i] + nums[j], maxSum);
i++;
j--;
}
return maxSum;
};
```

Let's dry-run our algorithm to see how the solution works.

```
Input: nums = [3, 5, 5, 2, 4, 6]
Step 1: sort(nums.begin(), nums.end())
nums = [2, 3, 4, 5, 5, 6]
maxSum = 0
i = 0
j = nums.size() - 1
= 6 - 1
= 5
Step 2: loop while i < j
0 < 5
true
if nums[i] + nums[j] > maxSum
nums[0] + nums[5] > 0
2 + 6 > 0
8 > 0
true
maxSum = nums[i] + nums[j]
= nums[0] + nums[5]
= 2 + 6
= 8
i++
i = 1
j--
j = 4
Step 3: loop while i < j
1 < 4
true
if nums[i] + nums[j] > maxSum
nums[1] + nums[4] > 8
3 + 5 > 8
8 > 8
false
i++
i = 2
j--
j = 3
Step 4: loop while i < j
2 < 3
true
if nums[i] + nums[j] > maxSum
nums[2] + nums[3] > 8
4 + 5 > 8
9 > 8
true
maxSum = nums[i] + nums[j]
= nums[2] + nums[3]
= 4 + 5
= 9
i++
i = 3
j--
j = 2
Step 5: loop while i < j
3 < 2
false
Step 6: return maxSum
We return the answer as 9.
```

## Top comments (0)