Array Partition - Leetcode Solution

Problem Statement:

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

Input: nums = [1,4,3,2] Output: 4 Explanation: All possible pairings (ignoring the ordering of elements) are:

1. (1, 2) -> min(1, 2) = 1
2. (3, 4) -> min(3, 4) = 3
3. (2, 4) -> min(2, 4) = 2
4. (1, 3) -> min(1, 3) = 1 The maximum possible sum is 1 + 3 + 2 + 1 = 7.

Example 2:

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

Solution:

In this problem, we have to form pairs from the given array such that the sum of the minimum element of each pair is maximum. We can form pairs by choosing the two smallest elements in each pair so that we can maximize the sum of minimum element in each pair. This is because if we have two elements with a large difference between them and we pair them up, we lose out on the opportunity of having a larger sum because of that difference. Hence, it is always better to pair up the smallest elements.

To solve this problem, we can sort the given array in ascending order and then form pairs by selecting every alternate element starting from index 0. We can then sum up the minimum element of each pair to get the total maximum sum.

Let's take a closer look at the code:

1. Sort the given array in ascending order.

2. Initialize a variable to store the maximum sum of minimum elements in pairs.

3. Iterate over the array with a step of two.

4. For each pair, add the minimum element to the variable initialized in step 2.

5. Return the maximum sum.

Implementation of the code:

def arrayPairSum(nums: List[int]) -> int:

    # Sort the array in ascending order.
    nums.sort()
    
    # Initialize a variable to store the sum of minimum elements
    # in pairs. Start with 0.
    max_sum = 0
    
    # Iterate over the array with a step of two to form pairs.
    for i in range(0, len(nums), 2):
        
        # Add the minimum element of each pair to the max_sum variable.
        max_sum += min(nums[i], nums[i+1])
    
    # Return the maximum sum of minimum elements in pairs.
    return max_sum

Time Complexity:

The time complexity of the above algorithm is O(nlogn) because we are sorting the given array before forming pairs, which takes O(nlogn) time. The iteration over array with a step of 2 takes O(n) time.

Space Complexity:

The space complexity of the algorithm is O(1) because we are not using any extra space.

1