410. Split Array Largest Sum

Problem

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. (link)

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<sup>6</sup>

• 1 <= k <= min(50, nums.length)

Solution

Brute Force Approach

This is exactly the same as the book allocation problem(link). So basically, we approach this problem in the opposite way: we find out how many splits will be required for a given maximum sum of subarray. We start from the minimum subarray sum and incrementally increase it until reaching the maximum possible sum. For each sum, we calculate the number of subarray splits. We check if the number of splits is less than or equal to 𝑘k, then we return the answer.

Why calculate splits ≤ k?

Consider the following example: the answer is 3. But if we keep the maximum sum of each subarray as 3, it means [2], [3], [1,1,1],[1] will get 4 splits with the threshold. However, if we are careful, we can arrange it in such a way that we can get one more subarray by pulling out elements from other subarrays, i.e., [2], [3], [1,1],[1],[1].

The initial value of the answer can be the maximum value present in the subarray because if we want to create a single-element subarray, then it should have the capacity to hold the maximum value. Similarly, the end value of the answer is the total sum, which is only 1 split.

nums = [2,3,1,1,1,1,1]
k = 5

Answer: 3

Time - O(sum-max)*O(n)

Space - O(1)

sum = Total sum of array; max = Max element of the array , n=length of array

class Solution {
    public int getSplitsNo(int[] nums, int maxSum){
        int sum = 0;
        int noOfSplits = 1;
        for(int num : nums){
            if(sum+num<=maxSum){
                sum+=num;
            }
            else{
                noOfSplits += 1;
                sum = num;
            }
        }

        return noOfSplits;
    }

    public int splitArray(int[] nums, int k) {
        int min = Arrays.stream(nums).max().getAsInt();
        int max = Arrays.stream(nums).sum();

        for(int largestSum=min; largestSum<=max; largestSum++){
            if(getSplitsNo(nums, largestSum)<=k){
                return largestSum;
            }
        }
        return -1;
    }
}

Optimal Approach - Binary Search

Apply binary search on top of the brute force approach.

Time - O(sum-max) * O(logn)

space - O(1)

sum = Total sum of array; max = Max element of the array , n=length of array

class Solution {
    public int getSplitsNo(int[] nums, int maxSum){
        int sum = 0;
        int noOfSplits = 1;
        for(int num : nums){
            if(sum+num<=maxSum){
                sum+=num;
            }
            else{
                noOfSplits += 1;
                sum = num;
            }
        }
        return noOfSplits;
    }

    public int splitArray(int[] nums, int k) {
        int min = Arrays.stream(nums).max().getAsInt();
        int max = Arrays.stream(nums).sum();

        int low = min;
        int high = max;

        while(low<=high){
            int mid = (low+high)/2;

            if(getSplitsNo(nums,mid) > k){
                low = mid +1;
            }
            else{
                high = mid - 1;
            }
        }
        return low;
    }
}