Minimize Maximum Pair Sum in Array

Med

#1713Time: O(N log N). The dominant part of this algorithm is sorting the array, which typically takes `O(N log N)` time. The subsequent two-pointer scan to find the pair sums takes linear time, `O(N)`, which is overshadowed by the sorting time.Space: O(log N) to O(N). The space complexity is determined by the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which requires `O(log N)` space on average for the recursion stack, but can take up to `O(N)` in the worst case.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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.

For example, if we have 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:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.

Return 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.length
2 <= n <= 10⁵
n is even.
1 <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the intuition that to minimize the maximum pair sum, we should balance the pairs by pairing the smallest elements with the largest ones. Sorting the array allows us to easily identify these elements.

Algorithm

Sort the input array nums in non-decreasing order.
Initialize a variable maxSum to store the maximum pair sum, setting it to 0 initially.
Initialize two pointers: left at the beginning of the array (index 0) and right at the end of the array (index n-1).
Iterate with a while loop as long as left is less than right.
Inside the loop, calculate the sum of the elements pointed to by left and right: currentSum = nums[left] + nums[right].
Update maxSum to be the maximum of its current value and currentSum.
Move the pointers closer to the center: increment left and decrement right.
After the loop finishes, return maxSum.

Walkthrough

The core idea is that the optimal pairing strategy involves matching the smallest numbers with the largest numbers. To achieve this, we first sort the array nums in non-decreasing order. After sorting, the smallest element is at nums[0] and the largest is at nums[n-1]. The second smallest is at nums[1] and the second largest is at nums[n-2], and so forth. We can then use a two-pointer technique. One pointer, left, starts at the beginning of the sorted array, and another pointer, right, starts at the end. We form a pair with the elements at these pointers, calculate their sum, and update our running maximum sum. Then, we move both pointers inwards (left++, right--) to consider the next pair of smallest and largest available elements. This process continues until the pointers meet or cross, ensuring all elements are paired up. The final result is the minimized maximum pair sum.

