easy Array Partition

Problem Statement

Given an array of integers nums containing 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that sum of min(ai, bi) is maximized for all pairs.

Return the maximum possible sum of these minimum values.

Examples

1. Example 1:

   • Input: nums = [5, 3, 1, 2, 4, 6, 1, 4]
   • Output: 12
   • Explanation: Pair the integers as (1, 1), (2, 3), (4, 4) and (5, 6). The sum of the minimums is 1 + 2 + 4 + 5 = 12.

2. Example 2:

   • Input: nums = [1, 1, 1, 1, 2, 2]
   • Output: 4
   • Explanation: Pair the integers as (1, 1), (1, 1), and (2, 2). The sum of the minimums is 1 + 1 + 2 = 4.

3. Example 3:

   • Input: nums = [8, 9, 5, 6, 3, 4]
   • Output: 16
   • Explanation: Pair the integers as (3, 4), (5, 6), and (8, 9). The sum of the minimums is 3 + 5 + 8 = 16.

Constraints:

• 1 <= n <= 10⁴
• nums.length == 2 * n
• -10⁴ <= nums[i] <= 10⁴

Solution

To solve this problem, we use a counting sort approach to sort the array efficiently. The idea is to pair elements in a way that maximizes the sum of the minimum values of the pairs. By sorting the array and then pairing every two consecutive elements, we ensure that we always include the smallest possible element of each pair in the sum. This strategy works because, in a sorted array, every alternate element, starting from the smallest, will contribute to the maximum sum of the minimums.

Step-by-Step Algorithm

1. Initialize Variables:

   • Create an array count of size 20001 to hold the frequency of each element. The size is 2 * max + 1 because we need to account for both positive and negative numbers within the range [-10000, 10000].
   • Initialize sum to 0, which will hold the final result.
   • Initialize a boolean add to true, which will help in toggling between adding elements to the sum or not. It ensures that we select every alternate element in the sorted array.

2. Calculate the Frequency of Elements:

   • Loop through each element num in nums.
   • For each num, increment the count at index num + max. This step maps negative numbers to positive indices in the count array.

3. Traverse the Count Array:

   • Iterate through the count array from index 0 to 20000.
   • For each index i, while count[i] is greater than 0:
     • If add is true, add i - max to sum. This step takes the value mapped by the count array back to its original range. This step effectively helps in handling negative elements.
     • Toggle add to its opposite value. This ensures that we add every second element.
     • Decrement count[i] by 1, indicating that we have processed one occurrence of the number.

4. Return Result:

   • Return the final value of sum as the result.

Algorithm Walkthrough

Given nums = [5, 3, 1, 2, 4, 6, 1, 4]:

1. Initialize Variables:

   • max = 10000
   • count array of size 20001 initialized to all zeros.
   • sum = 0
   • add = true

2. Fill the Count Array:

   • For num = 5: count[5 + 10000]++ → count[10005] = 1
   • For num = 3: count[3 + 10000]++ → count[10003] = 1
   • For num = 1: count[1 + 10000]++ → count[10001] = 1
   • For num = 2: count[2 + 10000]++ → count[10002] = 1
   • For num = 4: count[4 + 10000]++ → count[10004] = 1
   • For num = 6: count[6 + 10000]++ → count[10006] = 1
   • For num = 1: count[1 + 10000]++ → count[10001] = 2
   • For num = 4: count[4 + 10000]++ → count[10004] = 2

3. Traverse the Count Array:

   • Starting from index 0 to 20000:
     • Indices with counts:
       • count[i] = count[10001] = 2
         • First occurrence: add = true, add 1 to sum → sum = sum + i - max = 0 + 10001 - 10000 = 1, toggle add to false, decrement count[10001]
         • Second occurrence: add = false, do not add, toggle add to true, decrement count[10001]
       • count[i] = count[10002] = 1
         • First occurrence: add = true, add 2 to sum → sum = 3, toggle add to false, decrement count[10002]
       • count[i] = count[10003] = 1
         • First occurrence: add = false, do not add, toggle add to true, decrement count[10003]
       • count[i] = count[10004] = 2
         • First occurrence: add = true, add 4 to sum → sum = 7, toggle add to false, decrement count[10004]
         • Second occurrence: add = false, do not add, toggle add to true, decrement count[10004]
       • count[i] = count[10005] = 1
         • First occurrence: add = true, add 5 to sum → sum = 12, toggle add to false, decrement count[10005]
       • count[i] = count[10006] = 1
         • First occurrence: add = false, do not add, toggle add to true, decrement count[10006]

4. Return Result:

   • The final value of sum is 12.

Code

class Solution {

  // Method to find the maximum sum of min pairs
  public int arrayPairSum(int[] nums) {
    // Determine the maximum value in the array to define the range for counting sort
    int max = 10000; // given constraint for the problem

    // Array to store the frequency of each element
    int[] count = new int[2 * max + 1];

    // Fill the count array
    for (int num : nums) {
      count[num + max]++;
    }

    // Initialize variables for calculating the sum and a flag to toggle between pairs
    int sum = 0;
    boolean add = true;

    // Traverse the count array
    for (int i = 0; i < count.length; i++) {
      while (count[i] > 0) {
        // Add to sum if the flag is true
        if (add) {
          sum += i - max;
        }
        // Toggle the flag
        add = !add;
        // Decrement the count for the current number
        count[i]--;
      }
    }

    return sum;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test case 1
    int[] nums1 = { 5, 3, 1, 2, 4, 6, 1, 4 };
    int result1 = solution.arrayPairSum(nums1);
    System.out.println("Test Case 1 Result: " + result1); // Expected Output: 12

    // Test case 2
    int[] nums2 = { 1, 1, 1, 1, 2, 2 };
    int result2 = solution.arrayPairSum(nums2);
    System.out.println("Test Case 2 Result: " + result2); // Expected Output: 4

    // Test case 3
    int[] nums3 = { 8, 9, 5, 6, 3, 4 };
    int result3 = solution.arrayPairSum(nums3);
    System.out.println("Test Case 3 Result: " + result3); // Expected Output: 16
  }
}

Complexity Analysis

Time Complexity

1. Calculating elements frequency:

   • This step involves iterating over the input array nums and updating the count array. The time complexity for this step is , where n is the length of the nums array.

2. Traversing the Count Array:

   • The count array is traversed, and each element is processed to calculate the sum of the minimum values of the pairs. Since the count array has a fixed size (20001), this step takes time.

Therefore, the overall time complexity of the algorithm is: , where n is the number of elements in the input array nums.

Space Complexity

1. Count Array:
   • The count array requires a fixed amount of space, regardless of the input size. The space required is O(20001), which simplifies to due to the fixed upper bound on the size of the array elements.