Solution: Split Array Largest Sum

Statement

Given an integer list nums and an integer k, split nums into k non-empty subarrays such that the largest sum among these subarrays is minimized. The task is to find the minimized largest sum by choosing the split such that the largest sum of every split of subarrays is the minimum among the sum of other splits.

Constraints:

• $1\leq$ nums.length $\leq 10^3$

• $0\leq$ nums[i] $\leq 10^4$

• $1\leq$ k $\leq$ nums.length

Solution

In a brute force method, you would try all possible ways to split the array into k subarrays, calculate the largest sum for each split, and then find the smallest among those largest sums. This approach is extremely inefficient because the number of ways to split the array grows exponentially as the size increases.

We reverse the process by guessing a value for the minimum largest sum and checking if it’s feasible:

• Instead of iterating through all splits, we only focus on testing whether a specific value allows us to split the array into k subarrays.

• But wait—just because one value works doesn’t mean it’s the smallest feasible value. We keep exploring smaller values to achieve the most optimized result.

The solution uses the binary search approach to find the optimal largest subarray sum without testing all possible splits. The binary search finds the smallest possible value of the largest subarray sum and applies searching over the range of possible values for this largest sum. But how do we guess this value? We guess the value using a certain range. Here’s how:

• Left boundary: The maximum element in the array is the minimum possible value for the largest subarray sum. This is because any valid subarray must have a sum at least as large as the largest element.

• Right boundary: The maximum possible value for the largest subarray sum is the sum of all elements in the array. You would get this sum if the entire array were one single subarray.

The binary search iteratively tests midpoints in the above ranges. It determines whether dividing the array results in at most k subarrays will result in the smallest largest sum. If it does, the search shifts to lower values to minimize the largest sum. Otherwise, it shifts to higher values. Still, there might be subarrays whose sum could be smaller, so the search keeps going until the search range crosses each other, i.e., left boundary > right boundary.

Here’s the step-by-step implementation of the solution:

• Start by initializing the ranges for search. The left will be the largest number in the array, and the right will be the sum of all numbers.

• Use a guessing approach. Start by considering a mid value between the left and right as a test value.

• Check if it is possible to divide the array into k subarrays so that the sum of no subarray is greater than mid.

  • Start with an empty sum and add numbers from the array. If adding the next number exceeds mid:

    • Start a new subarray with that number and increment the count of the subarrays.

  • Return FALSE if the count exceeds k. Otherwise, return TRUE.

• Adjust the guessing range by checking if the number of subarrays needed is within the k and reduce the mid to see if a smaller largest sum is possible.

• Otherwise, if the count of subarrays is more than k:

  • Increase the mid to make larger groups possible.

• Continue adjusting the mid until left < right. Return left as it contains the minimized largest possible sum.

Let’s look at the following illustration to get a better understanding of the solution: