1877. Minimize Maximum Pair Sum in Array

Problem Description

Given an array nums of even length n, pair up the elements of nums into n/2 pairs such that each element is in exactly one pair, and the maximum pair sum is minimized. Return the minimized maximum pair sum.

Example 1:

Input: nums = [3,5,2,3] Output: 7 Explanation: The pairs are (3,3) and (5,2), and the maximum pair sum is max(3+3, 5+2) = 7.

Example 2:

Input: nums = [3,5,4,2,4,6] Output: 8 Explanation: The pairs are (2,6), (3,5), (4,4), and the maximum pair sum is max(8, 8, 8) = 8.

Solution: Greedy Approach

The optimal strategy to minimize the maximum pair sum is to pair the smallest element with the largest element, the second smallest with the second largest, and so on. This ensures that the sum of each pair is as close as possible to the average of the elements.

Algorithm:

1. Sort the array: Sort the input array nums in ascending order.
2. Two-pointer approach: Use two pointers, left and right, initialized to the beginning and end of the sorted array, respectively.
3. Calculate pair sums: In each iteration, calculate the sum of the elements at nums[left] and nums[right].
4. Update maximum pair sum: Update the maxPairSum variable with the maximum of the current maxPairSum and the current pair sum.
5. Move pointers: Increment left and decrement right to consider the next pair.
6. Repeat: Repeat steps 3-5 until left and right cross each other.
7. Return: Return the final maxPairSum.

Time and Space Complexity Analysis

• Time Complexity: O(n log n), dominated by the sorting step.
• Space Complexity: O(log n) or O(1) depending on the sorting algorithm used (in-place sorting like merge sort uses O(log n) extra space, while others can use O(1)).

Code Implementation

Python:

def minPairSum(nums):
    nums.sort()
    left = 0
    right = len(nums) - 1
    maxPairSum = 0
    while left < right:
        maxPairSum = max(maxPairSum, nums[left] + nums[right])
        left += 1
        right -= 1
    return maxPairSum

Java:

import java.util.Arrays;
 
class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int maxPairSum = 0;
        while (left < right) {
            maxPairSum = Math.max(maxPairSum, nums[left] + nums[right]);
            left++;
            right--;
        }
        return maxPairSum;
    }
}

C++:

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int minPairSum(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        int left = 0;
        int right = nums.size() - 1;
        int maxPairSum = 0;
        while (left < right) {
            maxPairSum = std::max(maxPairSum, nums[left] + nums[right]);
            left++;
            right--;
        }
        return maxPairSum;
    }
};

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var minPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    let left = 0;
    let right = nums.length - 1;
    let maxPairSum = 0;
    while (left < right) {
        maxPairSum = Math.max(maxPairSum, nums[left] + nums[right]);
        left++;
        right--;
    }
    return maxPairSum;
};

These code examples all follow the same algorithm and achieve the same result. The choice of language depends on your preferences and the context of the problem. All have the same time and space complexity as analyzed above.