Skip to main content
Talentd

Array Partition - Solution & Explanation

EasyArrayGreedySortingCounting Sort16 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

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:

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 <= 104
  • nums.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:

The C code starts by sorting the array using the built-in qsort() function. Once sorted, we iterate over the array taking sum of every alternate element starting from index 0, because these represent the minimum in every pair if paired in sorted order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as no additional space is used except for input.

Try this approach in the editor →

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.

This C implementation utilizes counting sort for the defined range of input values. We update a count array and adjust it for each occurrence shifting values. The iteration through the count array allows us to easily compute the required sum by alternating over counts.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + range) due to counting sort.
Space Complexity: O(range) for the count array.

Try this approach in the editor →

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.

Code

PythonJavaC++GoRustJavaScript

Python

Java

C++

Go

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Pairing Strategy

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as no additional space is used except for input.

Greedy Pairing Strategy with Counting Sort Optimization

Time Complexity: O(n + range) due to counting sort.
Space Complexity: O(range) for the count array.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Pairing StrategyO(n log n)O(1) to O(log n)General case. Most common interview solution and easiest to implement.
Greedy with Counting Sort OptimizationO(n + k)O(k)When the integer range is bounded. Avoids comparison sorting for linear performance.

Video Solution

LeetCode Array Partition I Solution Explained - Java • Nick White • 15,507 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Array Partition with our built-in code editor and test cases.

Practice on FleetCode
Previous

All Divisions With the Highest Score of a Binary Array

Next

Minimum Cost of Buying Candies With Discount