Leetcode 1877: Minimize Maximum Pair Sum in Array
Given an array
nums of even length n, your task is to pair up the elements of the array into n / 2 pairs such that the maximum pair sum is minimized. A pair sum is defined as the sum of two elements in a pair. The goal is to minimize the largest of these pair sums.Problem
Approach
Steps
Complexity
Input: You are given an array `nums` consisting of `n` integers.
Example: For nums = [1, 9, 2, 8].
Constraints:
• 2 <= n <= 10^5
• n is even.
• 1 <= nums[i] <= 10^5
Output: Return the minimized maximum pair sum after optimally pairing up the elements.
Example: For nums = [1, 9, 2, 8], the output is 9.
Constraints:
• The output should be an integer representing the minimized maximum pair sum.
Goal: To minimize the maximum pair sum, the array should be sorted, and pairs should be formed from the smallest and largest elements.
Steps:
• Sort the array in non-decreasing order.
• Pair the smallest element with the largest element, the second smallest with the second largest, and so on.
• Compute the sum of each pair, and track the maximum sum.
• Return the maximum pair sum.
Goal: Ensure the array is of even length, with each element in the array being a positive integer.
Steps:
• 2 <= nums.length <= 10^5
• nums consists of integers in the range [1, 10^5].
Assumptions:
• The array contains at least two elements.
• The array length is even, and pairing is always possible.
• Input: For nums = [1, 9, 2, 8].
• Explanation: The sorted array is [1, 2, 8, 9]. The optimal pairings are (1, 9) and (2, 8), resulting in pair sums of 10 and 10. The minimized maximum pair sum is 9.
• Input: For nums = [3, 4, 6, 7, 2, 5].
• Explanation: The sorted array is [2, 3, 4, 5, 6, 7]. The optimal pairings are (2, 7), (3, 6), and (4, 5), resulting in pair sums of 9, 9, and 8. The minimized maximum pair sum is 8.
Approach: To solve this problem, we first sort the array in ascending order and then pair the smallest elements with the largest ones. This minimizes the maximum sum of any pair.
Observations:
• Sorting the array ensures that pairing the smallest and largest elements minimizes the maximum sum.
• By pairing extreme values, we balance the sums to reduce the largest possible pair sum.
Steps:
• Sort the array in ascending order.
• Pair the first element with the last element, the second element with the second-to-last, and continue until all elements are paired.
• For each pair, compute the sum and track the maximum sum.
• Return the maximum sum after pairing.
Empty Inputs:
• Not applicable, as the input array is guaranteed to have an even length and at least two elements.
Large Inputs:
• The algorithm should efficiently handle arrays with up to 100,000 elements.
Special Values:
• Arrays where all elements are the same value.
Constraints:
• Ensure the array length is even.
int minPairSum(vector<int>& A) {
sort(A.begin(), A.end());
int res = 0, n = A.size();
for (int i = 0; i < n / 2; ++i)
res = max(res, A[i] + A[n - i - 1]);
return res;
}
1 : Function Definition
int minPairSum(vector<int>& A) {
Define a function to compute the minimum possible maximum pair sum of an array.
2 : Sort
sort(A.begin(), A.end());
Sort the array to enable pairing of smallest and largest elements.
3 : Initialization
int res = 0, n = A.size();
Initialize the result variable and store the size of the array.
4 : Loop
for (int i = 0; i < n / 2; ++i)
Iterate through the first half of the array to form pairs with elements from the end.
5 : Update Result
res = max(res, A[i] + A[n - i - 1]);
Calculate the pair sum and update the result with the maximum pair sum encountered so far.
6 : Return
return res;
Return the minimum possible value of the maximum pair sum.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is O(n log n) due to the sorting step.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) for storing the sorted array, or O(1) if sorting in place.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus