[LeetCode] Array Partition

Problem: 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:

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

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Approach: The catch here is to get the maximum sum possible. That means we need to get the maximum n values possible from the array but the problem here is we need to get the minimum value of the pair so what we can get is 2nd maximum, 4th maximum, 6th maximum and so on.

To get this efficiently, we can sort the array and then take nums[0], nums[2], nums[4] and so on. We just need to add these values and return it.

Implementation in C#:

    public int ArrayPairSum(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0 || length % 2 != 0)

        {

            return 0;

        }

        Array.Sort(nums);

        int sum = 0;

        for (int i = 0; i < length; i += 2)

        {

            sum += nums[i];

        }

        return sum;

    }

Complexity: O(nlogn)