Burak Dede's Blog

Array Partition Problem - Leetcode

Problem

This is my approach to the solution of array partition problem from Leetcode. https://leetcode.com/problems/array-partition-i/description/

Description of the problem is hard to understand in the first read but basically it says that there are 2n elements array and you need n number of pairs which each pair must participate in the sum with its minimum element to make sum max. First thing comes to my mind is to sort the array so that I can easily partition them and iterate once to add smallest element from each pair which is the first element in each.

basic demonstration of algorithm

[1, 4, 3, 2]
[1, 2, 3, 4]
(1,2) - (3,4)
min(1,2) + min(3,4) = 4

here is the solution.

public int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int sum = 0;
    for(int i = 0; i < nums.length; i += 2) {
        sum += nums[i];
    }

    return sum;
}

Even though we pass once over the array time complexity is still O(nlogn) because of sorting and space is constant in this case.