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.
Leetcode problem #561 is titled “Array Partition I” and it states.
Given an integer array
2n integers, pair these integers into
(a1, b1), (a2, b2), ..., (an, bn) such that the sum of
min(ai, bi) for all
i is maximized. Return the maximized sum.
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
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])
- Sort the array using the built-in
- Slice the array using
[::2]to get every other element starting from index 0. This gives us all the minimum elements of the pairs.
- Sum the sliced array using
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 =  * 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
- Initialize an array
bucketof size 20001 (range of integers + 1) to keep count of each integer.
- Count the occurrences of each number and store it in the bucket.
- 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
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))
This approach is similar to the first one, but we are using in-place sorting using the
The time complexity remains O(n log n) due to sorting, but the space complexity is improved to O(1).
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.