LeetCode Solutions Blog

Split Array Largest Sum

Number: 410

Difficulty: Hard

Paid? No

Problem Description

Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays such that the largest sum among these subarrays is minimized.

Key Insights

Use binary search over the answer: the candidate value is the maximum subarray sum.
The lower bound of the search is max(nums) and the upper bound is sum(nums).
A greedy approach is used to check if a candidate maximum sum allows splitting nums into at most k subarrays.
Adjust the binary search bounds based on the feasibility check.

Space and Time Complexity

Time Complexity: O(n * log(sum(nums))) – n elements are processed for each binary search iteration. Space Complexity: O(1) – Constant extra space is used.

Solution

The solution employs binary search to determine the smallest maximum subarray sum possible. We set the initial lower bound to the maximum element and the upper bound to the total sum of the array. For each candidate value (mid), we check if the array can be split into k or fewer subarrays without any subarray sum exceeding mid using a greedy approach. If possible, we try to lower the candidate; if not, we increase the candidate. This continues until the optimal solution is found.

Code Solutions

# Python solution for Split Array Largest Sum

def splitArray(nums, k):
    # Helper function to determine if we can split array into <= k subarrays with max subarray sum <= max_sum
    def canSplit(max_sum):
        subarray_count = 1  # start with one subarray
        current_sum = 0
        for num in nums:
            if current_sum + num > max_sum:
                subarray_count += 1  # start a new subarray
                current_sum = num     # reset the sum with the current number
            else:
                current_sum += num    # add num to current subarray
        return subarray_count <= k  # valid if we used k or fewer subarrays

    low, high = max(nums), sum(nums)  # boundaries for binary search
    while low < high:
        mid = (low + high) // 2  # candidate maximum subarray sum
        if canSplit(mid):
            high = mid  # candidate is valid, try to find a smaller one
        else:
            low = mid + 1  # candidate too small, increase it
    return low

# Example usage:
nums = [7,2,5,10,8]
k = 2
print(splitArray(nums, k))  # Expected output: 18