561. Array Partition I

// LeetCode URL: https://leetcode.com/problems/array-partition-i/

import java.util.Arrays;

/**
 * Refer:
 * https://leetcode.com/problems/array-partition-i/discuss/102170/Java-Solution-Sorting.-And-rough-proof-of-algorithm.
 *
 * Time Complexity: O(N log N + N). Sorting + Iterating over sorted array.
 *
 * Space Complexity: O(N). Space required for sorting.
 *
 * N = Length of input array.
 */
class Solution1 {
    public int arrayPairSum(int[] nums) {
        if (nums == null || nums.length % 2 != 0) {
            return 0;
        }

        Arrays.sort(nums);
        int pairSum = 0;

        for (int i = 0; i < nums.length; i += 2) {
            pairSum += nums[i];
        }

        return pairSum;
    }
}

/**
 * Refer:
 * https://leetcode.com/problems/array-partition-i/discuss/102180/Java-O(n)-beats-100
 *
 * Time Complexity: O(N + 20001).
 *
 * Space Complexity: O(20001).
 *
 * N = Length of input array.
 */
class Solution2 {
    public int arrayPairSum(int[] nums) {
        if (nums == null || nums.length % 2 != 0) {
            return 0;
        }

        int[] count = new int[20001];
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int n : nums) {
            int idx = n + 10000;
            count[idx]++;
            max = Math.max(max, idx);
            min = Math.min(min, idx);
        }

        int pairSum = 0;

        boolean even = true;
        for (int i = min; i <= max; i++) {
            while (count[i] > 0) {
                if (even) {
                    pairSum += i - 10000;
                }
                even = !even;
                count[i]--;
            }
        }

        return pairSum;
    }
}