Python Algorithm Q10

Q10 Array Partition I

---

Q

Given an integer 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.

Notice that the solution set must not contain duplicate triplets.

Sample Input

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:

1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
   So the maximum possible sum is 4.

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Constraints

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

1. My Solution == Given Solution #1

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort() #sort it first
        ans = 0
        for i in range(0,len(nums),2):
            ans += nums[i]
        return ans

#for testing
a = Solution()
nums = [6,2,6,5,1,2]
print(a.arrayPairSum(nums))

2. Given Solution #2

def arrayPairSum(self, nums: List[int]) -> int:
    return sum(sorted(nums)[::2])

Notice that this is not that tough problem. At first, you may feel confused and then be overwhelmed by the description of the problem. But you will soon notice that just sorting the array and then merging every even idx number give the solution.

What is more important is the #2 solution, “the most pythonic answer” according to the book. As I already mentioned, just picking every even idx number is the answer. So made it just in a sentence.

1. sorted() : to sort the list
2. [::2] : return every two intervals(=all even idx number)
3. sum() : literally

Overall Review

Easy question. Just not be frightened by the description.