Code Implementation

class Solution:
    def minPairSum(self, nums):
        nums.sort()
        n = len(nums)
        max_pair_sum = 0
        for i in range(n // 2):
            pair_sum = nums[i] + nums[n - 1 - i]
            max_pair_sum = max(max_pair_sum, pair_sum)
        return max_pair_sum
      

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

import java.util.Arrays;
class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int maxPairSum = 0;
        for (int i = 0; i < n / 2; i++) {
            int pairSum = nums[i] + nums[n - 1 - i];
            maxPairSum = Math.max(maxPairSum, pairSum);
        }
        return maxPairSum;
    }
}
      

var minPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    let maxPairSum = 0;
    for (let i = 0; i < n / 2; i++) {
        let pairSum = nums[i] + nums[n - 1 - i];
        maxPairSum = Math.max(maxPairSum, pairSum);
    }
    return maxPairSum;
};
      

Problem Description

Given an array nums of even length, you must pair up the elements into n / 2 pairs (where n is the length of nums). Each element must be used exactly once and cannot be reused in multiple pairs.

For each pair, calculate the sum of its two elements. The maximum of these pair sums is called the maximum pair sum for your chosen pairing.

Your task is to minimize this maximum pair sum by choosing the best possible way to pair up the elements. Return the minimized maximum pair sum as an integer.

• You must use each element exactly once.
• There is always one valid solution.
• Input constraints: 2 <= nums.length <= 10^5, nums.length is even, 1 <= nums[i] <= 10^5.

Thought Process

At first glance, this problem seems to require checking all possible ways to pair up the numbers and then finding the pairing where the largest pair-sum is as small as possible. But with n elements, the number of possible pairings grows extremely quickly, making brute-force infeasible for large arrays.

Instead, let's think about what causes a large maximum pair sum. If we put the two largest numbers together, their sum will likely be the largest of any possible pair. Similarly, pairing the two smallest numbers together doesn't help us minimize the maximum sum.

The key insight is that to "balance" the pairs, we should try to pair the largest number with the smallest, the second largest with the second smallest, and so on. This way, each pair's sum is more evenly distributed, preventing any one pair from having an excessively large sum.

Solution Approach

Let's break down the optimized solution step by step:

1. Sort the Array: First, we sort nums in ascending order. This allows us to easily access the smallest and largest elements.
2. Pair Elements: We pair the smallest element with the largest, the next smallest with the next largest, and so on. For index i (starting from 0), we pair nums[i] with nums[n - 1 - i].
3. Track the Maximum Pair Sum: For each pair, calculate the sum and keep track of the largest sum we have seen.
4. Return the Result: After processing all pairs, return the largest sum encountered. This is the minimized maximum pair sum.

Why does this work? By always pairing the smallest available number with the largest, we "balance out" the sums, avoiding a situation where the largest two numbers combine to create an unavoidably large pair sum.

Example Walkthrough

Let's walk through an example with nums = [3, 5, 2, 3].

• Step 1: Sort the array.
  Sorted nums: [2, 3, 3, 5]
• Step 2: Pair smallest with largest.
  - Pair 1: nums[0] + nums[3] = 2 + 5 = 7
  - Pair 2: nums[1] + nums[2] = 3 + 3 = 6
• Step 3: Find the maximum pair sum.
  The pair sums are 7 and 6. The maximum is 7.
• Step 4: Return the result.
  The minimized maximum pair sum is 7.

Notice how pairing the largest with the smallest "spreads out" the larger numbers, preventing a single pair from having a much higher sum than the others.

Time and Space Complexity

• Brute-force Approach: Trying all possible pairings would have factorial time complexity, specifically O((n-1)!!) (double factorial), which is infeasible for large n.
• Optimized Approach:
  • Time Complexity: Sorting takes O(n \log n), and pairing in a single pass takes O(n). So overall: O(n \log n).
  • Space Complexity: If sorting in-place, the extra space is O(1) (ignoring recursion stack for some languages). If not, it may be O(n) depending on the sort implementation.

Summary

The key insight for minimizing the maximum pair sum is to pair the smallest element with the largest, the second smallest with the second largest, and so on. This approach ensures that the pair sums are as balanced as possible, preventing any one pair from having an excessively large sum. The algorithm is efficient, relying mainly on sorting and a single pass through the array, making it suitable even for large inputs.