Split Array Largest Sum - Leetcode Solution

The Split Array Largest Sum problem on LeetCode asks you to divide an array of integers into m subarrays such that the maximum sum of any subarray is minimized.

For example, given the array [7,2,5,10,8] and m = 2, the optimal solution would be to split the array into [7,2,5] and [10,8], resulting in a maximum subarray sum of 12.

This problem can be solved using binary search. The range of possible answers is from the maximum value in the array (meaning each subarray only consists of one element) to the sum of all values in the array (meaning there is only one subarray). We can use binary search to find the smallest value within this range that satisfies the given conditions.

To do so, we can first calculate the middle value of the range. We then try to split the array into m subarrays such that each subarray has a sum less than or equal to the middle value. If we successfully split the array into m subarrays and each subarray has a sum less than or equal to the middle value, we can narrow the search range to the lower half of the range. If we cannot successfully split the array into m subarrays with sums less than or equal to the middle value, we need to increase the middle value and try again.

As an illustration, let's look at the previous example: given the array [7,2,5,10,8] and m = 2, the range of possible answers is from the maximum value in the array (10) to the sum of all values in the array (32). We first calculate the middle value, which is (10+32)/2 = 21. We then try to split the array into 2 subarrays such that each subarray has a sum less than or equal to 21. One possible split is [7,2,5] and [10,8], resulting in subarray sums of 14 and 18, respectively. Since both subarrays have sums less than or equal to 21, we can narrow the search range to the lower half of the range (since we are looking for the smallest value that satisfies the conditions). We can repeat this process until we find the optimal solution.

Here is the Python code that implements the above algorithm:

def splitArray(nums, m):
    # calculate the range of possible answers
    left = max(nums)
    right = sum(nums)
    
    # helper function to check if a middle value is valid
    def is_valid(mid):
        count, total = 1, 0
        for num in nums:
            total += num
            if total > mid:
                count += 1
                total = num
                if count > m:
                    return False
        return True
    
    # binary search to find the optimal solution
    while left < right:
        mid = left + (right - left) // 2
        if is_valid(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

The time complexity of this solution is O(n*log(sum(nums))), where n is the length of the array and sum(nums) is the sum of all values in the array. The space complexity is O(1).

1