Minimize Maximum Pair Sum in Array

Problem Statement

In mathematical problems involving pairs, a common inquiry involves the sum derived from each pair, termed the pair sum, which equals the addition of its two elements (a, b), thus a + b. Among multiple pairs, there's a specific interest in identifying the maximum value from these sums, known as the maximum pair sum.

For illustrative purposes with pairing in an array, consider pairs like (1,5), (2,3) and (4,4); the maximum pair sum is determined by max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

The main problem here involves an array nums with an even length n. You need to pair its elements into n/2 pairs with each element used exactly once, with an objective to minimize the maximum pair sum. The challenge is to find and return this minimized maximum pair sum value after arranging the pairs strategically.

Examples

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 <= 105
• n is even.
• 1 <= nums[i] <= 105

Approach and Intuition

Understanding the approach to solving this problem revolves around some basic insights and strategic arrangements:

1. Pairing Strategy: Since the goal is to minimize the maximum pair sum, a strategic way to form pairs is crucial. Consider pairing the smallest available element with the largest. This tends to evenly distribute the large values across the pairs, preventing any single pair from having an excessively high sum, which might become the maximum.

2. Practical Implementation:

   • First, sort the array nums to easily access the smallest and largest elements.
   • Utilize two pointers or indices to help in the pairing process: one starting at the beginning (smallest element after sorting) and the other at the end (largest element).
   • Subsequently, form pairs using these pointers: one pointer at the start (smallest index) and the other at the end (largest index), then adjust both pointers inwardly to form the next pair, and so on until you reach the middle of the list.
   • Compute the pair sum for each formed pair and continually track the maximum of these sums throughout the process.

3. Optimal Efficiency: Given the constraints that n (length of nums) could be as large as 105, an efficient sorting algorithm is crucial, generally O(n log n). The subsequent pairing and checking for maximum operations are linear, O(n). Thus, the entire approach is dominated by the sorting step.

In simpler terms, it can be likened to mitigating financial disparities in wealth distribution by pairing the richest with the poorest, hence averting the concentration of wealth (or large values) that could lead to greater disparities (or maximum sums in this context). This strategy ensures a more balanced outcome, minimally impacting the overall maximum sum that can be observed in any single pairing.

Solutions

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

class Solution {
  public int minimumPairSum(int[] values) {
    Arrays.sort(values);

    int maxPairSum = 0;
    for (int i = 0; i < values.length / 2; i++) {
      maxPairSum = Math.max(maxPairSum, values[i] + values[values.length - 1 - i]);
    }

    return maxPairSum;

  }
}