Leetcode 0561 Array Partition I

Problem statement

https://leetcode.com/problems/array-partition-i/

Solution

It happens that we can just sort numbers and choose every odd number. How we can prove that choosing odd will give the best result? We can show that $S_m = (S - S_d)/2$, where $S_m$ is our sum to maximize and $S_d$ is sum of absolute values between numbers in pairs. So, we need to minimize $S_d$, and we can show our example is optimal.

Complexity

Time complexity is O(n log n), space complexity is O(n) if we are not allowed to change data and O(log n) in opposite case.

Code

class Solution:
    def arrayPairSum(self, nums):
        return sum(sorted(nums)[::2])