LeetCode 410 - Split Array Largest Sum

LeetCode Problem 410

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum

Solution

Problem Understanding

The problem gives an integer array nums and an integer k. We must divide the array into exactly k non-empty contiguous subarrays. Among those subarrays, each one has its own sum, and the goal is to minimize the largest subarray sum.

In other words, we are trying to split the array as evenly as possible in terms of cumulative sum, while preserving the original order of elements and ensuring every partition remains contiguous.

For example, if:

nums = [7,2,5,10,8]
k = 2

One possible split is:

[7,2,5] and [10,8]

The sums are:

14 and 18

The largest subarray sum is 18.

Another split:

[7,2] and [5,10,8]

Produces sums:

9 and 23

The largest subarray sum becomes 23, which is worse because we want the maximum subarray sum to be as small as possible.

The input constraints are extremely important:

• nums.length <= 1000
• k <= 50
• nums[i] <= 10^6

These constraints tell us several things:

• The array is not tiny, so exponential partition generation is impossible.
• The values can become very large, meaning subarray sums may exceed 32-bit integer ranges in some languages.
• Since k is relatively small, dynamic programming is possible, but we should still look for more efficient solutions.

The problem also guarantees:

• Every split must contain at least one element.
• The array contains non-negative integers.
• k is always valid.

The fact that all numbers are non-negative is the key observation that enables binary search on the answer.

Several edge cases are important:

• k = 1, meaning the entire array must remain one subarray.
• k = len(nums), meaning every element becomes its own partition.
• Arrays containing zeros, which can create multiple equivalent partitions.
• Very large values, which can expose integer overflow issues in some languages.
• Highly uneven arrays, such as [1,1,1,1000], where balancing becomes difficult.

Approaches

Brute Force Approach

The brute force solution tries every possible way to place k - 1 partition boundaries inside the array.

For an array of length n, there are n - 1 possible split positions. We must choose k - 1 of them. For every partition arrangement, we compute the sum of each subarray and track the maximum subarray sum. The answer is the minimum of all such maxima.

This approach is correct because it exhaustively checks every valid partitioning configuration.

However, it becomes computationally infeasible very quickly. The number of possible partitions grows combinatorially:

C(n - 1, k - 1)

For n = 1000, this is astronomically large.

Even with optimizations like prefix sums, brute force cannot handle the input constraints.

Key Insight

The important observation is that the answer itself can be binary searched.

Suppose we guess a value X and ask:

Can we split the array into at most k subarrays such that no subarray sum exceeds X?

This becomes a greedy feasibility problem.

Because all numbers are non-negative:

• If a maximum sum X is feasible, then every larger value is also feasible.
• If X is not feasible, then every smaller value is also not feasible.

This monotonic behavior is exactly what binary search requires.

The smallest possible answer is:

max(nums)

because no subarray can avoid containing its largest element.

The largest possible answer is:

sum(nums)

which corresponds to using only one subarray.

We binary search this range and greedily check feasibility.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(k)	Tries every possible partition configuration
Optimal	O(n log(sum(nums)))	O(1)	Binary search on answer with greedy validation

Algorithm Walkthrough

Optimal Algorithm: Binary Search + Greedy

1. Initialize the binary search boundaries.

The minimum possible largest subarray sum is the largest individual element because no partition can split an element.

The maximum possible largest subarray sum is the total array sum because we could place everything into one subarray.

So:

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

2. Perform binary search over the answer space.

At each step, compute:

mid = (left + right) // 2

Here, mid represents a candidate value for the maximum allowed subarray sum. 3. Greedily test whether mid is feasible.

Traverse the array while maintaining a running subarray sum.

For each number:

• Add it to the current subarray.
• If the sum exceeds mid, start a new subarray.
• Increment the subarray count.

This greedy strategy minimizes the number of partitions because we only split when absolutely necessary. 4. Check the number of required subarrays.

If we can partition the array into k or fewer subarrays, then mid is feasible.

This means we may be able to reduce the answer further, so move left:

right = mid

5. Otherwise, if more than k subarrays are required, then mid is too small.

