Log inSign up
easyLeetCodeNot Started

Array Partition

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Standard 4-element Array:

Input: nums = [1, 4, 3, 2]
Output: 4
Explanation: All possible pairings: 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 The maximum sum of minimums is 4.

Example 2 · 6-element Array with Duplicates:

Input: nums = [6, 2, 6, 5, 1, 2]
Output: 9
Explanation: Sort the array: [1, 2, 2, 5, 6, 6]. Pair adjacent elements: (1, 2), (2, 5), (6, 6). Sum of minimums = min(1, 2) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Example 3 · Negative Numbers:

Input: nums = [-1, -4, -3, -2]
Output: -5
Explanation: Sort the array: [-4, -3, -2, -1]. Optimal pairing: (-4, -3) and (-2, -1). Sum = min(-4, -3) + min(-2, -1) = -4 + (-2) = -5.

Constraints:

  • 1 <= n <= 104
  • nums.length == 2 * n (array length is always even)
  • -104 <= nums[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array indexing and traversal
  • Basic sorting algorithms and Big-O complexity
  • Greedy strategy intuition (local optimal choices)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mathematical intuition behind pairing adjacent elements in sorted arrays.
  • Formulate greedy invariants to prove why sorting yields the optimal sum of minimums.
  • Implement the single-pass sum over even indices: sum += nums[i] where i = 0, 2, 4, ...
  • Compare comparison sort (O(N log N)) with Counting Sort (O(N + K)) for bounded input ranges.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks to partition an array of 2n elements into pairs to maximize or minimize a sum of minimums/maximums.
  • The operation min(a, b) causes the larger number in every pair to be sacrificed/discarded.
  • To minimize waste of large numbers, numbers with similar magnitudes should be grouped together.

Algorithmic Decision Tree:

  • Whenever you need to pair numbers to minimize the gap or wasted potential -> Sort the array first.
  • After sorting in ascending order, pair adjacent elements (nums[2i], nums[2i+1]) and sum elements at even indices.
  • If the range of elements is small (e.g. [-104, 104]), Counting Sort can achieve O(N + K) linear time.

Connected Patterns:

Greedy PairingSorting & Two PointersInterval SchedulingMinimizing Maximum Pair Sum

1. Brute Force — Generate All Pairings

Intuition

Recursively generate all valid ways to pair the 2n elements, compute the sum of minimums for each pairing, and return the maximum.

Algorithm

  1. Track used elements with a boolean visited array.
  2. Find the first unvisited element at index i.
  3. Pair it with every subsequent unvisited element at index j (j > i).
  4. Mark i and j as visited, recursively solve for remaining elements, and add min(nums[i], nums[j]).
  5. Backtrack by unmarking i and j to explore other pairings.
  6. Return the maximum sum found across all complete pairings.

Brute Force All Partition Pairings

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 3, 2]
Current operationSTEP 1 OF 6
Step 1: Test grouping (1, 4) and (3, 2)
Visual state
Values and pointers at this exact step
array
S
1
4
3
2
0
↑ Pair 1: (1, 4)
1
2
↑ Pair 2: (3, 2)
3
Variables at this step
Pairing
[(1, 4), (3, 2)]
Sum
3
maxSum
3
Check / comparison
Pairing A: (1, 4) and (3, 2). min(1, 4) + min(3, 2) = 1 + 2 = 3.
Decision / next transition
maxSum = 3.
Why this step matters

