Description

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.

Example 1:

1Input: nums = [1,4,3,2]
2Output: 4
3Explanation: All possible pairings (ignoring the ordering of elements) are:
41. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
52. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
63. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
7So the maximum possible sum is 4.

Example 2:

1Input: nums = [6,2,6,5,1,2]
2Output: 9
3Explanation: 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

Solution

From the first look the problem looks difficult one where we are asked to find groups but if we apply some thinking to it, the difference between two numbers in the group will be minimum if those are two consecutive numbers. That means we will get best possible minimum sum with this case. In this case, differences could be reduced if we group two numbers in a sorted array.

 1class Solution {
 2    public int arrayPairSum(int[] nums) {
 3        // Sort the array
 4        Arrays.sort(nums);
 5        int sum = 0;
 6        for (int i = 0; i < nums.length; i+= 2) {
 7            sum += nums[i]; // this will be the minimum of the pair as the array is sorted
 8        }
 9        return sum;
10    }
11}