LeetCode 1877 - Minimize Maximum Pair Sum in Array

The problem asks us to pair elements in an array of even length such that the largest sum among all pairs is minimized. In simpler terms, imagine we have a collection of numbers and we want to form pairs of two numbers each. Each number can only belong to one pair.

leetcodemediumarraytwo-pointersgreedysorting

LeetCode Problem 1877

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to pair elements in an array of even length such that the largest sum among all pairs is minimized. In simpler terms, imagine we have a collection of numbers and we want to form pairs of two numbers each. Each number can only belong to one pair. Once we pair them, each pair has a sum. Out of all these sums, we look for the largest one - this is the "maximum pair sum." Our goal is to organize the pairings so that this maximum is as small as possible.

The input is an array nums of even length n, where each number is a positive integer. The output is a single integer, the minimized maximum pair sum after optimal pairing. Constraints indicate that n can be up to 100,000, and each element can be up to 100,000. This means any approach that is worse than O(n log n) or O(n) in time complexity may be too slow. The input is guaranteed to be even in length, which simplifies pairing logic.

Important edge cases include arrays where all elements are the same, arrays with a mix of very large and very small numbers, and arrays with the minimum length of 2.

Approaches

The brute-force approach would consider all possible pairings, calculate the maximum pair sum for each arrangement, and return the smallest maximum found. This guarantees correctness but is infeasible because the number of pairings grows factorially with n. Specifically, with n elements, there are (n-1)!! ways to pair them, which is computationally impossible for n up to 100,000.

The key insight for an optimal approach is based on sorting. If we sort the array in ascending order, pairing the smallest element with the largest, the second smallest with the second largest, and so on ensures that the sums are balanced and the maximum pair sum is minimized. This works because pairing extremes prevents creating a very large sum with two large numbers, which would increase the maximum unnecessarily.

Approach Time Complexity Space Complexity Notes
Brute Force O((n-1)!!) O(n) Check all possible pairings, infeasible for large n
Optimal O(n log n) O(1) or O(n) Sort array and pair smallest with largest iteratively

Algorithm Walkthrough

  1. Sort the input array nums in ascending order. This allows easy access to the smallest and largest elements.
  2. Initialize a variable max_pair_sum to 0. This will store the maximum pair sum found.
  3. Use two pointers, left starting at the beginning of the array and right starting at the end.
  4. While left is less than right, compute the sum of nums[left] + nums[right].
  5. Update max_pair_sum to be the maximum of its current value and the sum computed in the previous step.
  6. Increment left and decrement right to move inward and form the next pair.
  7. Once all pairs are processed, return max_pair_sum.

Why it works: Pairing the smallest and largest elements minimizes the impact of large numbers on the maximum sum. This greedy strategy guarantees that no sum exceeds the minimal possible maximum because any other pairing would either leave large numbers paired together, increasing the maximum, or small numbers paired with small numbers, which does not reduce the maximum. Sorting ensures that the extremes are always paired optimally.

Python Solution

from typing import List

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        max_pair_sum = 0
        left, right = 0, len(nums) - 1
        while left < right:
            pair_sum = nums[left] + nums[right]
            max_pair_sum = max(max_pair_sum, pair_sum)
            left += 1
            right -= 1
        return max_pair_sum

The implementation first sorts the array, allowing access to smallest and largest elements easily. The while loop iterates over pairs from the outside in, computing sums and tracking the largest sum seen. Finally, the result is returned as the minimized maximum pair sum.

Go Solution

import "sort"

func minPairSum(nums []int) int {
    sort.Ints(nums)
    maxPairSum := 0
    left, right := 0, len(nums)-1
    for left < right {
        pairSum := nums[left] + nums[right]
        if pairSum > maxPairSum {
            maxPairSum = pairSum
        }
        left++
        right--
    }
    return maxPairSum
}

In Go, the implementation mirrors Python closely. We sort the slice with sort.Ints, then use two indices to traverse the array from both ends, updating the maximum sum along the way. Go handles slices efficiently, so no additional space is required beyond the sorted array.

Worked Examples

Example 1: nums = [3,5,2,3]

Step left right nums[left] nums[right] pair_sum max_pair_sum
1 0 3 2 5 7 7
2 1 2 3 3 6 7

Return 7.

Example 2: nums = [3,5,4,2,4,6]

Step left right nums[left] nums[right] pair_sum max_pair_sum
1 0 5 2 6 8 8
2 1 4 3 4 7 8
3 2 3 4 5 9 9

Here, notice the initial sort changes the array to [2,3,3,4,4,5,6]. The optimal pairing gives a maximum of 8, confirmed by the algorithm.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime; pairing is linear O(n)
Space O(1) (Python) / O(n) (Go sort) Only constant extra space for pointers; sorting may require extra depending on implementation

Sorting is the key step for achieving efficiency. The pairing itself is linear and does not increase complexity.

Test Cases

# Provided examples
assert Solution().minPairSum([3,5,2,3]) == 7
assert Solution().minPairSum([3,5,4,2,4,6]) == 8

# Edge cases
assert Solution().minPairSum([1,1]) == 2  # minimal input
assert Solution().minPairSum([1,100000]) == 100001  # large numbers
assert Solution().minPairSum([1,2,3,4,5,6,7,8]) == 9  # sequential numbers
assert Solution().minPairSum([5,5,5,5]) == 10  # all equal
assert Solution().minPairSum([1,2,2,1]) == 3  # repeated numbers
Test Why
[3,5,2,3] Basic small array example
[3,5,4,2,4,6] Example with multiple pairs, repeated numbers
[1,1] Minimum input size
[1,100000] Large element to test limits
[1,2,3,4,5,6,7,8] Sequential numbers, general case
[5,5,5,5] All elements equal
[1,2,2,1] Repeated elements

Edge Cases

Minimum size array: When nums has only two elements, the algorithm still works as the while loop executes once and returns the sum of the two numbers.

All elements equal: If every element in nums is the same, any pairing will yield the same sum. The algorithm handles this gracefully because max_pair_sum correctly updates but never changes from the uniform sum.

Large disparities: Arrays with very small and very large numbers could lead to incorrect results if a naive approach pairs the two largest together. By sorting and pairing extremes, the algorithm guarantees that large numbers are paired with small ones, minimizing the maximum sum effectively.