Array Partition - Problem

Given an integer array nums of 2n integers, group these integers into n pairs (a₁, b₁), (a₂, b₂), ..., (aₙ, bₙ) such that the sum of min(aᵢ, bᵢ) for all i is maximized.

Return the maximized sum.

Input & Output

Example 1 — Basic Case
$ Input: nums = [1,4,3,2]
Output: 4
💡 Note: After sorting: [1,2,3,4]. Pairs: (1,2) and (3,4). Sum of minimums: min(1,2) + min(3,4) = 1 + 3 = 4
Example 2 — Larger Array
$ Input: nums = [6,2,6,5,1,2]
Output: 9
💡 Note: After sorting: [1,2,2,5,6,6]. Pairs: (1,2), (2,5), (6,6). Sum of minimums: 1 + 2 + 6 = 9
Example 3 — Minimum Size
$ Input: nums = [1,2]
Output: 1
💡 Note: Only one pair possible: (1,2). Sum of minimums: min(1,2) = 1

Constraints

  • 1 ≤ n ≤ 104
  • nums.length == 2 * n
  • -104 ≤ nums[i] ≤ 104

Visualization

Tap to expand
Array Partition ProblemInput Array1432SortAfter Sorting1234Pair (1,2)Pair (3,4)min = 1min = 3Result: 1 + 3 = 4
Understanding the Visualization
1
Input
Array of 2n integers that need to be paired
2
Process
Sort array and pair adjacent elements optimally
3
Output
Maximum possible sum of minimum values
Key Takeaway
🎯 Key Insight: Sort the array and pair adjacent elements to ensure no larger element is wasted as a minimum
Asked in
Amazon 25 Microsoft 18 Facebook 15 Google 12
125.0K Views
Medium Frequency
~10 min Avg. Time
2.8K Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen