Minimize Maximum Pair Sum in Array

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.

The problem asks us to pair elements in an array of even length such that the maximum pair sum is minimized. A naive approach would be to try all possible pairings and compute the maximum pair sum for each pairing, then take the minimum of those. However, this would be very inefficient. A better approach is to sort the array and then pair the smallest and largest elements, the second smallest and second largest, and so on. This ensures that the maximum pair sum is minimized.

Optimal Solution

1. Sort the array: Sort the input array nums in ascending order.
2. Pair elements: Pair the elements at the beginning and end of the sorted array. Specifically, pair nums[i] with nums[n - 1 - i] for i from 0 to n / 2 - 1.
3. Calculate maximum pair sum: Calculate the maximum pair sum among all the pairs formed in the previous step.

Code Implementation (Python)

def min_max_pair_sum(nums):
    nums.sort()
    max_sum = 0
    n = len(nums)
    for i in range(n // 2):
        max_sum = max(max_sum, nums[i] + nums[n - 1 - i])
    return max_sum

# Example Usage
nums1 = [3, 5, 2, 3]
print(f"Input: {nums1}, Output: {min_max_pair_sum(nums1)}")  # Output: 7

nums2 = [3, 5, 4, 2, 4, 6]
print(f"Input: {nums2}, Output: {min_max_pair_sum(nums2)}")  # Output: 8

Code Implementation (Java)

import java.util.Arrays;

class Solution {
    public int minMaxPairSum(int[] nums) {
        Arrays.sort(nums);
        int maxSum = 0;
        int n = nums.length;
        for (int i = 0; i < n / 2; i++) {
            maxSum = Math.max(maxSum, nums[i] + nums[n - 1 - i]);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {3, 5, 2, 3};
        System.out.println("Input: {3, 5, 2, 3}, Output: " + solution.minMaxPairSum(nums1)); // Output: 7

        int[] nums2 = {3, 5, 4, 2, 4, 6};
        System.out.println("Input: {3, 5, 4, 2, 4, 6}, Output: " + solution.minMaxPairSum(nums2)); // Output: 8
    }
}

Big(O) Run-time Analysis

• Sorting: The dominant operation is sorting the array, which takes O(n log n) time, where n is the number of elements in the array. Common sorting algorithms like merge sort or quicksort have this time complexity.
• Pairing and Summation: After sorting, the loop iterates n / 2 times, performing constant-time operations (addition and comparison) in each iteration. This part takes O(n) time.
• Overall: The overall time complexity is dominated by the sorting step, so the run-time complexity is O(n log n).

Big(O) Space Usage Analysis

• Sorting: The space complexity depends on the sorting algorithm used.
  • If an in-place sorting algorithm like heapsort is used, the space complexity is O(1). In-place sorting algorithms modify the array directly without requiring additional space.
  • If an algorithm like merge sort is used, which requires additional space for merging, the space complexity is O(n) in the worst case.
• Other Variables: The algorithm uses a constant number of additional variables (max_sum, i, n), which take O(1) space.
• Overall: If we use an in-place sorting algorithm, the overall space complexity is O(1). If we use a sorting algorithm that requires O(n) extra space, then the overall space complexity will be O(n).

Edge Cases

1. Empty Array: The problem statement specifies that n >= 2, so an empty array is not a valid input. However, if we were to handle it, we would need to raise an exception or return a default value.
2. Array with Two Elements: The algorithm works correctly for an array with two elements. The array is sorted, and the two elements are paired and summed.
3. Array with Duplicate Elements: The algorithm handles duplicate elements correctly. The array is sorted, and the duplicate elements are paired appropriately to minimize the maximum pair sum.
4. Large Input Array: For very large input arrays (e.g., n = 10^5), the O(n log n) time complexity might become a concern. However, since n is limited to 10^5, the algorithm should still run efficiently.
5. Negative Numbers: If the input array contains negative numbers, the algorithm still works correctly. Sorting the array will place the most negative numbers at the beginning and the most positive numbers at the end, ensuring optimal pairing.