Problem Description

You are given an array nums of even length n. Your task is to pair up all elements in the array into n/2 pairs such that each element belongs to exactly one pair.

For any pair (a, b), the pair sum is defined as a + b. Among all the pairs you create, there will be a maximum pair sum (the largest sum among all pairs).

Your goal is to arrange the pairs in such a way that this maximum pair sum is as small as possible.

For example, if you have the array [1, 2, 3, 4]:

• One way to pair: (1, 2) and (3, 4) gives pair sums of 3 and 7, with maximum = 7
• Another way: (1, 4) and (2, 3) gives pair sums of 5 and 5, with maximum = 5
• The second pairing is better because its maximum pair sum (5) is smaller than the first (7)

The solution uses a greedy strategy: after sorting the array, pair the smallest element with the largest, the second smallest with the second largest, and so on. This approach ensures that we balance out the pairs - avoiding situations where large numbers are paired together, which would create unnecessarily large pair sums.

The code sorts the array, then pairs elements from opposite ends: nums[0] with nums[n-1], nums[1] with nums[n-2], etc. It calculates all these pair sums and returns the maximum among them, which represents the minimized maximum pair sum.

Intuition

The key insight is to think about what happens when we create pairs. If we pair two large numbers together, we get a very large sum. Similarly, pairing two small numbers gives us a small sum, but this wastes the opportunity to use those small numbers to "balance out" the large ones.

Consider what we're trying to minimize: the maximum pair sum. This means we want to avoid creating any pair that's too large. The worst-case scenario would be pairing the two largest numbers together - this would create an unnecessarily large maximum.

So how do we prevent any pair from becoming too large? By ensuring that whenever we include a large number in a pair, we balance it with a small number. This naturally leads us to the strategy of pairing opposites: the largest with the smallest, the second-largest with the second-smallest, and so on.

Why does this work? Think of it as a balancing act. Each large number needs to be "diluted" by pairing it with a small number. If we pair max with min, and second_max with second_min, we're distributing the "burden" of large numbers evenly across all pairs.

This greedy approach ensures that no single pair bears too much weight. Any other pairing strategy would result in at least one pair having a larger sum - either by putting two relatively large numbers together, or by not optimally balancing the extreme values.

The mathematical reasoning is that for any sorted array, the sum nums[i] + nums[n-1-i] creates the most balanced pairs, minimizing the maximum among all such sums.

Learn more about Greedy, Two Pointers and Sorting patterns.

Solution Approach

The implementation follows a straightforward greedy algorithm with these steps:

Step 1: Sort the array

nums.sort()

First, we sort the array in ascending order. This arranges the elements so we can easily identify and pair the smallest with the largest elements.

Step 2: Create pairs and find maximum

return max(x + nums[-i - 1] for i, x in enumerate(nums[: len(nums) >> 1]))

This line does several things efficiently:

• nums[: len(nums) >> 1] takes the first half of the sorted array (the smaller elements). The >> 1 is a bitwise right shift, equivalent to dividing by 2.
• enumerate(nums[: len(nums) >> 1]) iterates through the first half with indices
• For each element x at index i in the first half, we pair it with nums[-i - 1] from the second half
  • When i = 0: we pair nums[0] with nums[-1] (first with last)
  • When i = 1: we pair nums[1] with nums[-2] (second with second-to-last)
  • And so on...
• x + nums[-i - 1] calculates each pair sum
• max(...) finds the maximum among all these pair sums

Time Complexity: O(n log n) due to sorting, where n is the length of the array. The pairing operation itself is O(n/2) which simplifies to O(n).

Space Complexity: O(1) if we don't count the space used by the sorting algorithm (which might use O(log n) for the recursion stack in some implementations).

The algorithm leverages the two-pointer pattern conceptually - we're effectively using pointers from both ends of the sorted array moving toward the center, though the implementation uses indexing rather than explicit pointers.

Example Walkthrough

Let's walk through the solution with the array nums = [3, 5, 2, 3].

Step 1: Sort the array After sorting: nums = [2, 3, 3, 5]

Step 2: Create pairs from opposite ends

We'll pair elements from the first half with elements from the second half:

