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.
(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:
nums is in exactly one pair, andReturn 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.
Constraints:
n == nums.length2 <= n <= 105n is even.1 <= nums[i] <= 105Sort the array first. Then, use a two-pointer technique to pick the smallest and largest elements to form pairs. Start with the smallest, pair it with the largest, and move inwards. This minimizes the largest sum in each pair.
The solution sorts the array using the C standard library function qsort(). It then iteratively forms pairs of elements from the two ends (smallest and largest), computes the pair sum, and tracks the maximum pair sum encountered.
C++
Java
Python
C#
JavaScript
The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) as we don't use any additional data structures.
Use the sorted array but pair elements directly based on their index positions in a staggered manner. This approach takes advantage of the sorted order to pair elements directly based on their index positions.
This solution leverages the sorted nature of the list to directly pair numbers in the staggered pattern (index-based).
C++
Java
Python
C#
JavaScript
The time complexity remains O(n log n) due to sorting, and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sorting and Two-Pointer Approach | The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) as we don't use any additional data structures. |
| Direct Index Pairing Strategy | The time complexity remains O(n log n) due to sorting, and the space complexity is O(1). |
Minimize Maximum of Array - Leetcode 2439 - Python • NeetCodeIO • 25,249 views views
Watch 9 more video solutions →Practice Minimize Maximum Pair Sum in Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor