Array Partition: Greedy Pairing After Sorting
LeetCode #561, Array Partition, asks you to pair up 2n integers so that the sum of the smaller element from each pair is as large as possible. The greedy strategy is to sort and pair adjacent elements. Once you see why this works, the code is just two lines.
The problem
Given an integer array nums of 2n integers, group them into n pairs such that the sum of min(ai, bi) for all pairs is maximized. Return that maximum sum.
nums = [1, 4, 3, 2] -> 4 (pairs: (1,2), (3,4), sum of mins = 1 + 3)
nums = [6, 2, 6, 5, 1, 2] -> 9 (sorted: [1,2,2,5,6,6], sum of even indices = 1+2+6)
The approach
The key question is: why does sorting and pairing adjacent elements give the best result?
Think about what happens when you pair a very small number with a very large one. Say you pair 1 with 4. The minimum is 1, and the 4 is completely "wasted." It contributes nothing to your sum. Now compare that with pairing 1 with 2 and 3 with 4. The minimums are 1 and 3, giving a sum of 4. By keeping close-valued numbers together, you minimize the gap between paired elements, which means less waste.
The greedy argument in one sentence: sorting minimizes the total difference within each pair, which maximizes the sum of minimums. Any swap that pairs a small number with a larger one (skipping over a closer match) can only decrease or maintain the total, never increase it.
More formally, suppose the sorted array is a[0], a[1], ..., a[2n-1]. Adjacent pairing gives pairs (a[0], a[1]), (a[2], a[3]), ... with minimums a[0], a[2], a[4], .... If you tried a different pairing that crosses over adjacent elements, the minimum of at least one pair would drop compared to the adjacent pairing, and no other pair's minimum could increase enough to compensate. This is the classic exchange argument for greedy correctness.
The solution
def arrayPairSum(nums):
nums.sort()
return sum(nums[::2])
Sort the array, then sum every other element starting from index 0. The slice nums[::2] picks out indices 0, 2, 4, and so on. These are the even-indexed elements, which are the smaller value in each adjacent pair.
In languages without Python's slice syntax, you can loop and accumulate:
def arrayPairSum(nums):
nums.sort()
total = 0
for i in range(0, len(nums), 2):
total += nums[i]
return total
Step-by-step walkthrough
Step 1: Start with the unsorted array.
We have 2n = 4 integers. We need to form n = 2 pairs that maximize the sum of minimums.
Step 2: Sort the array in ascending order.
After sorting: [1, 2, 3, 4]. Sorting lets us pair adjacent elements to minimize waste.
Step 3: Pair adjacent elements: (1,2) and (3,4).
Adjacent pairing keeps close-valued numbers together. The difference within each pair is just 1, so the waste is minimal.
Step 4: Take the minimum of each pair.
The even-indexed elements (indices 0 and 2) are the smaller value in each pair. These are the values we sum.
Step 5: Sum the minimums to get the answer.
The maximum possible sum of minimums is 4. No other pairing can do better. For example, pairing (1,3) and (2,4) gives 1 + 2 = 3.
The walkthrough confirms the pattern: sort, pair neighbors, and sum the even-indexed elements. The waste in each pair is exactly a[1] - a[0] and a[3] - a[2], which is minimized when elements are close together.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Try all pairings | O((2n)! / (2^n * n!)) | O(n) |
| Sort + sum even indices | O(n log n) | O(1) (in-place sort) |
Time: O(n log n). Dominated by the sort. The summation is O(n).
Space: O(1) if sorting in place, O(n) if using a sort that requires extra space.
The building blocks
Greedy after sorting
Many greedy problems follow the same template: sort the input, then make a single pass with a simple rule. Sorting transforms a seemingly complex optimization problem into one where the greedy choice is obvious. You will see this pattern in interval scheduling, activity selection, and task assignment problems. The hard part is usually proving correctness via an exchange argument, but once you have seen a few examples, the reasoning becomes familiar.
nums.sort()
result = 0
for i in range(0, len(nums), 2):
result += nums[i]
This "sort then scan" template is a building block worth memorizing. The specifics of the scan vary per problem, but the structure is always the same: sort first, then extract the answer in a single pass.
Edge cases
- Two elements: Only one pair, return the minimum of the two values.
- All equal elements: Every pairing gives the same result, so sorting and summing even indices still works.
- Negative numbers: Sorting still works. Pair the most negative together to minimize waste. For example,
[-5, -4, -3, -2]sorted gives pairs(-5,-4)and(-3,-2), with sum-5 + -3 = -8. - Already sorted input: Works directly with no wasted work beyond the sort itself.
From understanding to recall
Sorting-based greedy problems all feel obvious after you read the solution. The challenge is reproducing the logic under pressure. Can you remember to sort first? Can you recall that you want even indices, not odd? Can you articulate the exchange argument when the interviewer asks "why does this work?"
Spaced repetition locks in both the code and the reasoning. You practice writing the two-line solution from scratch, and you practice explaining the greedy argument in your own words. After a few cycles, the pattern fires automatically whenever you see "maximize the sum of minimums" or "pair elements optimally."
Related posts
- Contains Duplicate - Another problem where sorting reveals structure
- Merge Intervals - Classic sort-first greedy approach
- Assign Cookies - Greedy pairing with sorted arrays
The sort-then-greedy pattern covers a surprisingly large family of problems. Learning to recognize it is one of the highest-leverage skills you can build for interviews. CodeBricks breaks it down into a drillable building block so you can practice the pattern in isolation, then recognize it instantly in new contexts.