Array Partition I

Problem Source: LeetCode
Companies: Adobe

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:

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

Solution:

Explanation of the problem may not be easy for many. Thus, we will try to understand the problem in a simple manner.

The given input array contains 2n integers (means it will always have even number of elements) and we need to form the pairings of the array’s elements such that the overall sum of the minimum out of such pairings is maximum. So if we choose (a,b) pairing we have to take care that to get maximum sum the differnce of a and b is minimized.

One solution to this problem is sorting. If we sort the whole array first and make pairs of adjacent elements, the difference between the pairs is minimized. Hence we will get maximum sum.

Implementation

Java

public static class Solution1 {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int total = 0;
        for (int i = 0; i < nums.length; i += 2) {
            total += nums[i];
        }
        return total;
    }
}

Complexity Analysis:

• Time Complexity: O(nlogn). Sorting will take O(nlogn) complexity.
• Space Complexity: O(1).