Minimum Difference Among Groups of Size Two asks you to split numbers into pairs so the pair sums stay as close together as possible. It is a clean lesson in greedy pairing: the right matching is obvious once you sort.
Problem. Given an even-length array of integers nums, split it into pairs (each number used
exactly once). Form each pair and add its two numbers. Minimize the spread — the difference between
the largest pair sum and the smallest pair sum. Return that minimum spread.
Example: nums = [1, 3, 4, 7] → pair (1, 7) and (3, 4) → sums 8 and 7 → spread 8 − 7 = 1.
The slow way first
The brute-force idea: try every way to partition the array into pairs, compute the spread of each, and keep the best. The number of pairings explodes factorially — for 2k numbers there are (2k − 1)!! of them. Even a small array becomes hopeless. We need to know the one pairing that is best without enumerating them all.
The question to ask: what makes one pairing better than another? A pairing is good when all the pair sums are close to each other — ideally all equal to the average. So we want to avoid leaving a huge number paired with another huge number.
The idea: pair smallest with largest
Sort the array. Then pair the i-th smallest with the i-th largest: first with last, second with second-to-last, and so on. The biggest number gets dragged down by the smallest, the second-biggest by the second-smallest. Every pair sum lands near the middle, so the sums cluster tightly and the spread is minimized.
Why is this optimal? If you instead paired two large numbers together, their sum would shoot up while some other pair (two small numbers) would sink — widening the spread. Matching extremes against each other is the unique way to keep every sum near the average.
Walk through it
Step through the animation. After sorting, pointer i starts at the left and j at the right. We pair 1 + 7 = 8, lock it with an arc, then move both pointers inward and pair 3 + 4 = 7. The two sums are 8 and 7, so the spread is just 1.
Pseudocode
sort nums ascending
sums = empty list
i = 0, j = last index
while i < j:
sums.append(nums[i] + nums[j]) # pair the ends
i = i + 1
j = j - 1
return max(sums) - min(sums) # the spreadThe Python solution
def min_difference(nums):
nums.sort()
sums = []
i, j = 0, len(nums) - 1
while i < j:
sums.append(nums[i] + nums[j])
i += 1
j -= 1
return max(sums) - min(sums)nums.sort()is the whole trick — once sorted, the optimal partner of each end is the opposite end.iandjare two pointers that start at the extremes and walk toward each other.- Line 6 forms one pair sum by adding the current smallest and current largest values.
- Each iteration consumes one number from each end, so the loop pairs everything in
n / 2steps. max(sums) - min(sums)is the spread we were asked to minimize.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (all pairings) | O((n−1)!!) (moderate) | factorial blow-up |
| Sort + two pointers | O(n log n) (moderate) | sort dominates the linear pairing |
O(n) (moderate)The sort costs O(n log n); the pairing pass is O(n). We store the pair sums in O(n) space (or O(1) if you track the running max and min instead of a list).
When this pattern shows up
When a problem asks you to pair, match, or split into groups to minimize a spread or maximize a balance, try sorting first and then pairing extremes against each other. Sorting turns a factorial search into an obvious greedy choice.
This extremes-together rule minimizes the spread of pair sums. If a problem instead asked to minimize the largest pair sum, the same sorted-ends pairing still wins — but if it asked to make sums as unequal as possible, you would pair adjacent elements instead. Always confirm which quantity the problem optimizes.
Practice
For nums = [1, 3, 4, 7], after sorting, which two values does the greedy rule pair first, and what is their sum?
1. After sorting, which two elements does the greedy rule pair together first?
2. Why does pairing extremes minimize the spread of pair sums?
3. What dominates the running time of this solution?
4. For nums = [1, 3, 4, 7], what is the minimum spread?