Scale Engineer

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
Two PointersGreedy
Algorithms
Sorting
Data structures
Array
Companies
eBay

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 <= 105
  • n is even.
  • 1 <= nums[i] <= 105

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

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

import java.util.Arrays; class Solution {    public int minPairSum(int[] nums) {        // Step 1: Sort the array        Arrays.sort(nums);                int maxSum = 0;        // Step 3: Initialize two pointers        int left = 0;        int right = nums.length - 1;                // Step 4-7: Iterate and find pair sums        while (left < right) {            int currentSum = nums[left] + nums[right];            maxSum = Math.max(maxSum, currentSum);            left++;            right--;        }                // Step 8: Return the result        return maxSum;    }}

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.

Solutions

class Solution {public  int minPairSum(int[] nums) {    Arrays.sort(nums);    int ans = 0, n = nums.length;    for (int i = 0; i < n >> 1; ++i) {      ans = Math.max(ans, nums[i] + nums[n - i - 1]);    }    return ans;  }}

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 →

Next problem