We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize Maximum Pair Sum in Array

Number: 1988

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, eBay

Problem Description

Given an even-length array nums, pair up its elements such that each element is used in exactly one pair and the maximum pair sum (i.e. the largest sum of any pair) is minimized. The problem asks to return this minimized maximum pair sum.

Key Insights

  • Sorting the array allows for pairing the smallest element with the largest element.
  • Pairing the lowest with the highest balances the pair sums, thereby minimizing the maximum sum.
  • A two-pointer approach (one pointer at the start and one at the end) efficiently forms the optimal pairs.
  • This greedy technique ensures each pair's sum is as balanced as possible.

Space and Time Complexity

Time Complexity: O(n log n) – due to the sorting step.
Space Complexity: O(1) if sorted in place (or O(n) if extra space is used).

Solution

The algorithm starts by sorting the array. Then, it pairs the smallest element with the largest element, the second smallest with the second largest, and so on. This minimizes the possibility of any one pair having an excessively high sum, as each large element is counterbalanced by a small element. A simple iteration over the first half of the sorted array using two pointers gives the maximum pair sum among these optimal pairs, which is then returned as the result.

Code Solutions

def minPairSum(nums):
    # Sort the array in ascending order.
    nums.sort()
    
    max_pair_sum = 0
    n = len(nums)
    
    # Pair the smallest number with the largest, second smallest with second largest, etc.
    for i in range(n // 2):
        pair_sum = nums[i] + nums[n - 1 - i]
        # Update the maximum pair sum observed.
        max_pair_sum = max(max_pair_sum, pair_sum)
        
    return max_pair_sum

# Example usage:
print(minPairSum([3, 5, 2, 3]))  # Output should be 7
← Back to All Questions