561. Array Partition


Problem Description

The task is formulated around an optimization problem using an integer array named nums. This array has 2n elements, meaning that its length is an even number. The objective is to pair up the integers into n pairs in such a way that the sum of the minimum values from each pair is maximized. In mathematical terms, for pairs (a_1, b_1), (a_2, b_2), ..., (a_n, b_n), we need to find the maximum value of sum(min(a_i, b_i)) for all i from 1 to n.

To fulfill the task:

  1. We have to create the pairs from the elements in the array.
  2. Then, calculate the minimum of each pair.
  3. Finally, calculate and return the sum of all these minimum values.

The objective is to construct these pairs wisely so that we get the maximum possible sum of the minimums.

Intuition

The intuition behind the solution relies on the idea of minimizing the loss of the larger numbers and ensuring that we can maximize the sum of the smaller numbers.

A crucial observation is that in each pair (a, b), the minimum value is the one that will be included in our final sum, whereas the larger one is effectively 'wasted' in terms of contributing to the sum. Therefore, we should minimize the waste by making sure that the difference between the paired numbers is as small as possible.

To meet this goal, the following steps are considered:

  1. Sort the array in ascending order. Sorting allows us to easily group the elements into pairs in a way that minimizes the differences between the numbers within each pair.
  2. Once we have the sorted array, we can pair each element with its adjacent element without worrying about missing out on a possibly smaller or equal pair.
  3. Now that we have the pairs as adjacent elements, we know that within each pair, the first element is the smaller one (due to the array being sorted).
  4. To find the sum of all minimum elements from each pair, we can add up every second element starting from the first element in the sorted array.

The provided code does exactly that: sum(sorted(nums)[::2]) sorts the array and then uses slicing to get every second element starting from the first one (which are all the minimums in each pair), and then sums them up to get the result.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The implementation of the solution is straightforward and leverages Python's built-in functions to achieve the goal efficiently. Here's a step-by-step guide through the algorithm and the patterns used in the solution:

  1. Sorting the Array: The initial step is to use Python's built-in sorting function with sorted(nums). Sorting is a very common technique in such problems as it often simplifies and provides a structure to the data which can be exploited in a subsequent step. In this case, sorting puts the array in ascending order so that each pair (a, b) will have a as the minimum.

  2. Slicing the Array: With the sorted array, we apply slicing sorted(nums)[::2]. In Python, slicing is a way to obtain a subsequence of a list or array. The slice [::2] specifically means "start from the first element and pick every second element." This slice operation is both compact and efficient, avoiding the need for an explicit loop to go through the array and pick the elements.

  3. Summing the Minimums: Lastly, by passing the sliced list to sum(), Python's built-in function that computes the sum of the numbers in an iterable, we add up the selected numbers. The minimum of each pair is included due to the slicing, and thus the sum of these minimums is maximized.

The algorithm’s time complexity is dominated by the sorting operation, which is O(n log n) in the average and worst case scenarios. The slicing and summing are linear operations, O(n), but since n log n grows faster than n, the overall time complexity remains O(n log n).

No additional data structures are used or needed since the problem can be resolved with operations on the provided array. In terms of patterns, it's worth noting that this approach elegantly combines sorting with the properties of a sorted array to avoid a more complex and potentially less efficient approach that might explicitly build and then process pairs of numbers.

The simplicity of the approach is its strength, as it doesn’t rely on complex data structures or algorithms beyond what Python provides out of the box. The use of slicing to select every other element of an already sorted array makes the implementation both elegant and intuitive.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Example Walkthrough

Consider the array nums = [3, 1, 5, 4, 2, 6] with a length of 2n = 6, indicating that we need to create n = 3 pairs. Apply the solution approach to this example:

  1. Sorting the Array: First, sort the array in ascending order which gives us the sorted array [1, 2, 3, 4, 5, 6]. By sorting, the smallest numbers are positioned at the beginning, which will help maximize the sum of the minimums of each pair.

  2. Slicing the Array: Now, we retrieve every second element starting from the first element using slicing. From our sorted array, this yields [1, 3, 5] which represents the minimum values from each potential pair ((1,2), (3,4), (5,6)).

  3. Summing the Minimums: Finally, sum up the elements in the sliced array [1, 3, 5]. The sum is 1 + 3 + 5 = 9. This total is the maximum sum of the minimums that can be obtained by pairing up numbers in the given array.

Following this method, the code sum(sorted(nums)[::2]) provides a quick and efficient way to reach the solution, which is the sum 9 in this case. By ensuring that we pair each number with its nearest neighbor in the sorted list, we maximize the contribution of the lower number to the sum while minimizing the "waste" due to the higher number being paired with it but not counted in the sum.

Not Sure What to Study? Take the 2-min Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Python Solution

