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.
- Difficulty: Easy
- Topics: Arrays, Sorting, Greedy, Counting Sort
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 40nums.length is even.-1000 <= nums[i] <= 1000
Hints for Array Partition
Hint 1
Every pair throws away its larger element, so you want the discarded halves to be as small as possible.
Hint 2
Sorting and pairing neighbours achieves that: each element is wasted against the value nearest above it.
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
- Sort the array.
- 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