1import java.util.Arrays;2 3class Solution {4    public int minPairSum(int[] nums) {5        // Step 1: Sort the array6        Arrays.sort(nums);7        8        int maxSum = 0;9        // Step 3: Initialize two pointers10        int left = 0;11        int right = nums.length - 1;12        13        // Step 4-7: Iterate and find pair sums14        while (left < right) {15            int currentSum = nums[left] + nums[right];16            maxSum = Math.max(maxSum, currentSum);17            left++;18            right--;19        }20        21        // Step 8: Return the result22        return maxSum;23    }24}

Complexity

Time

O(N log N). The dominant part of this algorithm is sorting the array, which typically takes `O(N log N)` time. The subsequent two-pointer scan to find the pair sums takes linear time, `O(N)`, which is overshadowed by the sorting time.

Space

O(log N) to O(N). The space complexity is determined by the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which requires `O(log N)` space on average for the recursion stack, but can take up to `O(N)` in the worst case.

Trade-offs

Pros

The logic is straightforward and easy to implement.
It's a general solution that works regardless of the range of values in the input array.

Cons

The time complexity of O(N log N) is not optimal for this problem, given the constraints on the input values.
The space complexity depends on the sorting algorithm's implementation and can be O(N) in the worst case.

This approach leverages the problem's constraint on the range of input values to achieve a linear time solution. By using a frequency array (similar to Counting Sort), we can efficiently find the smallest and largest available numbers to pair up without performing a full comparison-based sort.

Algorithm

Determine the maximum possible value K from the input constraints (e.g., 100000).
Create a frequency array counts of size K+1 to store the count of each number.
Iterate through the input array nums and populate the counts array. For each num in nums, increment counts[num].
Initialize maxSum = 0.
Initialize two pointers: low starting at 1 and high starting at K.
Loop while low <= high: a. If counts[low] is 0, it means the number low is not present or has been used up. Increment low and continue. b. If counts[high] is 0, decrement high and continue. c. If both counts[low] and counts[high] are greater than 0, we have found the current smallest and largest available numbers. d. Calculate their sum low + high and update maxSum = Math.max(maxSum, low + high). e. Decrement counts[low] and counts[high] to mark them as used.
Return maxSum.

Walkthrough

Instead of sorting the array, we can use a more direct method to find the smallest and largest available elements by taking advantage of the value constraints (1 <= nums[i] <= 10^5). We can create a frequency array, counts, to store how many times each number appears in the input nums. The size of this array will be based on the maximum possible value (100001).

After populating the counts array in a single pass over nums, we use two pointers, low and high, initialized to the start (1) and end (100000) of our value range. We move low forward until we find a number with a count greater than zero (the smallest available number). Similarly, we move high backward to find the largest available number. We then pair these two numbers, update our maximum sum, and decrement their counts in the frequency array. This process is repeated until all numbers are paired. This avoids the O(N log N) cost of sorting, leading to a more efficient O(N + K) solution, where K is the range of values.

1class Solution {2    public int minPairSum(int[] nums) {3        // The maximum value is constrained to 1000004        int maxVal = 100000;5        int[] counts = new int[maxVal + 1];6        7        // Populate the frequency array8        for (int num : nums) {9            counts[num]++;10        }11        12        int maxSum = 0;13        int low = 1;14        int high = maxVal;15        16        // Use two pointers on the frequency array17        while (low <= high) {18            // Find the smallest available number19            if (counts[low] == 0) {20                low++;21                continue;22            }23            // Find the largest available number24            if (counts[high] == 0) {25                high--;26                continue;27            }28            29            // Form a pair and update maxSum30            maxSum = Math.max(maxSum, low + high);31            32            // Decrement counts for the used numbers33            counts[low]--;34            counts[high]--;35        }36        37        return maxSum;38    }39}

Complexity

Time

O(N + K), where `N` is the length of `nums` and `K` is the range of values. Populating the `counts` array takes `O(N)`. The two-pointer scan on the `counts` array takes `O(K)` time because the `low` and `high` pointers each traverse the range of values at most once. Thus, the total time complexity is linear.

Space

O(K), where `K` is the maximum possible value in `nums`. We need an auxiliary array `counts` of size `K+1` to store the frequencies of the numbers. Given the constraint `nums[i] <= 10^5`, this is a fixed amount of extra space.

Trade-offs

Pros

Achieves linear time complexity, which is more efficient than the sorting-based approach for the given constraints.
The logic remains intuitive: pair the smallest with the largest.

Cons

This approach is only efficient when the range of values (K) is manageable. If K were very large, the space complexity would become a problem.
It is less general than the sorting approach as it relies on the values being non-negative integers within a specific range.

Solutions

Solution

1class Solution {2public3  int minPairSum(int[] nums) {4    Arrays.sort(nums);5    int ans = 0, n = nums.length;6    for (int i = 0; i < n >> 1; ++i) {7      ans = Math.max(ans, nums[i] + nums[n - i - 1]);8    }9    return ans;10  }11}

1/** * @param {number[]} nums * @return {number} */ var minPairSum = function (2  nums,3) {4  nums.sort((a, b) => a - b);5  let ans = 0;6  const n = nums.length;7  for (let i = 0; i < n >> 1; ++i) {8    ans = Math.max(ans, nums[i] + nums[n - 1 - i]);9  }10  return ans;11};

1public class Solution {2    public int MinPairSum(int[] nums) {3        Array.Sort(nums);4        int ans = 0, n = nums.Length;5        for (int i = 0; i < n >> 1; ++i) {6            ans = Math.Max(ans, nums[i] + nums[n - i - 1]);7        }8        return ans;9    }10}

1class Solution {2public:3  int minPairSum(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int ans = 0, n = nums.size();6    for (int i = 0; i < n >> 1; ++i) {7      ans = max(ans, nums[i] + nums[n - i - 1]);8    }9    return ans;10  }11};

1class Solution:2    def minPairSum(self, nums: List[int]) -> int: nums . sort() n = len(nums) return max(x + nums[n - i - 1] for i, x in enumerate(nums[: n >> 1]))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem