Split Array Largest Sum
Split an array into k pieces so the largest piece sum is as small as possible: binary search on that sum, with a greedy count of pieces for each try.
Problem Understanding
Split Array Largest Sum: split nums into k non-empty contiguous pieces so that the largest piece sum is as small as possible, and return that sum.
Examples: nums = [7,2,5,10,8], k = 2 returns 18 ([7,2,5] and [10,8]); nums = [1,2,3,4,5], k = 2 returns 9.
The Intuition: Guess the Answer, Then Check It
Trying every way to cut is expensive. Turn the question around: given a cap, can the array be cut into at most k pieces with no sum over it?
- Checking a cap is easy: walk left to right and start a new piece only when the next number would go over. That greedy cut uses the fewest pieces possible.
- The answer is monotonic: if a cap works, every larger cap works too.
- So binary search the cap between
max(nums)andsum(nums), keeping the smallest one that works.
This is binary search on the answer, the same move as Koko Eating Bananas, where the guess is an eating speed instead of a sum.
Interactive Walkthrough
k = 2 PIECES
RANGE [MAX, SUM]
0
1
2
3
4
lo
10
hi
32
cap
:
pieces
:
answer
:
The cap is at least the largest number (10) and at most the whole sum (32). Search [10, 32]
Next
Try cap = 21: cut whenever the next number would go over. Pieces: 14, 18, so 2 pieces
nums
k
Each step cuts the array greedily at the cap being tried; the pieces sit apart with their sums (Σ) underneath. When the cut needs more than k pieces, the extra ones are solid. Try k = 1 to see every cap below the total fail.
Dry Run Table
Input: nums = [7,2,5,10,8], k = 2. Range: [10, 32].
| lo | hi | cap (mid) | Greedy pieces | Count | Move |
|---|---|---|---|---|---|
| 10 | 32 | 21 | [7,2,5] [10,8] | 2 | hi = 21 |
| 10 | 21 | 15 | [7,2,5] [10] [8] | 3 | lo = 16 |
| 16 | 21 | 18 | [7,2,5] [10,8] | 2 | hi = 18 |
| 16 | 18 | 17 | [7,2,5] [10] [8] | 3 | lo = 18 |
Answer: lo = hi = 18.
The Solution Template
A greedy piece counter plus a lower-bound binary search: hi = mid keeps a cap that works, lo = mid + 1 drops one that does not.
Split Array Largest Sum Code
1var splitArray = function(nums, k) {2 const pieces = (cap) => {3 let count = 1, cur = 0;4 for (const x of nums) {5 if (cur + x > cap) { count++; cur = 0; }6 cur += x;7 }8 return count;9 };10 let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);11 while (lo < hi) {12 const mid = Math.floor((lo + hi) / 2);13 if (pieces(mid) <= k) hi = mid;14 else lo = mid + 1;15 }16 return lo;17};
Edge Cases & Common Mistakes
- k = 1: the answer is the whole sum.
- k = n: every number alone; the answer is
max(nums). - Starting lo at 0 or 1: a cap below
max(nums)can never hold the largest number, yet the greedy counter still returns a count (for[10], k = 1it says 1 piece at cap 0), so the search would return a wrong answer. Start atmax(nums). - Fewer than k pieces: fine. A cut with fewer pieces can always be split further without raising the largest sum.
- Overflow: the sum can reach 10⁹ under LeetCode's limits; it fits in 32 bits, but use 64-bit if the limits are larger.
Summary
Binary search the cap between max(nums) and sum(nums). For each cap, cut greedily and count pieces: at most k means hi = mid, more means lo = mid + 1. Return lo. O(n log S) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet