410. Split Array Largest Sum

This page provides solutions for the leetcode problem 410. Split Array Largest Sum.

Problem Explanation

The problem is asking us to split an array into $\text{K}$ subarrays in such a way that the largest sum of any subarray is minimized.

Solution

This problem can be solved using the Binary Search technique. More such questions can be found here.

Java

class Solution {
  public int splitArray(int[] nums, int k) {
    int lo = Integer.MIN_VALUE;
    int hi = 0;

    for(int num: nums) {
      lo = Math.max(lo, num); 
      hi += num; 
    }

    while(lo < hi) {
      int mid = lo + (hi - lo) / 2; 
      int partitions = getPartitions(nums, mid); 
      if (partitions > k) lo = mid + 1; 
      else hi = mid; 
    }
    return lo; 
  }

  private int getPartitions(int[] nums, int required) {
    int index = 0, sum = 0, partition = 1;
    while(index < nums.length) {
      sum += nums[index]; 
      if (sum > required) {
        sum = nums[index]; 
        partition++; 
      }
      index++;
    }
    return partition;
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array, and total sum of all elements in an array is $\text{S}$.

Time Complexity

The time complexity is $\text{O}(\log \text{S})$ for searching the optimal solution using binary search, and $\text{O}(\text{N})$ for checking if the array can be split into $\text{K}$ subarrays., so total time complexity will be:

$$\text{O}(\text{N} \log \text{S})$$

Space Complexity

The solution uses constant space for storing binary search variables, so space complexity will be:

$$\text{O}(1)$$