Minimize Maximum Pair Sum in Array LeetCode Solution

Difficulty Level Medium
Frequently asked in eBay GoogleViews 3671

Problem Statement

Minimize Maximum Pair Sum in Array LeetCode Solution says 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 (2,6), (1,3), and (5,4), the maximum pair sum would be max(2+6, 1+3, 5+4) = max(8, 4. 9) = 9 .

Given array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Return the minimized maximum pair sum after optimally pairing up the elements.

Example:

Test Case 1:

Input:

nums = [3,5,2,4,6,8]

Output:

10

Test Case 2:

Input:

nums = [1,5,3,4,6,7]

Output:

9

Explanation:

i) For the first test case, we can have pairs such as (2,8), (3,6), and (4,5). The sums of these pairs are 10, 9, and 9. Max sum is 10.

ii) For the second test case, we can have pairs such as (1,7), (3,6), and (4,5). The sums of these pairs are 8, 9, and 9. Max sum is 9.

Approach

Idea:

Here we need to minimize the maximum pair sum. So the basic idea is we can pair the numbers such as (the 1st largest and the 1st smallest), (the 2nd largest and the 2nd smallest), and so on. This way we can minimize the sum. We might feel that if we will pair (2nd largest and 1st smallest), it will minimize the sum. But this way we will have to pair (1st largest) with another number that will be larger than the 1st smallest number, which will increase the maximum sum. We can 2 pointers, left pointer and right pointer. Each time we will increase the left pointer and decrease the right pointer and check for maximum value.

Code

Java Program for Minimize Maximum Pair Sum in Array LeetCode Solution

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int left = 0, right = nums.length-1;
        int maxSum = 0;
        while(left<right) {
          maxSum = maxSum>(nums[left++]+nums[right--])?maxSum:(nums[left-1]+nums[right+1]);
        }
        return maxSum;
    }
}

C++ Program for Minimize Maximum Pair Sum in Array LeetCode Solution

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        int left = 0, right = nums.size()-1;
        int maxSum = 0;
        while(left<right) {
          maxSum = maxSum>(nums[left++]+nums[right--])?maxSum:(nums[left-1]+nums[right+1]);
        }
        return maxSum;
    }
};

Complexity Analysis for Minimize Maximum Pair Sum in Array LeetCode Solution

Time Complexity

Here we are iterating the array using two pointers technique. So for that, it will take O(n/2) ≡ O(n) time. But before that, we are sorting the array. It takes O(nlogn) time. It dominates the time complexity. So overall time complexity will be O(nlogn).

Space Complexity

Here we are not using any extra space. So space complexity is O(1).

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique

Translate »