Partition Array into Sizes K and N-K asks you to cut an array into two groups — one of size k, the other of size n - k — so the two group sums are as close as possible. It is a clean example of a greedy insight: once you sort, the best split lives among contiguous blocks of the sorted order.
Problem. Given an array nums of n integers and an integer k, split the elements into a group
of size k and a group of size n - k. Return the minimum possible absolute difference between
the two group sums.
Example: nums = [1, 3, 4, 6], k = 2 → answer 0 (split into {3, 4} = 7 and {1, 6} = 7).
The slow way first
The obvious idea: try every way to choose k elements for group A, sum each side, and keep the smallest difference. There are C(n, k) such choices — combinatorial, which blows up fast. For even a modest array that is far too slow.
The question to ask: is there structure that lets me avoid trying every subset? The total sum is fixed, so if group A sums to a, group B sums to total - a, and the difference is |total - 2a|. So we only need to steer one group sum a as close to total / 2 as we can.
The idea: sort, then slide a window
Sort the array. Now the k elements that give a sum nearest the target are a contiguous block of the sorted order. We slide a size-k window across the sorted values, keeping a running sum, and record the window whose sum lands closest to total / 2.
Because diff = |total - 2a|, every window gives a candidate difference in O(1). Sliding the window is O(1) per step too — add the entering element, subtract the leaving one.
Walk through it
Step through the animation. After sorting we get [1, 3, 4, 6] with total 14, so the target per group is 7. The size-2 window starts on {1, 3} (diff 6), slides to {1, 4} (diff 4), and reaches {3, 4} = 7, where the difference drops to 0 — the best possible.
Pseudocode
sort nums
total = sum(nums)
a = sum of the first k elements # window sum
best = |total - 2*a|
for i from k to n-1:
a += nums[i] - nums[i-k] # slide window right
best = min(best, |total - 2*a|)
return bestThe Python solution
def min_diff(nums, k):
nums.sort()
total = sum(nums)
target = total / 2
a = sum(nums[:k])
best = abs(total - 2 * a)
for i in range(k, len(nums)):
a += nums[i] - nums[i - k]
diff = abs(total - 2 * a)
best = min(best, diff)
return bestnums.sort()puts values in order so the best group is a contiguous block.totalis fixed;target = total / 2is what each group wants to sum to.a = sum(nums[:k])seeds the window on theksmallest values.best = abs(total - 2 * a)is the difference for that first window — since group B istotal - a, the gap is|total - 2a|.- The loop slides the window:
a += nums[i] - nums[i - k]adds the entering element and drops the one falling off the left. - We recompute
diffeach slide and keep the running minimum.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (every subset) | O(C(n, k)) (moderate) | try all choices of k elements |
| Sort + slide (this solution) | O(n log n) (moderate) | sort dominates; the slide is O(n) |
O(1) (fast)Sorting is the only expensive part. The window slide and the running-minimum are both O(n) overall and use O(1) extra space.
When this pattern shows up
When a problem fixes a total and asks you to balance two parts, rewrite the objective in terms of a
single quantity — here diff = |total - 2a|. Once one variable controls the answer, sorting plus a
sliding window often turns an exponential search into O(n log n).
The contiguous-window shortcut relies on choosing the group by size from a sorted array. If the two groups had extra constraints (forbidden pairings, fixed positions), the greedy block would no longer be safe and you would need a different approach.
Practice
For nums = [1, 3, 4, 6], k = 2, total is 14 so the target per group is 7. Which size-2 window hits the target exactly?
1. Why can we express the difference as |total - 2a| where a is one group sum?
2. Why do we sort the array first?
3. What does the line a += nums[i] - nums[i - k] do?
4. What dominates the time complexity?