1877. Minimize Maximum Pair Sum in Array → Leetcode (Google Interview)

Below is question

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.

Intuitive Solution

What we can see is we have to create pairs of two numbers from an array such that when we add them and find the maximum sum pair it should be the minimum of all possible pairs. If we add smallest number to largest one then we can achieve these minimized pairs and then we can find which one is largest out of these.

[3,5,4,2,4,6]
Sorted array for this would be
[2,3,4,4,5,6]
Now we can create pair taking one element from start and another from end and select which one is maximum. Out of minimum we have to find maximum.
[{2+6},{3,5},{4+4}]

below is code for same in Java

public int minPairSum(int[] nums) {

Arrays.sort(nums);
int result = Integer.MIN_VALUE;

for(int i = 0 ; i < nums.length/2;i++){
result = Math.max(nums[i]+nums[nums.length-1 -i],result);
}
return result;
}

Result from leetcode for same

Software engineer, Leading highly scalable product @scale of million records per day.