1from typing import List
2
3class Solution:
4    def arrayPairSum(self, nums: List[int]) -> int:
5        """
6        Find the max sum of min pairs in an array.
7      
8        The function takes in an array of 2n integers and we need to pair them up
9        in such a way to minimize the difference between the pairs. The sum we want
10        to maximize is the sum of the smaller number in each pair.
11      
12        :param nums: List[int] - Array of 2n integers
13        :return: int - Maximum sum of min pairs
14        """
15      
16        # Sort the array in non-decreasing order
17        sorted_nums = sorted(nums)
18      
19        # Take every other element starting from the first element
20        # because after sorting, the first element of each pair
21        # will be the smaller one
22        min_pairs_sum = sum(sorted_nums[::2])
23      
24        return min_pairs_sum
25
26# Example usage:
27# sol = Solution()
28# print(sol.arrayPairSum([1,4,3,2]))  # Output: 4
29

Java Solution

1import java.util.Arrays; // Import Arrays class for sorting
2
3public class Solution {
4  
5    // Function to maximize sum of min(ai, bi) for all pairs (ai, bi)
6    public int arrayPairSum(int[] nums) {
7        // Sort the array to make pairs of two consecutive elements
8        Arrays.sort(nums);
9
10        // Initialize sum to store the final answer
11        int sum = 0;
12
13        // Iterate through the array, jumping two steps at a time
14        for (int i = 0; i < nums.length; i += 2) {
15            // Add the first element of each pair to the sum since it's the minimum
16            sum += nums[i];
17        }
18
19        // Return the accumulated sum of the min elements of the pairs
20        return sum;
21    }
22}
23

C++ Solution

1#include <vector>
2#include <algorithm> // Include the algorithm header to use the std::sort function
3
4// Solution class contains a method to solve the problem.
5class Solution {
6public:
7    // The method arrayPairSum maximizes the minimum pair sum in an array.
8    int arrayPairSum(vector<int>& nums) {
9        // Sort the input array in non-decreasing order.
10        std::sort(nums.begin(), nums.end());
11      
12        // Initialize the answer to store the sum of the min elements of the pairs.
13        int maxMinPairSum = 0;
14      
15        // Iterate over the array, incrementing by 2 to only consider the first element of each pair (since array is sorted).
16        for (int i = 0; i < nums.size(); i += 2) {
17            // Accumulate the sum by adding the first element of each pair, which is the min of the two.
18            maxMinPairSum += nums[i];
19        }
20      
21        // Return the final sum as the answer.
22        return maxMinPairSum;
23    }
24};
25

Typescript Solution

1/**
2 * Given an integer array `nums` of 2n integers, 
3 * group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) 
4 * such that the sum of min(ai, bi) for all i is maximized. 
5 * Return the maximized sum.
6 * 
7 * @param {number[]} nums - The array of 2n integers.
8 * @return {number} - The maximized sum of min(ai, bi) for all paired integers.
9 */
10function arrayPairSum(nums: number[]): number {
11    // Sort the array in non-decreasing order
12    nums.sort((a, b) => a - b);
13    let sum: number = 0;
14
15    // Iterate through the array, increasing by 2 to consider pairs
16    for (let i = 0; i < nums.length; i += 2) {
17        // Add the minimum of each pair (which is the first element in the sorted pair)
18        sum += nums[i];
19    }
20
21    // Return the sum of minimums
22    return sum;
23}
24
25// Example usage:
26// const result: number = arrayPairSum([1, 3, 2, 4]);
27// console.log(result); // Output would be 4, because 1+3 (min of pair (1,2) + min of pair (3,4)) is the largest sum.
28
Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Time and Space Complexity

The given Python function arrayPairSum finds the sum of min(a[i], a[i+1]) for every pair of elements in the array when the array is sorted. It sorts the array and then sums up elements at even indices (i.e., considering 0-based indexing, indices 0, 2, 4, etc).

Time Complexity:

The time complexity is primarily determined by the sorting function. Python uses Timsort for sorting, which has a time complexity of O(n log n) for an average and worst-case scenario, where n is the length of the nums array.

There is also the summation operation, which iterates over every other element of the sorted array, contributing an additional O(n/2), which simplifies to O(n) time. However, since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity:

The space complexity of the sorting operation depends on the implementation. For Timsort, the worst-case space complexity is O(n), because it might need temporary space to hold elements while merging. Timsort is a hybrid sorting algorithm that requires temporary storage for the merge operations.

However, since the input array itself is sorted in-place and the result is computed using that without requiring extra space, other than what is needed for the sorted array and the sum variable, the space complexity may be considered O(1) or constant if the space used by the sorting algorithm is not taken into account, which is typically the case for space complexity analysis in Python where sorting is considered to be in-place.

In summary:

  • Time Complexity: O(n log n)
  • Space Complexity: O(1) (disregarding the space used by the sorting algorithm)

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