Solution: Split Array Largest Sum

Let’s solve the Split Array Largest Sum problem using the Modified Binary Search pattern.

We'll cover the following

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≤1\leq nums.length ≤103\leq 10^3

  • 0≤0\leq nums[i] ≤104\leq 10^4

  • 1≤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:

Press + to interact
canvasAnimation-image
1 of 20

Let’s look at the code for the algorithm we just discussed:

public class Solution {
  public boolean canSplit(int[] nums, int k, int mid) {
    int subarrays = 1;
    int currentSum = 0;
    for (int num : nums) {
      if (currentSum + num > mid) {
        subarrays += 1;
        currentSum = num;
        
        if (subarrays > k) {
          return false;
        }
      } else {
        currentSum += num;
      }
    }
    return true;
  }
  public int splitArray(int[] nums, int k) {
    int left = Integer.MIN_VALUE, right = 0;
    for (int num : nums) {
      left = Math.max(left, num);
      right += num;
    }
    while (left < right) {
      int mid = (left + right) / 2;
      if (canSplit(nums, k, mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    
    return left;
  }
  
  // Driver code
  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] splits = {
            {3, 4, 6, 3},
            {2, 7, 8, 9, 2, 1, 4},
            {12, 53, 43, 67, 35},
            {4, 6, 4, 6, 4, 6},
            {11, 11, 11, 11, 11}
    };
    int[] k = {3, 6, 5, 4, 2};
    for (int i = 0; i < splits.length; i++) {
      System.out.println((i + 1) + ".\tInput Array: " + java.util.Arrays.toString(splits[i]));
      System.out.println("\tk: " + k[i]);
      System.out.println("\tLargest minimized sum: " + solution.splitArray(splits[i], k[i]));
      System.out.println(new String(new char[100]).replace('\0', '-'));
    }
  }
}
Split Array Largest Sum

Time complexity

The time complexity of this solution is O(n log(m))O(n~log(m)), where nn is the length of the input array, and mm is the difference between max(nums) and sum(nums) because the range of possible sums considered during the binary search is from max(nums) to sum(nums). This range size determines the number of iterations in the binary search. The tighter this range, the fewer iterations are needed. However, in the worst case, it spans the full difference: sum(nums) - max(nums). The time complexity becomes n log(m)n~log(m) because the can_split function is called nn times for each iteration.

Space complexity

The time complexity of this solution is O(1)O(1) because only constant space is used.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.