easy

Array Partition

Pair up array values to maximize the sum of each pair’s minimum.

1. Define the problem

Array Partition

Given an integer array nums of 2n integers, group these integers into n pairs, for example (a1, b1), (a2, b2), ..., (an, bn), to maximize the sum of the minimum of each pair. Return the maximized sum. First sort the array , then pair up neighbors: index 0 with index 1, index 2 with index 3, and so on — the smaller of each neighboring pair is always the even-indexed one.

Constraints

  • 1 ≤ n ≤ 104
  • nums.length == 2 * n
  • -104 ≤ numsi ≤ 104

Example

Inputnums = [1, 4, 3, 2]
Output4

Explanation Sorted, nums becomes [1, 2, 3, 4]. Pairing (1, 2) and (3, 4) gives min sum 1 + 3 = 4, the best possible.

2. Know the words first

In plain terms

Maximize the sum of the minimum
Pair the numbers so that when you take the smaller value from every pair and add those smaller values together, that total is as large as possible.
3. Visualize the solution

Sort, then sum every value at an even index

Sort, then sum every value at an even index
Statusinit

Sorted array: [1, 2, 3, 4]. Pair (index 0, 1) = (1, 2), min = 1. sum = 1.

What happens in this step

sorted = [1, 2, 3, 4]
pair (nums[0]=1, nums[1]=2), min = 1
sum = 1
Step 1 of 3

Steps to visualize

  1. Sort the array in non-decreasing order.
  2. Pair index 0 with index 1, index 2 with index 3, and so on.
  3. In each pair, the value at the even index is always the smaller one.
  4. Add up every value sitting at an even index to get the maximized sum.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sort, then sum every value at an even index
Statusinit

Sorted array: [1, 2, 3, 4]. Pair (index 0, 1) = (1, 2), min = 1. sum = 1.

What happens in this step

sorted = [1, 2, 3, 4]
pair (nums[0]=1, nums[1]=2), min = 1
sum = 1
Step 1 of 3
5. Solution

Solution

solution.tsTypeScript
function arrayPairSum(nums) {
  const sorted = nums.slice().sort((a, b) => a - b);
  let sum = 0;

  for (let i = 0; i < sorted.length; i += 2) {
    sum += sorted[i];
  }

  return sum;
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [1, 4, 3, 2]4example from the docstring
nums = [1, 2]1smallest valid input, a single pair
nums = [5, 5, 5, 5]10every value identical, sum is straightforward
nums = [-1, -2, -3, -4]-6all negative values
nums = [-1, 4, -3, 2]-1mixed positive and negative values
nums = [6, 2, 6, 5, 1, 2]9larger set with duplicate values

Keep reading