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
numsis 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;
};
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.
Top comments (0)