Split Array Largest Sum
Binary search the answer, not the array
The array is unsorted and stays unsorted — there is nothing to binary search inside it. What IS searchable is the answer: a candidate cap on how large any single piece may be. That cap is monotonic. If 3 pieces can each stay under 21, they can certainly stay under 22; if 16 is impossible, 15 is hopeless too. So the range [max(nums), sum(nums)] splits cleanly into a run of impossible caps followed by a run of possible ones, and each guess throws away half of it. The 'is this cap possible?' question is answered greedily: keep piling numbers into the current piece until the next one would break the cap, then cut. That packing uses the fewest pieces any split can, so if it needs more than k, no arrangement will do.
Details
Animated on: nums = [7,2,5,10,8,3,6,12], k = 3. Cut the array into 3 consecutive pieces so that the piece with the biggest sum is as small as possible.
Problem:Split Array Largest SumHard
Pattern:Binary Search on Answer
Binary search the answer, not the array
step 1 / 8
8 numbers to cut into 3 consecutive pieces, minimising the LARGEST piece. That answer sits somewhere in [12, 53]: it can never drop below 12 because the single value 12 has to land in some piece, and never exceed 53 because one piece holding everything sums to that. Binary search the answer itself, not the array.
1FUNCTION splitArray(nums, k)2 low <- MAX(nums)3 high <- SUM(nums)4 WHILE low <= high5 mid <- FLOOR((low + high) / 2)6 need <- PIECES_NEEDED(nums, mid)7 IF need <= k8 best <- mid9 high <- mid - 110 ELSE11 low <- mid + 112 RETURN best
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- 8 numbers to cut into 3 consecutive pieces, minimising the LARGEST piece. That answer sits somewhere in [12, 53]: it can never drop below 12 because the single value 12 has to land in some piece, and never exceed 53 because one piece holding everything sums to that. Binary search the answer itself, not the array.
- Cap 32: filling each piece to the brim gives [7,2,5,10,8]=32 | [3,6,12]=21 — only 2 piece(s), which fits inside 3. So a largest-sum of 32 is reachable; remember it and pull the ceiling down to 31, because a tighter cap might still work.
- Cap 21: filling each piece to the brim gives [7,2,5]=14 | [10,8,3]=21 | [6,12]=18 — only 3 piece(s), which fits inside 3. So a largest-sum of 21 is reachable; remember it and pull the ceiling down to 20, because a tighter cap might still work.
- Cap 16: even the greediest packing spills into 5 pieces — [7,2,5]=14 | [10]=10 | [8,3]=11 | [6]=6 | [12]=12 — and only 3 are allowed. Greedy already uses the fewest pieces any split can, so no arrangement survives this cap. Everything at or below 16 is dead; raise the floor to 17.
- Cap 18: even the greediest packing spills into 4 pieces — [7,2,5]=14 | [10,8]=18 | [3,6]=9 | [12]=12 — and only 3 are allowed. Greedy already uses the fewest pieces any split can, so no arrangement survives this cap. Everything at or below 18 is dead; raise the floor to 19.
- Cap 19: even the greediest packing spills into 4 pieces — [7,2,5]=14 | [10,8]=18 | [3,6]=9 | [12]=12 — and only 3 are allowed. Greedy already uses the fewest pieces any split can, so no arrangement survives this cap. Everything at or below 19 is dead; raise the floor to 20.
- Cap 20: even the greediest packing spills into 4 pieces — [7,2,5]=14 | [10,8]=18 | [3,6]=9 | [12]=12 — and only 3 are allowed. Greedy already uses the fewest pieces any split can, so no arrangement survives this cap. Everything at or below 20 is dead; raise the floor to 21.
- low crossed high, so 21 is the smallest cap that still fits in 3 pieces: [7,2,5]=14 | [10,8,3]=21 | [6,12]=18, largest 21. The cap one lower, 20, was tested above and needed an extra piece — that is what makes 21 the answer and not merely a valid split.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.