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.
(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:
nums is in exactly one pair, andReturn 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.
Constraints:
n == nums.length2 <= n <= 105n is even.1 <= nums[i] <= 105Problem 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.
Sort the array first. Then, use a two-pointer technique to pick the smallest and largest elements to form pairs. Start with the smallest, pair it with the largest, and move inwards. This minimizes the largest sum in each pair.
The solution sorts the array using the C standard library function qsort(). It then iteratively forms pairs of elements from the two ends (smallest and largest), computes the pair sum, and tracks the maximum pair sum encountered.
The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) as we don't use any additional data structures.
Use the sorted array but pair elements directly based on their index positions in a staggered manner. This approach takes advantage of the sorted order to pair elements directly based on their index positions.
This solution leverages the sorted nature of the list to directly pair numbers in the staggered pattern (index-based).
The time complexity remains O(n log n) due to sorting, and the space complexity is O(1).
To minimize the maximum pair sum in the array, we can pair the smallest number with the largest number, the second smallest with the second largest, and so on.
Therefore, we can first sort the array, then use two pointers to point to the two ends of the array. Calculate the sum of the numbers pointed to by the two pointers, update the maximum pair sum, then move the left pointer one step to the right and the right pointer one step to the left. Continue this process until the two pointers meet, and we will get the minimum maximum pair sum.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Sorting and Two-Pointer Approach | The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) as we don't use any additional data structures. |
| Direct Index Pairing Strategy | The time complexity remains O(n log n) due to sorting, and the space complexity is O(1). |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O((n-1)!!) | O(n) | Conceptual understanding or very small input sizes |
| Sorting + Two-Pointer Greedy | O(n log n) | O(1) | Standard optimal approach for unsorted arrays |
| Direct Index Pairing After Sort | O(n log n) | O(1) | Cleaner implementation once the array is sorted |
Minimize Maximum Pair Sum in Array | Intuition | Similar Problems | Leetcode 1877 | codestorywithMIK • codestorywithMIK • 14,302 views views
Watch 9 more video solutions →Practice Minimize Maximum Pair Sum in Array with our built-in code editor and test cases.
Practice on FleetCode