561. 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.

Example 1:

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).

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

Problem Summary #

Given an array of length 2n, your task is to divide these numbers into n pairs, such as (a1, b1), (a2, b2), …, (an, bn), so that the sum of min(ai, bi) from 1 to n is maximized.

Solution Ideas #

• Given an array of 2n numbers, divide them into n groups of one pair each, and find the maximum possible sum of the minimum values of each group.
• Since the data range given by the problem is not large, [-10000, 10000], we can consider using a hash table array, which stores the frequency of the element i - 10000, with an offset of 10000. This hash table can access the array in increasing order, which can reduce the time spent on sorting. The problem asks for the maximum value of the sum after grouping, so all smaller elements should be arranged in the same groups as much as possible. After taking min, this has little impact on the maximum sum. For example, arranging (1, 1) together gives 1 after taking min. But if two elements with a large difference are arranged together, the larger element is “sacrificed”. For example, (1, 10000) gives 1 after taking min, so 10000 is “sacrificed”. Therefore, smaller values need to be considered first.
• The frequency of smaller values may be odd or even. If it is even, it is relatively simple: just arrange them in pairs. If it is odd, then one of them will be left alone once, and the remaining one needs to be paired with the nearest element to it, which minimizes the impact on the final sum. If the count of a smaller value is odd, it will affect the choice of later elements. If a later element has an even count, since one element needs to be paired with the previous smaller value, the remaining count becomes odd again. This impact will be passed on to the following elements in sequence. Therefore, use a flag to mark this: if there is a remaining element in the current set that will be considered again, this flag is set to 1. When selecting elements from the next group, the same extra element already considered will be taken into account.
• Finally, just dynamically maintain the sum value during the scan.

Code #

package leetcode

func arrayPairSum(nums []int) int {
	array := [20001]int{}
	for i := 0; i < len(nums); i++ {
		array[nums[i]+10000]++
	}
	flag, sum := true, 0
	for i := 0; i < len(array); i++ {
		for array[i] > 0 {
			if flag {
				sum = sum + i - 10000
			}
			flag = !flag
			array[i]--
		}
	}
	return sum
}