561. Array Partition I

The problem requires us to maximize the sum of pair-wise minimums

Approach 1: Brute Force

The ugliest solution to the problem is by brute-forcing each and every combination for all the values of the array. This will involve generating all permutations of the given array and then splitting them pairwise and returning the corresponding minimum

Time Complexity: O(n!) (There can be a total of n! permutations)

Space Complexity: O(1) (Since we do not need to store all the permutations)

Given that the size of the array could be up to 20000, this solution was bound to fail and giving it a try would be a waste of time.

Approach 2: Sorting

The easier and faster solution to the problem is by first sorting the given array in ascending order, then grouping the numbers into pairs in sequential order and summing up the minimum of all the pairs (i.e. sum up every alternate number since the array is already sorted in ascending order)

array-partition-i

def arrayPairSum(self, nums):     
    """     
    https://leetcode.com/problems/array-partition-i/description/
    :type nums: List[int]     
    :rtype: int     
    """     
    nums.sort()    
    sum = 0
    for i in range(0,len(nums),2):
        sum += nums[i]
        return sum

Time complexity: O(nlog(n)) (Sorting takes O(nlog(n)) time)

Space complexity: O(1) (Sorting is done in place so no extra memory is needed)

Some minor code improvements would be to replace the for loop with a list comprehension sum instead i.e. return sum(nums[::2]) which does not change the logic but makes it more concise