BS on Answer — Split Array Largest Sum
↗ LeetCode: Split Array Largest Sum · Hard · pattern chapter →
Asked atMetaGoogleAmazonBloomberg
Split nums into m non-empty contiguous subarrays to minimize the largest sum among the subarrays. Return that min largest sum.
Example — nums=[7,2,5,10,8], m=2 → 18
Constraints — 1 ≤ m ≤ n ≤ 1000; 0 ≤ nums[i] ≤ 10⁶.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Interval DP
dp[i][k] = min largest sum for nums[0..i-1] split into k parts. O(n²·m).
Approach 2 — Binary search on the answer
Insight. feasible(cap) = can we split into ≤ m parts each with sum ≤ cap? Monotonic. Range: lo = max(nums), hi = sum(nums).
java
int splitArray(int[] nums, int m) {
int lo = 0, hi = 0;
for (int x : nums) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int parts = 1, sum = 0;
for (int x : nums) {
if (sum + x > mid) { parts++; sum = 0; }
sum += x;
}
if (parts <= m) hi = mid;
else lo = mid + 1;
}
return lo;
}Execution Trace
Step 1 / 5cap 21 → 2 parts ≤ 2 → hi=21
Complexity — Time O(n log sum); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Interval DP | O(n²·m) | O(n·m) |
| BS on answer | O(n log sum) | O(1) |
When to use which
- "Min largest chunk after splitting" → BS on answer.
- DP alternative → interval DP; slower but returns actual partition.
- Related: max smallest chunk → similar BS with
≥predicate.
AI Study CompanionBeta
Related problems
- Capacity To Ship Packages — same skeleton
- Divide Chocolate — maximize the minimum
- Koko Eating Bananas
Was this page helpful?
📚 Related problems