Step 1: Test grouping (1, 4) and (3, 2). Minimum sum is 1 + 2 = 3. Set maxSum = 3.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <climits>
3#include <iostream>
4#include <vector>
5using namespace std;
6
7// Brute force helper to explore all pairings
8int findMaxPairSum(vector<int>& nums, vector<bool>& visited, int count) {
9 int n = nums.size();
10 if (count == n) return 0; // All elements paired
11
12 // Find first unvisited element
13 int first = -1;
14 for (int i = 0; i < n; i++) {
15 if (!visited[i]) {
16 first = i;
17 break;
18 }
19 }
20 if (first == -1) return 0;
21
22 visited[first] = true;
23 int maxSum = INT_MIN;
24
25 // Try pairing __SF_TOKEN_A__ with every other unvisited element
26 for (int j = first + 1; j < n; j++) {
27 if (!visited[j]) {
28 visited[j] = true;
29 int currentSum = min(nums[first], nums[j]) + findMaxPairSum(nums, visited, count + 2);
30 maxSum = max(maxSum, currentSum);
31 visited[j] = false; // Backtrack
32 }
33 }
34
35 visited[first] = false; // Backtrack
36 return maxSum;
37}
38
39int arrayPairSumBruteForce(vector<int>& nums) {
40 vector<bool> visited(nums.size(), false);
41 return findMaxPairSum(nums, visited, 0);
42}
43
44int main() {
45 vector<int> nums = {1, 4, 3, 2};
46 cout << "Output: " << arrayPairSumBruteForce(nums) << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O((2N)!) — The number of ways to partition 2N elements into N pairs is (2N - 1) × (2N - 3) × ... × 1 = (2N)! / (2N × N!), which grows factorially.
  • Space complexity: O(N) — The recursive call stack reaches a maximum depth of N (where 2N is array length), using O(N) auxiliary stack space.

Why Brute Force Doesn't Scale:

For N = 10 (array size 20), there are over 654 million possible pairings to check. For N = 10,000, the number of permutations exceeds the number of atoms in the universe.

By mathematical proof, pairing adjacent elements in sorted order always minimizes the sacrifice of large numbers, reducing the problem from factorial time down to standard O(N log N) sorting.

At 2N = 20: Brute force checks 654,729,075 pairings (~2.5s). Sorting takes 20 log(20) ≈ 86 ops (< 0.001ms).

2. Better — Sort & Sum Even Indices

Intuition

Sort the array in ascending order. Pair adjacent elements (nums[2i], nums[2i+1]) and sum all numbers at even indices (0, 2, 4, ...).

Algorithm

  1. Sort the array nums in ascending order.
  2. Initialize totalSum = 0.
  3. Loop with index i from 0 to nums.length - 1 with a step of 2 (i += 2).
  4. Add nums[i] to totalSum.
  5. Return totalSum after the loop completes.

Sort + Greedy Adjacent Pairing

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 3, 2]
Current operationSTEP 1 OF 6
Step 1: To sacrifice the smallest number possible when taking min(a, b), sort ascending to pair elements with their immediate neighbors
Visual state
Values and pointers at this exact step
array
S
1
4
3
2
0
↑ Unsorted input
1
2
3
Variables at this step
Action
Sort
nums
[1, 2, 3, 4]
Check / comparison
To maximize sum of min(a, b), we must pair numbers as closely as possible.
Decision / next transition
Sort array ascending: [1, 2, 3, 4].
Why this step matters

Step 1: To sacrifice the smallest number possible when taking min(a, b), sort ascending to pair elements with their immediate neighbors.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Optimal: Sort and sum elements at even indices
7int arrayPairSum(vector<int>& nums) {
8 sort(nums.begin(), nums.end());
9
10 int totalSum = 0;
11 for (int i = 0; i < (int)nums.size(); i += 2) {
12 totalSum += nums[i]; // Add minimum of each pair
13 }
14 return totalSum;
15}
16
17int main() {
18 vector<int> nums = {1, 4, 3, 2};
19 cout << "Output: " << arrayPairSum(nums) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting an array of size N takes O(N log N) time using standard IntroSort / TimSort. The subsequent loop steps through every 2nd element (N/2 iterations), taking O(N) time. Overall time complexity is dominated by sorting: O(N log N).
  • Space complexity: O(1) or O(log N) — In-place sorting uses O(1) auxiliary space beyond the O(log N) stack space required by the sorting algorithm.

3. Optimal — Counting Sort for Bounded Range

Intuition

Since values are bounded in [-104, 104], use a frequency array to achieve linear O(N + K) time.

Algorithm

  1. Create a frequency array of size 20001 with OFFSET = 10000.
  2. Populate the frequency of each number in nums.
  3. Maintain a boolean flag shouldAdd = true.
  4. Iterate through the frequency array from lowest to highest value.
  5. While a value's frequency > 0, if shouldAdd is true, add the value to totalSum.
  6. Toggle shouldAdd = !shouldAdd and decrement frequency.

Counting Sort Frequency Array Traversal

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 4, 3, 2]
Current operationSTEP 1 OF 6
Step 1: Use Counting Sort to sort in linear time without comparison
Visual state
Values and pointers at this exact step
array
S
1
4
3
2
0
↑ Count offset
1
2
3
Variables at this step
Frequencies
{ 1:1, 2:1, 3:1, 4:1 }
take
true
sum
0
Check / comparison
Values are in range [-10000, 10000]. Build frequency array count[20001].
Decision / next transition
Populate counts for 1, 4, 3, 2.
Why this step matters

