Leetcode 561. Array Partition I

Problem Explanation

The problem is to group every two elements in a given array of length 2n- where n is a positive integer in the range of [1, 10000]. For instance, in the array [1,4,3,2], pairs could be established as follows: (1,4), (3,2). Though, our aim is to make the sum of the smaller number of each pair as large as possible.

This implies that, in each pair, the number which would add to the total sum would be the smaller one. Thus, to increase the sum, we must maximize the smaller numbers. We do this by sorting array elements to ensure the smaller numbers are maximized.

Let's take the above mentioned array as an example- [1,4,3,2]. This array could be sorted ascendingly to obtain [1,2,3,4]. Pairs could be produced by grouping every two adjacent numbers. In this instance, the pairs would be (1,2) and (3,4). We would then add the smaller elements of each pair to get the final sum. In this case, sum would be 1+3 = 4.

Solution Approach

A simple yet effective approach to solve this problem is to sort the array in non-decreasing order and create pairs of two consecutive elements. The reason behind this is that sorting the array puts the elements in the most probable order to increase total sum- which means, the pairs would be set in a way that the smaller number are maximized and contribute to the final sum. Since the pair with the larger element wouldn't be adding to the sum if it is situated with an even larger element, it should be added with the smallest possible number- in this case, the next smallest number. This happens naturally when array is sorted in a non-decreasing order.

After forming pairs, we would add the smallest elements of each pair to get the maximum possible total sum of minimum numbers.

Walking through a small example, if we have array [1,4,3,2], we would:

  1. Sort the array to get [1,2,3,4].
  2. Form pairs of consecutive elements to get (1,2) and (3,4).
  3. Find the sum of minimum elements in each pair to get 1+3 = 4.

Python Solution

1
2python
3class Solution:
4    def arrayPairSum(self, nums: List[int]) -> int:
5        # Sort the nums
6        nums.sort()
7
8        return sum(nums[i] for i in range(0, len(nums), 2))

The Python solution sorts the array in non-decreasing order using the built-in sort() function and then finds the sum of all alternate elements starting from the first element. It does this by using list comprehension where it generates a sequencer of alternate index values i.e. 0,2,4... and uses them to access those elements from the array - essentially picking up first element from each pair.

Java Solution

1
2java
3class Solution {
4    public int arrayPairSum(int[] nums) {
5        // Sort the array
6        Arrays.sort(nums);
7
8        int sum = 0;
9
10        // Find sum of alternate numbers starting from first element
11        for (int i = 0; i < nums.length; i += 2) {
12            sum += nums[i];
13        }
14
15        return sum;
16    }
17}

Java solution, quite similar to python solution, sorts the array using Arrays.sort() and then iterates over array with step size of two to find sum of every alternate element starting from first element.

JavaScript Solution

1
2javascript
3var arrayPairSum = function(nums) {
4    // Sort the array in non-decreasing order
5    nums.sort((a, b) => a - b);
6
7    let sum = 0;
8
9    // Find sum of alternate numbers starting from first element
10    for (let i = 0; i < nums.length; i += 2) {
11        sum += nums[i];
12    }
13
14    return sum;
15};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int arrayPairSum(vector<int>& nums) {
6        // Sort the vector
7        sort(nums.begin(), nums.end());
8
9        int sum = 0;
10
11        // Find sum of alternate numbers starting from first element
12        for (int i = 0; i < nums.size(); i += 2) {
13            sum += nums[i];
14        }
15
16        return sum;
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public int ArrayPairSum(int[] nums) {
5        // Sort array
6        Array.Sort(nums);
7
8        int sum = 0;
9
10        // Find sum of alternate numbers starting from first element
11        for (int i = 0; i < nums.Length; i += 2) {
12            sum += nums[i];
13        }
14
15        return sum;
16    }
17}

The C# solution revolves around the same approach as previous solutions. It sorts the array using Array.Sort() and then finds sum of every alternate element (1st element from every pair) by iterating over the array with step size of 2.

Thus, all the aforementioned solutions follow the same approach to solve the problem by sorting the array and finding sum of alternate elements.# Go Solution

In Go, the sort.Ints() function is used to sort the slice in ascending order.

1
2go
3package main
4import (
5	"fmt"
6	"sort"
7)
8
9func arrayPairSum(nums []int) int {
10	// Sort the slice
11	sort.Ints(nums)
12
13	sum := 0
14
15	// Take alternate numbers starting from first element
16	for i := 0; i < len(nums); i += 2 {
17		sum += nums[i]
18	}
19
20	return sum
21}

The Go solution precisely mirrors the logic implemented in other languages. After sorting, it uses a basic for loop to add the smaller number in each pair to the total sum.

Summary

The key to finding the maximum possible sum of the least numbers in each pairing lies in sorting the array and then selecting the smallest number in each pair. By sorting the array, we increase the potential of getting a higher least value in each pair. We then sum this least value across all pairs to achieve the maximum possible sum.

Each of the Python, Java, JavaScript, C++, C# and Go solutions follow this general approach. The basis of these solutions lies in sorting the array or list then summing alternate values to ensure the smallest value in each pair is included in the final sum. This common solution approach leads to an uncomplicated and effective answer to this problem.


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 👨‍🏫