Array Partition

Easy
260.

Array Partition

Array Partition is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

Given an integer array nums of 2n integers, group them into n pairs so that the sum of min(a, b) over all pairs is as large as possible.

Return that maximised sum.

Example 1

Input
nums = [1,4,3,2]
Output
4
Explanation
Pairing (1,2) and (3,4) gives 1 + 3 = 4.

Example 2

Input
nums = [6,2,6,5,1,2]
Output
9
Explanation
(2,1), (2,5) and (6,6) give 1 + 2 + 6 = 9.

Example 3

Input
nums = [1,1]
Output
1

Constraints

  • 2 <= nums.length <= 40
  • nums.length is even.
  • -1000 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Array Partition — Solution in Python, Java & C++

Array Partition solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and sorting.

Array Partition is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

Problem statement

Given an integer array nums of 2n integers, group them into n pairs so that the sum of min(a, b) over all pairs is as large as possible.

Return that maximised sum.

Example 1

Input: nums = [1,4,3,2]
Output: 4
Explanation: Pairing (1,2) and (3,4) gives 1 + 3 = 4.

Example 2

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: (2,1), (2,5) and (6,6) give 1 + 2 + 6 = 9.

Example 3

Input: nums = [1,1]
Output: 1

Constraints

  • 2 <= nums.length <= 40
  • nums.length is even.
  • -1000 <= nums[i] <= 1000

Hints for Array Partition

  1. Hint 1

    Every pair throws away its larger element, so you want the discarded halves to be as small as possible.

  2. Hint 2

    Sorting and pairing neighbours achieves that: each element is wasted against the value nearest above it.

  3. Hint 3

    The answer is then the sum of every element at an even index.

How to solve Array Partition

Sort and pair neighbours; the sum of the elements at even indices is the maximum.

Approach

  1. Sort the array.
  2. Sum a[0], a[2], a[4], ….

Why it works

Each pair discards its larger member, so the total wasted value is minimised by pairing each element with the nearest value above it. In sorted order that is the adjacent-pair pairing, and its minima are exactly the even-index elements.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Pairing smallest with largest is the intuitive wrong answer — it wastes the large values entirely.

Reference solution

Python

def arrayPairSum(nums) -> int:
    a = sorted(nums)
    return sum(a[::2])

Java

public static int arrayPairSum(int[] nums) {
    int[] a = Arrays.copyOf(nums, nums.length);
    Arrays.sort(a);
    int sum = 0;
    for (int i = 0; i < a.length; i += 2) sum += a[i];
    return sum;
}

C++

int arrayPairSum(vector<int>& nums) {
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int sum = 0;
    for (size_t i = 0; i < a.size(); i += 2) sum += a[i];
    return sum;
}

JavaScript

var arrayPairSum = function(nums) {
    const a = nums.slice().sort(function(x, y) { return x - y; });
    let sum = 0;
    for (let i = 0; i < a.length; i += 2) sum += a[i];
    return sum;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms