Split Array Largest Sum

Problem Statement:

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split. A subarray is a contiguous part of the array.

Example 1:

Input: nums = [7,2,5,10,8], k = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], k = 2 Output: 9 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)

Solution:

If you take a close look, you would probably see how similar this problem is with Capacity To Ship Packages Within D Days. Similarly, we can design a feasible function: given an input threshold, then decide if we can split the array into several subarrays such that every subarray-sum $<=$ threshold. In this way, we discover the monotonicity of the problem: if feasible(m) is True, then all inputs larger than m can satisfy feasible function.

class Solution {
    private boolean feasible(int[] nums, int threshold, int k){
        int count = 1;
        int total = 0;
 
        for(int num: nums){
            total += num; // Add the current number to the total sum of the current subarray
            if(total > threshold){
                total = num; // Start a new subarray with the current number
                count++;
                
                // If the number of subarrays needed exceeds 'k', return false
                if(count > k){
                    return false;
                }
            }
        }
        // If the number of subarrays needed is within 'k', return true
        return true;
    }
 
    public int splitArray(int[] nums, int k) {
        int sum = 0;
        int maxNum = Integer.MIN_VALUE;
 
        for(int num: nums){
            maxNum = Math.max(maxNum, num);
            sum += num;
        }
 
        //Define search space
        int left = maxNum; // Minimum possible threshold (the largest single element)
        int right = sum; // Maximum possible threshold (the sum of all elements)
        
        while(left < right){
            int mid = left + (right - left)/2; //threshold
 
            if(feasible(nums, mid, k)){//if feasible, I'll decrease my threshold
                right = mid;
            } else{
                left = mid + 1;
            }
        }
 
        return left; // The minimum possible threshold where the array can be split into 'k' subarrays
    }
}

Note:

But we probably would have doubts: It’s true that left returned by our solution is the minimal value satisfying feasible, but how can we know that we can split the original array to actually get this subarray-sum? For example, let’s say nums = [7,2,5,10,8] and m = 2. We have 4 different ways to split the array to get 4 different largest subarray-sum correspondingly: 25:[[7], [2,5,10,8]], 23:[[7,2], [5,10,8]], 18:[[7,2,5], [10,8]], 24:[[7,2,5,10], [8]]. Only 4 values. But our search space [max(nums), sum(nums)] = [10, 32] has much more that just 4 values. That is, no matter how we split the input array, we cannot get most of the values in our search space.

Proof:

Let’s say k is the minimal value satisfying feasible function. We can prove the correctness of our solution with proof by contradiction. Assume that no subarray’s sum is equal to k, that is, every subarray sum is less than k. The variable total inside feasible function keeps track of the total weights of current load. If our assumption is correct, then total would always be less than k. As a result, feasible(k - 1) must be True, because total would at most be equal to k - 1 and would never trigger the if-clause if total > threshold, therefore feasible(k - 1) must have the same output as feasible(k), which is True. But we already know that k is the minimal value satisfying feasible function, so feasible(k - 1) has to be False, which is a contradiction. So our assumption is incorrect. Now we’ve proved that our algorithm is correct.