< Back




410. Split Array Largest Sum

We're given an array of numbers and asked to split them into k subarrays such that the subarray with
the maximum sum is minimized. Basically, we're guessing what the maximum subarray's sum will be while
being able to split the nums array into the required number of subarrays.

Using binary search, we set the left and right pointers to the maximum num in nums and the sum of
nums, respectively. During each step of the binary search, we calculate m, the maximum sum of the
largest subarray in our guessed split. We iterate through the nums array, adding each number to a
running tally if that running tally doesn't exceed the guessed maximum sum, m. If it does, we reset
our tally and increment the number of splits, c, by 1.

If the number of subarrays, c + 1, is greater than the requested number of subarrays, k, we know that
we guessed too low of the maximum sum of the subarray in a possible split. Therefore, we set the left
pointer to m + 1, decreasing the search space. In the other case, we've set the guess too high or
just right, to where the number of subarrays, c + 1, is less than or equal to k. In this case, we
lower the limit for our guesses, setting the right pointer to m - 1. We also record the maximum for
this guess as our answer.

Eventually, the left and right pointers will converge, and we'll m, the guess, as our answer.

The solution is as follows:


  class Solution:
      def splitArray(self, nums: List[int], k: int) -> int:
          l, r, ans = max(nums), sum(nums), -1

          while l <= r:
              m, t, c = (r + l) // 2, 0, 0

              for num in nums:
                  if t + num <= m:
                      t += num
                  else:
                      t = num
                      c += 1

              if c + 1 > k:
                  l = m + 1
              else:
                  r = m - 1
                  ans = m

          return ans


_ Time Complexity:

  O(n log(s)) - Where s is the sum of the nums array and n is the length of the nums array.

_ Space Complexity:

  O(1) - We use constant space to retain our variables.