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

Idea – 1

The maximum element will not contribute towards the sum. The best pairing with the max elements will be with the second max. Once this pair is determined, we keep doing the same for the array of size n-2. We sort. Time complexity O(n\cdot \lg{n}) and space complexity O(1). 
[code lang="java"]
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i += 2)
        {
            sum += nums[i];
        }
        
        return sum;
    }
}
[code]

Runtime: 14 ms, faster than 92.53% of Java online submissions for Array Partition I.Memory Usage: 39.3 MB, less than 99.91% of Java online submissions for Array Partition I.

Leave a comment