This problem asks us to split the array into K
contiguous subarrays in such a way that the largest sum among these subarrays is as small as possible.
Understanding the Goal
We're not just trying to split the array randomly. We need to find a split where the heaviest load (the subarray with the highest sum) is minimized. Imagine splitting tasks across K workers, and you want to minimize the maximum load any one worker handles.
What Are We Really Searching For?
The answer is somewhere between:
- The largest single element in the array (because no subarray can be smaller than this)
- And the total sum of the array (if we don’t split it at all)
So, we’re trying to find the minimum possible value of the largest subarray sum — such that we can split the array into exactly K subarrays without any subarray exceeding that sum.
How We Approach It
We use binary search on the answer space. Instead of iterating through all ways to split (which is slow), we guess a value and check if it's possible to split the array using that as the maximum allowed subarray sum. Based on whether it's possible or not, we adjust our guess (just like binary search).
What Happens in Different Cases?
- If the array is empty, we return 0 since there’s nothing to split.
- If K is 0, we cannot make any valid partitions, so again return 0.
- If K ≥ array length, the best case is to assign each number to its own subarray — so the largest element in the array becomes the answer.
- If K = 1, we have to take the whole array as one subarray, so the total sum is the answer.
- Normal case: We keep checking possible max sums using binary search, and count how many subarrays we need if we restrict the max sum to our current guess. If we need ≤ K subarrays, we try a smaller sum. If we need more than K, we increase the sum.
This method gives us the smallest possible largest subarray sum that still allows splitting the array into exactly K subarrays.
Why Binary Search Works
We’re using binary search over a range of answers — the range between the largest element and the sum of all elements. We're not searching inside the array but rather searching through all possible values the final answer can take. It’s efficient and brings the complexity down to O(n log(sum)).