Step 1: Use Counting Sort to sort in linear time without comparison. Count frequencies of each number.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Counting Sort: Linear time for bounded range [-10000, 10000]
6int arrayPairSumCountingSort(vector<int>& nums) {
7 const int OFFSET = 10000;
8 vector<int> count(20001, 0);
9
10 for (int num : nums) {
11 count[num + OFFSET]++;
12 }
13
14 int totalSum = 0;
15 bool shouldAdd = true;
16
17 for (int i = 0; i < 20001; i++) {
18 while (count[i] > 0) {
19 if (shouldAdd) {
20 totalSum += (i - OFFSET); // Add minimum
21 }
22 shouldAdd = !shouldAdd; // Toggle for partner
23 count[i]--;
24 }
25 }
26 return totalSum;
27}
28
29int main() {
30 vector<int> nums = {1, 4, 3, 2};
31 cout << "Output: " << arrayPairSumCountingSort(nums) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N + K) — Counting frequencies takes O(N) time. Scanning the frequency table of size K = 20,001 takes O(K) time. Total time is O(N + K), which is linear when K is constant.
  • Space complexity: O(K) — Requires a fixed frequency array of size K = 20,001 to store counts of integers in range [-10000, 10000].

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All PermutationsO((2N)!)O(N)Generate all possible pairings, compute the sum of minimums for each, and find the maximum.Factorial growth in number of pairing combinations.
2.Optimal — Sort and Sum Even IndicesO(N log N)O(1)Sort array ascending, pair adjacent elements (nums[2i], nums[2i+1]), and sum even indices.Comparison-based sorting time.
3.Better / Alternative — Counting SortOptimalO(N + K)O(K)Use a frequency array for numbers in range [-104, 104] to sort in linear time.Space depends on the value range K.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Sorting in descending order and summing even indices (which takes the larger element instead of the minimum).

Pitfall 2:

Trying to use greedy maximum pairs (e.g. pairing largest with smallest), which severely reduces the sum.

Pitfall 3:

Forgetting that JavaScript's default .sort() sorts lexicographically; always use .sort((a, b) => a - b).

Crucial Edge Cases to Validate:

  • Array with exactly two elements (nums = [1, 2]) -> only one pair possible, returns 1.
  • Array with all identical elements (nums = [5, 5, 5, 5]) -> returns 5 + 5 = 10.
  • All negative numbers (nums = [-1, -4, -3, -2]) -> sorting yields [-4, -3, -2, -1], answer is -4 + (-2) = -5.
  • Array with alternating negative and positive numbers (nums = [-10, 10, -5, 5]).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by explaining the greedy intuition: 'In every pair, the larger value is wasted. To minimize waste, pair elements with minimal difference.'
  2. Write the clean 3-line sorted summation solution first.
  3. Mention the Counting Sort alternative to demonstrate deep knowledge of bounded integer optimization (O(N + K) linear time).
  4. State time complexity as O(N log N) dominated by sorting, with O(1) extra memory.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Array Partition?

2.Why is the brute force approach suboptimal for large inputs in Array Partition?

3.Which data structure or technique enables the optimal solution for Array Partition?

Back to DSA Sheet