Left And Right Sum Differences - Leetcode Solution

Problem:

Given an array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Constraints:

• 1 <= n <= 10^4
• nums.length == 2n
• -10^4 <= nums[i] <= 10^4

Solution:

To solve this problem, we need to understand that the maximum sum will be achieved when we pair the smallest numbers with the second smallest numbers, and so on. This is because choosing the smallest number will give us the biggest choice to pair the remaining numbers.

Let's sort the array in ascending order first. Then, we can pair the numbers at positions 0 and 1, 2 and 3, and so on. The minimum number of each pair will be added to the sum. This will give us the maximum possible sum.

Below is the code implementation for the same:

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

Complexity Analysis:

• Time Complexity: O(n log n) as we are sorting the input array.
• Space Complexity: O(1) as we are not using any extra space other than the input list.

1