CODEWITHSUNDEEP
arraysmath
Joanne Lee
Joanne Lee

Reputation: 45

Array Partition I (How to prove this in math)

This is a question from leetcode.

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.

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.

I resolved this by trying multiple examples and found out if I sorted and arranged the pair like 1 2 | 3 4, the min value of each pair is what I want. Since the array is sorted, the positions of min values are fixed; hence I can get the value by index + 2. Although it works, it's more like a guss. Does anyone know how to prove this in mathematics to make the logic more rigourously?

def arrayPairSum(nums: List[int]) -> int:
    nums_sort = sorted(nums)
    res = 0
    i = 0
    while i < len(nums):
        res += nums_sort[i]
        i += 2
    return res

Upvotes: 1

Views: 1638

Answers (1)

Mad Physicist
Mad Physicist

Reputation: 114548

You can use induction. Let's say you have a sorted array a. The smallest number, a[0] will always be the smallest of whatever pair it occurs in. The maximum sum will occur if you select its partner to be a[1], the next smallest number. You can show this by selecting some other number a[m] to be its partner. In that case, at least one of the other pairs will have minimum a[1], which is by definition less than it would otherwise have. You can proceed to apply the same argument to the remaining elements a[2:].

Alternatively, you can start from the other end. a[-1] is guaranteed to never figure in the sum because it is the maximum of whatever pair it will occur in. If you pair it with anything other than a[-2], the total sum will not be maximized: some smaller a[m] will represent the pair containing a[-1] in the sum, while a[-2] will be larger than any a[n] it is paired with, and therefore will not appear in the sum.

Both arguments yield the same result: the maximum sum is over the even indices of the sorted array.

As mentioned in the comments, the following two implementations will be more efficient than a raw for loop:

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

OR

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

The latter does the sorting in-place, and is probably faster if allowed.

Upvotes: 1

Related Questions