Array Partition

Problem 🤔

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Code

def quickSort(self,nums, low, high):
    if low < high:
        part = self.partition(nums, low,high)
        self.quickSort(nums,low,part-1)
        self.quickSort(nums,part+1,high)

def partition(self, nums, low, high):
    i = (low - 1)
    pivot = nums[high]
    for j in range(low, high):
        if nums[j] <= pivot:
            i += 1
            nums[i],nums[j] = nums[j],nums[i]
    nums[i+1],nums[high] = nums[high],nums[i+1]
    return(i+1)

def arrayPairSum(self, nums):
    temp = 0
    self.quickSort(nums,0,len(nums)-1)
    for index in range(0,len(nums)-1,2):
        temp += min(nums[index],nums[index+1])
    return temp

Developer’s Notes 👨‍💻

For this I ordered the list using a quicksort, then I cycled through the array took the pairs of numbers and summed the mins. I ordered the array since it would give the largest possible minimum for each pair.