< 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.