Split Array Largest Sum
Hard Binary search on the answer (book allocation)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Split the array into k non-empty contiguous parts so that the largest part's sum is as small as possible. Return that sum.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: cut the array into k parts so the biggest part sum is as small as possible ("book allocation").
Why this works: guess a limit; greedily count how many parts you need. Fewer parts than k is fine. Binary search the smallest workable limit.
Example: [7, 2, 5, 10, 8], k = 2
limit 18: [7,2,5] [10,8] → 2 parts ✓limit 17: [7,2,5] [10] [8] → 3 parts ✗ → answer 18
✦Hints open one at a time
↗Approach
This is "book allocation". Binary search L in [max element, total]. If greedy needs at most k parts, L is feasible — search lower.
</>Solution (Java)
class Solution {
public int splitArray(int[] nums, int k) {
long lo = 0, hi = 0;
for (int x : nums) {
lo = Math.max(lo, x);
hi += x;
}
while (lo < hi) {
long mid = (lo + hi) / 2;
if (parts(nums, mid) <= k) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}
private int parts(int[] nums, long limit) {
int parts = 1;
long sum = 0;
for (int x : nums) {
if (sum + x > limit) { // start a new part
parts++;
sum = 0;
}
sum += x;
}
return parts;
}
}!Common mistake
Thinking "at most k parts" is a problem — if fewer parts fit, you can always split further without increasing the max.
- Time: O(n log(sum)).
- Space: O(1).