• First half: [2, 3] (indices 0, 1)
• Second half: [3, 5] (indices 2, 3)

Now let's trace through the pairing process:

When i = 0:

• We take x = nums[0] = 2
• We pair it with nums[-0-1] = nums[-1] = 5
• Pair sum: 2 + 5 = 7

When i = 1:

• We take x = nums[1] = 3
• We pair it with nums[-1-1] = nums[-2] = 3
• Pair sum: 3 + 3 = 6

So our pairs are:

• (2, 5) with sum = 7
• (3, 3) with sum = 6

Step 3: Find the maximum pair sum Maximum of [7, 6] = 7

The algorithm returns 7 as the minimized maximum pair sum.

Why is this optimal? Let's verify by checking other possible pairings:

• If we paired (2, 3) and (3, 5): sums would be 5 and 8, max = 8 (worse)
• If we paired (2, 3) and (3, 5): sums would be 5 and 8, max = 8 (worse)

By pairing smallest with largest, we avoid creating the worst-case sum of 3 + 5 = 8, and instead balance the pairs to minimize the maximum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation nums.sort(), which takes O(n × log n) time where n is the length of the array. After sorting, the code iterates through half of the array (nums[:len(nums) >> 1]) to calculate pair sums, which takes O(n/2) = O(n) time. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's built-in sort() method uses Timsort, which has a worst-case space complexity of O(n) but typically uses O(log n) space for the recursion stack in practice. The generator expression max(x + nums[-i - 1] for i, x in enumerate(nums[:len(nums) >> 1])) computes values on-the-fly without storing them all at once, so it only uses O(1) additional space. Therefore, the overall space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Sort the Array

One of the most common mistakes is attempting to pair elements without first sorting the array. The greedy strategy only works when we can systematically pair smallest with largest elements.

Incorrect approach:

def minPairSum(self, nums: List[int]) -> int:
    n = len(nums)
    max_sum = 0
    # Wrong: trying to pair without sorting
    for i in range(n // 2):
        max_sum = max(max_sum, nums[i] + nums[n - 1 - i])
    return max_sum

Why it fails: Without sorting, you're pairing arbitrary elements that happen to be at opposite positions in the original array, which doesn't minimize the maximum pair sum.

2. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, calculating pair sums might cause integer overflow for large values.

Solution for languages with fixed integer sizes:

// C++ example with overflow protection
int minPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    long long maxSum = 0;  // Use long long to prevent overflow
    int n = nums.size();
    for (int i = 0; i < n / 2; i++) {
        maxSum = max(maxSum, (long long)nums[i] + nums[n - 1 - i]);
    }
    return maxSum;
}

3. Off-by-One Errors in Pairing

When pairing elements from opposite ends, it's easy to make indexing mistakes.

Common mistake:

# Wrong: incorrect pairing index
for i in range(n // 2):
    current_sum = nums[i] + nums[n - i]  # Should be nums[n - 1 - i]

This would cause an index out of bounds error since nums[n] doesn't exist (arrays are 0-indexed).

4. Modifying the Input Array

The solution sorts the input array in-place, which modifies it. If the original array order needs to be preserved for other operations, this could cause issues.

Solution if original order must be preserved:

def minPairSum(self, nums: List[int]) -> int:
    # Create a copy to avoid modifying the original
    sorted_nums = sorted(nums)  # Creates a new sorted list
    n = len(sorted_nums)
    max_pair_sum = 0
  
    for i in range(n // 2):
        current_pair_sum = sorted_nums[i] + sorted_nums[n - 1 - i]
        max_pair_sum = max(max_pair_sum, current_pair_sum)
  
    return max_pair_sum

5. Assuming Odd-Length Arrays

The problem specifies even-length arrays, but if you accidentally test with odd-length arrays or don't validate input, the algorithm will miss one element.

Defensive programming approach:

def minPairSum(self, nums: List[int]) -> int:
    n = len(nums)
    if n % 2 != 0:
        raise ValueError("Array length must be even")
  
    nums.sort()
    max_pair_sum = 0
  
    for i in range(n // 2):
        current_pair_sum = nums[i] + nums[n - 1 - i]
        max_pair_sum = max(max_pair_sum, current_pair_sum)
  
    return max_pair_sum