Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1877.html

1877. Minimize Maximum Pair Sum in Array

Level

Medium

Description

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

Solution

Sort the array nums and use two pointers from the two ends of the array to generate all pairs. Loop over all pairs and calculate the maximum pair sum. In this case, the maximum pair sum is minimized.

• Java
• C++
• Python
• Go
• TypeScript
• C#

• class Solution {
      public int minPairSum(int[] nums) {
          Arrays.sort(nums);
          int maxSum = 0;
          int left = 0, right = nums.length - 1;
          while (left < right) {
              int sum = nums[left] + nums[right];
              maxSum = Math.max(maxSum, sum);
              left++;
              right--;
          }
          return maxSum;
      }
  }
  
  ############
  
  class Solution {
      public int minPairSum(int[] nums) {
          Arrays.sort(nums);
          int res = 0, n = nums.length;
          for (int i = 0; i < (n >> 1); ++i) {
              res = Math.max(res, nums[i] + nums[n - i - 1]);
          }
          return res;
      }
  }
  

• // OJ: https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      int minPairSum(vector<int>& A) {
          sort(begin(A), end(A));
          int ans = 0;
          for (int i = 0; i < A.size() / 2; ++i) {
              ans = max(ans, A[i] + A[A.size() - 1 - i]);
          }
          return ans;
      }
  };
  

• class Solution:
      def minPairSum(self, nums: List[int]) -> int:
          nums.sort()
          res, n = 0, len(nums)
          for i in range(n >> 1):
              res = max(res, nums[i] + nums[n - i - 1])
          return res
  
  ############
  
  # 1877. Minimize Maximum Pair Sum in Array
  # https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/
  
  class Solution:
      def minPairSum(self, nums: List[int]) -> int:
          n = len(nums)
          nums.sort()
          res = []
          
          for i in range(n // 2):
              res.append(nums[i] + nums[n - i - 1])
          
          return max(res)
  
  

• func minPairSum(nums []int) int {
  	sort.Ints(nums)
  	res, n := 0, len(nums)
  	for i := 0; i < (n >> 1); i++ {
  		res = max(res, nums[i]+nums[n-i-1])
  	}
  	return res
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

• function minPairSum(nums: number[]): number {
      nums.sort((a, b) => a - b);
      let ans = 0;
      const n = nums.length;
      for (let i = 0; i < n >> 1; ++i) {
          ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
      }
      return ans;
  }
  
  

• public class Solution {
      public int MinPairSum(int[] nums) {
          Array.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;
      }
  }
  
  

All Problems

All Solutions