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 minimizedmaximum pair sum after optimally pairing up the elements.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

Solution

Method 1 – Two Pointers After Sorting

Intuition

To minimize the maximum pair sum, pair the smallest element with the largest, the second smallest with the second largest, and so on. This balances the sums and ensures the largest pair sum is as small as possible.

Approach

  1. Sort the array in ascending order.
  2. Use two pointers: one at the start, one at the end.
  3. Pair elements at the start and end, moving inward.
  4. For each pair, compute the sum and track the maximum.
  5. Return the minimum possible maximum pair sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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 / 2; ++i) {
            ans = max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func minPairSum(nums []int) int {
    sort.Ints(nums)
    ans := 0
    n := len(nums)
    for i := 0; i < n/2; i++ {
        if nums[i]+nums[n-1-i] > ans {
            ans = nums[i] + nums[n-1-i]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, n = nums.length;
        for (int i = 0; i < n / 2; i++) {
            ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minPairSum(nums: IntArray): Int {
        nums.sort()
        var ans = 0
        val n = nums.size
        for (i in 0 until n / 2) {
            ans = maxOf(ans, nums[i] + nums[n - 1 - i])
        }
        return ans
    }
}
1
2
3
4

def min_pair_sum(nums: list[int]) -> int:
    nums.sort()
    n = len(nums)
    return max(nums[i] + nums[n - 1 - i] for i in range(n // 2))
1
2
3
4
5
6
7

impl Solution {
    pub fn min_pair_sum(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let n = nums.len();
        (0..n/2).map(|i| nums[i] + nums[n-1-i]).max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    minPairSum(nums: number[]): number {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        let ans = 0;
        for (let i = 0; i < n / 2; ++i) {
            ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the array.
  • 🧺 Space complexity: O(1), if sorting in-place; otherwise O(n).