Minimize maximum pair sum in array
November 26, 2022
greedyProblem URL: Minimize maximum pair sum in array
We will sort the array. We will iterate over the array from the beginning and the end. We will add the first element and the last element to the result. We will return the result.
class Solution:
def minPairSum(self, nums: List[int]) -> int:
nums.sort()
res = 0
for i in range(len(nums)//2):
res = max(res, nums[i]+nums[-i-1])
return res
Time complexity: O(nlog(n))
, n is the length of nums
Space complexity: O(1)
We can also solve it using python built-in functions:
class Solution:
def minPairSum(self, nums: List[int]) -> int:
nums.sort()
return max(a+b for a, b in zip(nums, reversed(nums)))
Time complexity: O(nlog(n))
, n is the length of nums
Space complexity: O(n)