Increase the search range:

left = mid + 1

6. Continue until left == right.

At this point, we have found the smallest feasible maximum subarray sum.

Why it works

The correctness depends on two properties.

First, feasibility is monotonic. If a maximum sum X works, any larger value also works because larger limits only make partitioning easier.

Second, the greedy partitioning strategy always produces the minimum number of subarrays for a given limit. Since we only split when necessary, any alternative strategy would use at least as many partitions.

Together, these properties guarantee that binary search converges to the optimal minimum largest subarray sum.

Python Solution

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def can_split(max_allowed_sum: int) -> bool:
            subarray_count = 1
            current_sum = 0

            for num in nums:
                if current_sum + num > max_allowed_sum:
                    subarray_count += 1
                    current_sum = num
                else:
                    current_sum += num

            return subarray_count <= k

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

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

            if can_split(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation begins by defining a helper function named can_split.

This function answers the feasibility question:

Can the array be divided into at most k subarrays such that each subarray sum is at most max_allowed_sum?

Inside the helper, we greedily accumulate elements into the current subarray. Once adding another element would exceed the limit, we create a new subarray.

The binary search then operates over the valid answer range:

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

At every iteration, the midpoint becomes the candidate maximum subarray sum.

If the helper confirms feasibility, we try to find a smaller valid answer by moving the right boundary.

Otherwise, we increase the lower bound.

Eventually, the search converges to the smallest feasible value.

Go Solution

func splitArray(nums []int, k int) int {
	canSplit := func(maxAllowedSum int) bool {
		subarrayCount := 1
		currentSum := 0

		for _, num := range nums {
			if currentSum+num > maxAllowedSum {
				subarrayCount++
				currentSum = num
			} else {
				currentSum += num
			}
		}

		return subarrayCount <= k
	}

	left := nums[0]
	right := 0

	for _, num := range nums {
		if num > left {
			left = num
		}
		right += num
	}

	for left < right {
		mid := left + (right-left)/2

		if canSplit(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

The Go implementation follows the same algorithmic structure as the Python version.

One notable difference is integer handling. In Go, integer overflow can occur if using smaller integer types, but the standard int type is sufficient for the problem constraints on LeetCode.

The midpoint calculation uses:

mid := left + (right-left)/2

instead of:

(left + right) / 2

This is a common defensive practice that avoids overflow in languages with fixed-width integers.

Go slices are naturally passed by reference-like semantics, so no additional copying occurs during iteration.

Worked Examples

Example 1

nums = [7,2,5,10,8]
k = 2

Initial search range:

left = 10
right = 32

Binary Search Iteration 1

mid = 21

Greedy partitioning:

Number	Current Sum	Action	Subarrays
7	7	continue	1
2	9	continue	1
5	14	continue	1
10	24	split	2
8	18	continue	2

Feasible with 2 subarrays.

Update:

right = 21

Binary Search Iteration 2

mid = 15

Number	Current Sum	Action	Subarrays
7	7	continue	1
2	9	continue	1
5	14	continue	1
10	24	split	2
8	18	split	3

Requires 3 subarrays.

Update:

left = 16

Binary Search Iteration 3

mid = 18

Number	Current Sum	Action	Subarrays
7	7	continue	1
2	9	continue	1
5	14	continue	1
10	24	split	2
8	18	continue	2

Feasible.

Update:

right = 18

Binary Search Iteration 4

mid = 17

Number	Current Sum	Action	Subarrays
7	7	continue	1
2	9	continue	1
5	14	continue	1
10	24	split	2
8	18	split	3

Not feasible.

Update:

left = 18

Now:

left == right == 18

Final answer:

18

Example 2

nums = [1,2,3,4,5]
k = 2

Initial range:

left = 5
right = 15

Binary Search Iteration 1

mid = 10

Partitions:

[1,2,3,4] = 10
[5] = 5

Feasible.

Update:

right = 10

Binary Search Iteration 2

mid = 7

Partitions:

[1,2,3] = 6
[4] = 4
[5] = 5

Requires 3 subarrays.

Update:

left = 8

Binary Search Iteration 3

mid = 9

Partitions:

[1,2,3] = 6
[4,5] = 9

Feasible.

Update:

right = 9

Binary Search Iteration 4

mid = 8

Partitions:

[1,2,3] = 6
[4] = 4
[5] = 5

Requires 3 subarrays.

Update:

left = 9

Final answer:

9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log(sum(nums)))	Binary search performs log(sum(nums)) iterations, each scanning the array once
Space	O(1)	Only a few variables are used

The binary search range spans from max(nums) to sum(nums). Each binary search iteration requires a full linear scan to validate feasibility.

Since the validation step is greedy and uses constant extra memory, the space complexity remains O(1).

Test Cases

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def can_split(max_allowed_sum: int) -> bool:
            subarray_count = 1
            current_sum = 0

            for num in nums:
                if current_sum + num > max_allowed_sum:
                    subarray_count += 1
                    current_sum = num
                else:
                    current_sum += num

            return subarray_count <= k

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

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

            if can_split(mid):
                right = mid
            else:
                left = mid + 1

        return left

solution = Solution()

assert solution.splitArray([7,2,5,10,8], 2) == 18  # provided example 1
assert solution.splitArray([1,2,3,4,5], 2) == 9  # provided example 2

assert solution.splitArray([1], 1) == 1  # single element array
assert solution.splitArray([1,2,3,4], 1) == 10  # k = 1, entire array
assert solution.splitArray([1,2,3,4], 4) == 4  # k = n, largest element

assert solution.splitArray([0,0,0,0], 2) == 0  # all zeros
assert solution.splitArray([1000000,1000000], 1) == 2000000  # large values

assert solution.splitArray([1,4,4], 3) == 4  # each element separate
assert solution.splitArray([2,3,1,2,4,3], 5) == 4  # many partitions

assert solution.splitArray([1,1,1,1000], 2) == 1000  # highly uneven distribution
assert solution.splitArray([5,5,5,5], 2) == 10  # balanced partitions

assert solution.splitArray([1,2,3,4,5,6,7,8,9], 3) == 17  # larger mixed case

Test	Why
[7,2,5,10,8], k=2	Verifies the primary example
[1,2,3,4,5], k=2	Tests balanced increasing values
[1], k=1	Smallest valid input
[1,2,3,4], k=1	Entire array must remain together
[1,2,3,4], k=4	Every element becomes its own partition
[0,0,0,0], k=2	Handles zero values correctly
[1000000,1000000], k=1	Tests large sums
[1,4,4], k=3	One element per partition
[2,3,1,2,4,3], k=5	Many partitions relative to size
[1,1,1,1000], k=2	Uneven distribution stress test
[5,5,5,5], k=2	Perfectly balanced split
[1,2,3,4,5,6,7,8,9], k=3	Larger realistic scenario

Edge Cases

Case 1: k = 1

When k equals 1, the entire array must remain a single subarray. This means the answer is simply the total sum of the array.

A naive implementation might still attempt unnecessary partition logic or accidentally split the array anyway. The binary search solution naturally handles this because any feasible limit smaller than the total sum will require more than one partition.

Case 2: k = len(nums)

When k equals the array length, every element can become its own subarray. In this situation, the optimal answer is the maximum element in the array.

This is important because no partition can reduce the contribution of the largest element. The algorithm correctly initializes the lower bound as max(nums), ensuring the final answer can never go below this value.

Case 3: Arrays Containing Zeros

Arrays with many zeros can create multiple valid partition arrangements with identical sums.

For example:

nums = [0,0,0,0]

A buggy implementation may incorrectly create extra partitions or mishandle zero accumulation.

The greedy approach handles this correctly because adding zero never increases the current subarray sum beyond the allowed limit.

Case 4: Very Large Numbers

The constraints allow values up to 10^6, and arrays may contain up to 1000 elements. This means cumulative sums may reach 10^9.

Languages with fixed-width integers can overflow if midpoint calculations are done carelessly.

The Go solution avoids this issue with:

mid := left + (right-left)/2

which is the standard overflow-safe binary search pattern.