Leetcode 410. Split Array Largest Sum

Problem

Leetcode 410 - Split Array Largest Sum

Example:

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.

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.

Approach

We can solve this problem similar to Leetcode 875 using Binary Search where left pointer starts at max(nums), and right pointer with sum(nums).

We are then going to use a helper function to take the sum of the subarray then counting subarray to achieve mid, if we do we update result and right pointer, else we update left pointer.

Visualization of the Approach:

nums = [1,2,3,4,5], k = 2
left = 5, right = 15
mid = 10
Check how many subarray we can make
subarray_1 = [1,2,3,4]
subarray_2 = [5]
We can make 2 subarrays thus update res and right ponter
res = 10

left = 5, right = 9
mid = 7
Check how many subarray we can make
subarray_1 = [1,2,3]
subarray_2 = [4]
subarray_3 = [5]
Since we have more subarrays update left

left = 8, right = 9
mid = 8
Check how many subarray we can make
subarray_1 = [1,2,3]
subarray_2 = [4]
subarray_3 = [5]
Since we have more subararys update left

left = 9, right = 9
mid = 9
Check how many subarray we can make
subarray_1 = [1,2,3]
subarray_2 = [4,5]
We can make 2 subarrays thus update res and right ponter
res = 9

Thus return 9

Here is the Python code for the solution:

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        
        # helper function to check how many subarray we can have
        def canSplit(largest):
            subarr_count = 0
            currSum = 0

            for n in nums:
                curr += n
                if curr > largest:
                    subarr_count += 1
                    currSum = n
            
            return subarr_count + 1 <= k

        left, right = max(nums), sum(nums)
        res = right

        while left <= right:
            mid = (left+right) // 2

            if canSplit(mid):
                res = mid
                right = mid-1
            else:
                left = mid+1
        
        return res
    

Time Complexity and Space Complexity

Time Complexity: $O(n log s)$ where $n$ is the size of nums and $s$ is the sum of all elements in the array

Space Complexity: $O(1)$