LeetCode - Minimize Maximum Pair Sum in Array
Problem statement
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, andThe maximum pair sum is minimized.
Return the minimized maximum pair sum after optimally pairing up the elements.
Problem statement taken from: https://leetcode.com/problems/minimize-maximum-pair-sum-in-array
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
Explanation
Sorting
We sort the array first and then iterate over the loop to form pairs (i, j). i will start from index 0, and j will begin from the last index.
We increment and decrement i and j, respectively, to form the next pairs till i < j.
Let's check the algorithm first.
- sort(nums.begin(), nums.end())
maxSum = 0
i = 0
j = nums.size() - 1
- loop while i < j
- if nums[i] + nums[j] > maxSum
- maxSum = nums[i] + nums[j]
- i++
j--
- while end
- return maxSum
The time complexity of the above approach is O(n * log(n)), and the space complexity is O(1).
Let's check our algorithm in C++, Golang, and JavaScript.
C++ solution
class Solution {
public:
int minPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int maxSum = 0, i = 0, j = nums.size() - 1;
while(i < j) {
if(nums[i] + nums[j] > maxSum) {
maxSum = nums[i] + nums[j];
}
i++;
j--;
}
return maxSum;
}
};
Golang solution
func minPairSum(nums []int) int {
sort.Ints(nums)
i, j := 0, len(nums) - 1
maxSum := 0
for i < j {
if nums[i] + nums[j] > maxSum {
maxSum = nums[i] + nums[j]
}
i++
j--
}
return maxSum
}
JavaScript solution
var minPairSum = function(nums) {
nums.sort((a, b) => a - b);
let i = 0, j = nums.length - 1;
let maxSum = 0;
while(i < j) {
maxSum = Math.max(nums[i] + nums[j], maxSum);
i++;
j--;
}
return maxSum;
};
Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: nums = [3, 5, 5, 2, 4, 6]
Step 1: sort(nums.begin(), nums.end())
nums = [2, 3, 4, 5, 5, 6]
maxSum = 0
i = 0
j = nums.size() - 1
= 6 - 1
= 5
Step 2: loop while i < j
0 < 5
true
if nums[i] + nums[j] > maxSum
nums[0] + nums[5] > 0
2 + 6 > 0
8 > 0
true
maxSum = nums[i] + nums[j]
= nums[0] + nums[5]
= 2 + 6
= 8
i++
i = 1
j--
j = 4
Step 3: loop while i < j
1 < 4
true
if nums[i] + nums[j] > maxSum
nums[1] + nums[4] > 8
3 + 5 > 8
8 > 8
false
i++
i = 2
j--
j = 3
Step 4: loop while i < j
2 < 3
true
if nums[i] + nums[j] > maxSum
nums[2] + nums[3] > 8
4 + 5 > 8
9 > 8
true
maxSum = nums[i] + nums[j]
= nums[2] + nums[3]
= 4 + 5
= 9
i++
i = 3
j--
j = 2
Step 5: loop while i < j
3 < 2
false
Step 6: return maxSum
We return the answer as 9.