Array Partition solution and explanation
Google
9 more videos on this problem
LeetCode Array Partition I Solution Explained - JavaNick White · 3:25 · 15K views
Leetcode 561 - Array Partition I (JAVA Solution Explained!)LC Bear · 5:16 · 5K views
561. Array Partition || Leetcode || EnglishAyan this side · 5:57 · 4K views
Facebook Coding Interview: Array Partition I (LeetCode)Matt Upham | Tech + Coding · 5:01 · 3K views
561. Array Partition || In JAVA || Leetcode Problem || Easy #leetcodeQuick Learning With Sree · 4:29 · 1K views
LeetCode 561 : Array Partition || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 10:07 · 921 views
Leetcode 561. Array Partition I PythonTechZoo · 3:27 · 915 views
LeetCode Algorithms Easy: Array Partition IMike the Coder · 5:14 · 604 views
LeetCode 561. Array Partition I JavaScript Solution: One LineLearn Code · 1:48 · 325 views
LeetCode 561. Array Partition || Java Solution WalkthroughUnknown Koder · 14:47 · 321 views
The problem
Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.
Example 1:
Input: nums = [1,4,3,2] Output: 4 Explanation: All possible pairings (ignoring the ordering of elements) are: 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 So the maximum possible sum is 4.
Example 2:
Input: nums = [6,2,6,5,1,2] Output: 9 Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.
Constraints:
1 <= n <= 104nums.length == 2 * n-104 <= nums[i] <= 104
Approach overview
Problem Overview: You receive an array of 2n integers. The task is to form n pairs so that the sum of the minimum value in each pair is maximized. The trick is realizing that pairing decisions affect which numbers become the minimums contributing to the final sum.
Approach 1: Sorting and Pairing Strategy (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
The simplest and most reliable strategy is to sort the array first. Once sorted, pair adjacent elements: (nums[0], nums[1]), (nums[2], nums[3]), and so on. The key insight is that in each pair, the smaller element contributes to the sum. Sorting ensures that small numbers are grouped together instead of being wasted as the minimum in pairs with very large numbers. After sorting, iterate through the array and add every element at an even index (0, 2, 4...) to the result. Sorting dominates the runtime at O(n log n), while the pairing scan is linear. This approach uses concepts from Sorting and a simple Greedy strategy.
Approach 2: Greedy Pairing with Counting Sort Optimization (Time: O(n + k), Space: O(k))
The constraints guarantee that numbers fall within a limited range (typically -10000 to 10000). Instead of sorting with comparison-based algorithms, build a frequency array and simulate a Counting Sort. Iterate through the frequency array in increasing order and track whether the current number should be included in the sum or skipped. Every second element encountered becomes the minimum of a pair and is added to the result. This effectively recreates the sorted order without performing an explicit sort. The complexity becomes O(n + k), where k is the numeric range. This method leverages Counting Sort and still follows the same greedy observation: maximize the contribution of smaller numbers by pairing them early.
Recommended for interviews: The sorting approach is the expected solution in most interviews. It is easy to reason about and clearly demonstrates the greedy insight that pairing adjacent numbers in sorted order maximizes the sum of pair minimums. The counting sort optimization shows deeper awareness of constraints and can reduce runtime to linear when the value range is bounded. Mentioning both approaches shows strong algorithmic judgment.
Approach 1: Sorting and Pairing Strategy
The core idea of this approach is to pair up the elements after sorting the array to maximize the minimum sum of pairs. By sorting the array, the smallest values are naturally grouped together, maximizing your result. After sorting, pair the elements from the start with their consecutive neighbor. This guarantees maximal sum of mins in pairs.
Let us see how we can implement this in various programming languages:
def arrayPairSum(nums):
nums.sort()
return sum(nums[i] for i in range(0, len(nums), 2))
nums = [6, 2, 6, 5, 1, 2]
result = arrayPairSum(nums)
print(result)import java.util.Arrays;
public class ArrayPartition {
public static int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i += 2) {
sum += nums[i];
}
return sum;
}
public static void main(String args[]) {
int[] nums = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums);
System.out.println(result);
}
}#include <iostream>
#include <vector>
#include <algorithm>
int arrayPairSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int sum = 0;
for (int i = 0; i < nums.size(); i += 2) {
sum += nums[i];
}
return sum;
}
int main() {
std::vector<int> nums = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums);
std::cout << result << std::endl;
return 0;
}function arrayPairSum(nums) {
nums.sort((a, b) => a - b);
let sum = 0;
for (let i = 0; i < nums.length; i += 2) {
sum += nums[i];
}
return sum;
}
const nums = [6, 2, 6, 5, 1, 2];
const result = arrayPairSum(nums);
console.log(result);#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int arrayPairSum(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int sum = 0;
for (int i = 0; i < numsSize; i += 2) {
sum += nums[i];
}
return sum;
}
int main() {
int nums[] = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums, 6);
printf("%d", result);
return 0;
}using System;
class Program
{
static int ArrayPairSum(int[] nums)
{
Array.Sort(nums);
int sum = 0;
for (int i = 0; i < nums.Length; i += 2)
{
sum += nums[i];
}
return sum;
}
static void Main()
{
int[] nums = {6, 2, 6, 5, 1, 2};
int result = ArrayPairSum(nums);
Console.WriteLine(result);
}
}In Python, the function sorts the list using sort(). Then, it sums every second element starting from 0 using list comprehension.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1), if we ignore the space used by the sort operation.
Approach 2: Greedy Pairing Strategy with Counting Sort Optimization
Instead of using a traditional sorting method, we can optimize the sorting step with a counting sort. This is particularly useful given the constraints - limited range of numbers. This approach uses a counting array to sort, followed by picking elements at alternate indices in a manner similar to the previous approach.
def arrayPairSum(nums):
count = [0] * 20001
offset = 10000
for num in nums:
count[num + offset] += 1
sum_val = 0
odd = True
for i in range(len(count)):
while count[i] > 0:
if odd:
sum_val += i - offset
odd = not odd
count[i] -= 1
return sum_val
nums = [6, 2, 6, 5, 1, 2]
result = arrayPairSum(nums)
print(result)public class ArrayPartition {
public static int arrayPairSum(int[] nums) {
int[] count = new int[20001];
for (int num : nums) {
count[num + 10000]++;
}
int sum = 0;
boolean odd = false;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
if (!odd) {
sum += (i - 10000);
}
odd = !odd;
count[i]--;
}
}
return sum;
}
public static void main(String args[]) {
int[] nums = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums);
System.out.println(result);
}
}#include <iostream>
#include <vector>
#include <cstring>
int arrayPairSum(std::vector<int>& nums) {
const int RANGE = 20001;
int count[RANGE];
std::memset(count, 0, sizeof(count));
for (int num : nums) {
++count[num + 10000];
}
int sum = 0;
bool odd = false;
for (int i = 0; i < RANGE; ++i) {
while (count[i] > 0) {
if (!odd) {
sum += (i - 10000);
}
odd = !odd;
--count[i];
}
}
return sum;
}
int main() {
std::vector<int> nums = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums);
std::cout << result << std::endl;
return 0;
}function arrayPairSum(nums) {
let count = new Array(20001).fill(0);
const offset = 10000;
for (let num of nums) {
count[num + offset]++;
}
let sum = 0;
let odd = true;
for (let i = 0; i < count.length; i++) {
while (count[i] > 0) {
if (odd) {
sum += i - offset;
}
odd = !odd;
count[i]--;
}
}
return sum;
}
const nums = [6, 2, 6, 5, 1, 2];
const result = arrayPairSum(nums);
console.log(result);#include <stdio.h>
#include <string.h>
#define RANGE 20001 // Since range is fixed between -10^4 to 10^4
int arrayPairSum(int* nums, int numsSize) {
int count[RANGE];
memset(count, 0, sizeof(count));
for (int i = 0; i < numsSize; ++i) {
++count[nums[i] + 10000];
}
int sum = 0;
int odd = 0;
for (int i = 0; i < RANGE; ++i) {
while (count[i] > 0) {
if (odd == 0) {
sum += (i - 10000);
}
odd = 1 - odd;
--count[i];
}
}
return sum;
}
int main() {
int nums[] = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums, 6);
printf("%d", result);
return 0;
}using System;
class Program
{
static int ArrayPairSum(int[] nums)
{
int[] count = new int[20001];
foreach (var num in nums)
{
count[num + 10000]++;
}
int sum = 0;
bool odd = true;
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
if (odd)
{
sum += i - 10000;
}
odd = !odd;
count[i]--;
}
}
return sum;
}
static void Main()
{
int[] nums = {6, 2, 6, 5, 1, 2};
int result = ArrayPairSum(nums);
Console.WriteLine(result);
}
}The Python code showcases an adaptation of counting approach for determining optimal pairing using counting elements to achieve maximal possible minimum sum during translation into a simplified list state.
Time Complexity: O(n + range) owing to dual linear iterations.
Space Complexity: O(range), necessary for count indexes.
Approach 3: Sorting
For a pair of numbers (a, b), we can assume a leq b, then min(a, b) = a. In order to make the sum as large as possible, the b we choose should be as close to a as possible, so as to retain a larger number.
Therefore, we can sort the array nums, then divide every two adjacent numbers into a group, and add the first number of each group.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array nums.
func arrayPairSum(nums []int) (ans int) {
sort.Ints(nums)
for i := 0; i < len(nums); i += 2 {
ans += nums[i]
}
return
}impl Solution {
pub fn array_pair_sum(mut nums: Vec<i32>) -> i32 {
nums.sort();
nums.iter().step_by(2).sum()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Pairing Strategy | Time Complexity: O(n log n) for sorting. |
| Greedy Pairing Strategy with Counting Sort Optimization | Time Complexity: O(n + range) owing to dual linear iterations. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Pairing Strategy | O(n log n) | O(1) to O(log n) | General case. Most common interview solution and easiest to implement. |
| Greedy with Counting Sort Optimization | O(n + k) | O(k) | When the integer range is bounded. Avoids comparison sorting for linear performance. |
Frequently asked questions
Is Array Partition easy or hard?
Array Partition is classified as an Easy problem on LeetCode with an acceptance rate above 80%. The main challenge is recognizing the greedy insight that sorting and pairing adjacent elements maximizes the sum of pair minimums. Once that observation is made, the implementation is straightforward.
Array Partition Python/Java solution
In Python or Java, the typical solution sorts the array using built-in sorting utilities and sums elements at indices 0, 2, 4, and so on. Python uses nums.sort() followed by a loop stepping by two, while Java uses Arrays.sort(nums). Both implementations run in O(n log n) time and are concise.
How to solve Array Partition in O(n)?
Use a counting sort style frequency array instead of comparison sorting. Count occurrences of each number within the allowed range and iterate through the frequency array in ascending order. Track alternating elements so every second value contributes to the sum. This reconstructs the sorted order in linear time O(n + k).
What is the best approach for Array Partition?
The most common approach sorts the array and sums every element at even indices. After sorting, adjacent numbers form pairs and the smaller element contributes to the result. This greedy method works because pairing small numbers together prevents them from being wasted against much larger values. Time complexity is O(n log n) with constant extra space.
Is Array Partition asked at Google/Amazon/Meta?
Array Partition is a classic greedy problem commonly used in coding interviews and practice platforms. Variants of pairing or greedy sorting problems have appeared in interviews at large tech companies including Amazon and Meta. The problem mainly tests understanding of greedy ordering and sorting strategies.
What data structure is used in Array Partition?
The basic solution uses an array with a sorting algorithm. The optimized version uses a frequency array for counting sort, which acts as a histogram of values. Both approaches rely on sequential iteration rather than complex data structures like heaps or trees.
What is the time complexity of Array Partition?
The standard solution runs in O(n log n) time due to sorting. After sorting, computing the sum of every second element takes O(n). With a counting sort optimization that leverages the bounded value range, the runtime can be reduced to O(n + k) where k is the number range.