Pattern visualizer
Split Array Largest Sum
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. 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..
Binary search the answer, not the array
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