Leetcode – Array Partition Solution in Python

Spread the love

Array Partition is a classical problem, which is often seen in coding interviews and coding platforms like Leetcode. In this article, we will dive deep into the Array Partition problem, understand its different aspects, and solve it using Python. We will also explore different approaches and analyze their complexities.

Problem Statement

Leetcode problem #561 is titled “Array Partition I” and it states.

Given an integer array nums of 2n integers, pair 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 in each pair) are:
1. (1, 4), (3, 2) -> min(1, 4) + min(3, 2) = 1 + 2 = 3
2. (1, 3), (4, 2) -> min(1, 3) + min(4, 2) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Approaches to Solve the Problem

1. Sorting

The most intuitive way to approach this problem is to sort the array. Once the array is sorted, we can pair adjacent elements, ensuring that the difference between the numbers in each pair is minimized. This strategy guarantees the maximization of the sum of the smaller elements.

def arrayPairSum(nums):
    return sum(sorted(nums)[::2])

Explanation

  1. Sort the array using the built-in sorted() function.
  2. Slice the array using [::2] to get every other element starting from index 0. This gives us all the minimum elements of the pairs.
  3. Sum the sliced array using sum().

Time Complexity

The time complexity is O(n log n), where n is the length of the array. This is due to the sorting step. The space complexity is O(1) as we are not using extra space proportional to the input size.

2. Bucket Sort (Counting Sort)

When the range of integers in the array is known or is not very large, we can make use of Bucket Sort, which has a linear time complexity. In this problem, the range is from -10^4 to 10^4.

def arrayPairSum(nums):
    # Bucket sort
    bucket = [0] * 20001
    offset = 10000
    for num in nums:
        bucket[num + offset] += 1
        
    # Build the result
    result = 0
    need_new_pair = True
    for i, count in enumerate(bucket):
        while count > 0:
            if need_new_pair:
                result += i - offset
            need_new_pair = not need_new_pair
            count -= 1
            
    return result

Explanation

  1. Initialize an array bucket of size 20001 (range of integers + 1) to keep count of each integer.
  2. Count the occurrences of each number and store it in the bucket.
  3. Iterate through the bucket and for every non-zero count, add the number to the result if we need to start a new pair, and toggle the flag need_new_pair.

Time Complexity

The time complexity is O(n) since we only iterate through the array and the bucket. The space complexity is O(1) as the size of the bucket is constant and does not grow with the input size.

3. Greedy Algorithm with In-Place Sorting

An optimization over the sorting approach is to use in-place sorting which will reduce the space complexity.

def arrayPairSum(nums):
    nums.sort()
    return sum(nums[i] for i in range(0, len(nums), 2))

Explanation

This approach is similar to the first one, but we are using in-place sorting using the sort() method.

Time Complexity

The time complexity remains O(n log n) due to sorting, but the space complexity is improved to O(1).

Conclusion

We explored three different approaches to solving the Array Partition problem on LeetCode using Python. While sorting is an intuitive approach, using a bucket sort can be more efficient when the range of numbers is not very large. The in-place sorting approach is also a good balance between ease of understanding and space efficiency. Choose the approach that best fits the constraints and requirements of your specific situation.

Leave a Reply