Minimize Maximum Pair Sum in Array - Video Solutions

Problem Overview: You are given an even-length array of integers. Pair up the elements so every number belongs to exactly one pair. Among all pairs, compute the maximum pair sum and minimize that value. The goal is to choose pairings that keep the largest pair sum as small as possible.

Approach 1: Brute Force Pairing (Exponential Time)

The brute force idea is to try every possible way to form pairs, compute the maximum pair sum for each configuration, and return the minimum among them. This requires generating all pair combinations and tracking the worst pair sum per configuration. The number of pairings grows extremely fast, making the time complexity roughly O((n-1)!!) (factorial-like growth) with O(n) auxiliary space for recursion or bookkeeping. This approach mainly helps you reason about the objective: minimizing the largest pair sum across all pairings.

Approach 2: Sorting and Two-Pointer Greedy (O(n log n) time, O(1) space)

The key observation: the maximum pair sum is minimized when the smallest element is paired with the largest element. After sorting the array, use two pointers—one at the beginning and one at the end. Pair nums[left] with nums[right], compute their sum, and track the maximum across all such pairs. Move both pointers inward until they meet. Sorting ensures large numbers are balanced by small numbers, preventing a large value from being paired with another large value. This greedy pairing strategy produces the optimal answer.

This approach relies on sorting to structure the numbers and then applies a classic two pointers sweep from both ends. The greedy decision—always pairing extremes—keeps the worst-case pair sum as small as possible. Time complexity is dominated by sorting at O(n log n), while the pointer scan runs in O(n) time with O(1) extra space.

Approach 3: Direct Index Pairing After Sort (O(n log n) time, O(1) space)

This is a simplified variation once the array is sorted. Instead of explicitly maintaining two pointers, iterate through the first half of the array and pair index i with n - 1 - i. Each iteration calculates nums[i] + nums[n-1-i] and updates the maximum pair sum seen so far. The logic is identical to the two-pointer method but uses direct index symmetry. The algorithm still depends on sorting (O(n log n)) and scans only half the array (O(n)), using constant extra space.

Recommended for interviews: The expected solution is the greedy strategy using sorting plus two pointers. Interviewers want to see that you recognize the pairing pattern: smallest with largest minimizes the worst-case sum. Mentioning the brute force approach shows problem understanding, but implementing the greedy greedy solution demonstrates algorithmic insight and leads directly to the optimal O(n log n) implementation.