LeetCode 410: Split Array Largest Sum

Problem Restatement

We are given an integer array nums and an integer k.

We must split nums into exactly k non-empty subarrays.

Each subarray must be contiguous.

Among the k subarrays, each has a sum. We want to minimize the largest of those sums.

Return that minimized largest sum.

The official examples include nums = [7,2,5,10,8], k = 2, whose answer is 18, and nums = [1,2,3,4,5], k = 2, whose answer is 9. The constraints are 1 <= nums.length <= 1000, 0 <= nums[i] <= 10^6, and 1 <= k <= min(50, nums.length).

Input and Output

Example function shape:

def splitArray(nums: list[int], k: int) -> int:
    ...

Examples

Example 1:

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

Possible splits include:

[7] [2, 5, 10, 8]       largest sum = 25
[7, 2] [5, 10, 8]       largest sum = 23
[7, 2, 5] [10, 8]       largest sum = 18
[7, 2, 5, 10] [8]       largest sum = 24

The best split is:

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

The largest subarray sum is:

18

So the answer is:

18

Example 2:

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

The best split is:

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

The sums are:

6
9

The largest sum is 9, so the answer is:

9

First Thought: Try Every Split

A direct approach is to try every possible way to place k - 1 cuts between elements.

For each split, compute the largest subarray sum.

Then return the smallest largest sum.

This works for very small arrays.

But if nums has length n, there are many ways to choose cut positions. The number of choices grows too quickly.

We need to search the answer value instead of searching all split layouts.

Key Insight

The answer is a number.

It must be at least the largest single element, because every element must belong to some subarray.

left = max(nums)

It can be at most the total sum, because putting everything into one subarray gives that largest sum.

right = sum(nums)

So the answer is somewhere in:

[max(nums), sum(nums)]

Now suppose we guess a maximum allowed subarray sum limit.

We can ask:

Can we split the array into at most k subarrays so that every subarray sum is at most limit?

This can be checked greedily.

Scan from left to right. Keep adding numbers to the current subarray until adding the next number would exceed limit. Then start a new subarray.

If this greedy process needs at most k subarrays, then limit is feasible.

If it needs more than k subarrays, then limit is too small.

This gives a monotonic condition:

So we can binary search for the smallest feasible limit.

Algorithm

Set:

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

Define a helper function:

can_split(limit)

This returns whether nums can be split into at most k subarrays where every subarray sum is at most limit.

Inside can_split:

1. Start with one subarray.
2. Add numbers from left to right.
3. If adding a number would exceed limit, start a new subarray.
4. Count how many subarrays are needed.
5. Return whether this count is at most k.

Then binary search:

1. Let mid = (left + right) // 2.
2. If can_split(mid) is true, try a smaller answer by moving right = mid.
3. Otherwise, move left = mid + 1.
4. When the search ends, left is the minimum feasible largest sum.

Correctness

For a fixed limit, the greedy validation creates the fewest subarrays possible under that limit.

It keeps adding elements to the current subarray as long as the sum stays at most limit. Starting a new subarray earlier would only leave less room in the current subarray and cannot reduce the number of subarrays needed.

Therefore, if greedy needs more than k subarrays, no valid split with limit limit exists.

If greedy needs at most k subarrays, then a split with maximum subarray sum at most limit exists. Since all numbers are non-negative, any split into fewer than k subarrays can be refined into exactly k non-empty subarrays without increasing the largest sum, as long as k <= len(nums).

The feasibility condition is monotonic. If a limit works, every larger limit also works. If a limit fails, every smaller limit also fails.

Binary search over this monotonic range finds the smallest feasible limit.

That smallest feasible limit is exactly the minimized largest subarray sum.

Complexity

Here:

Implementation

class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        def can_split(limit: int) -> bool:
            parts = 1
            current = 0

            for num in nums:
                if current + num > limit:
                    parts += 1
                    current = num

                    if parts > k:
                        return False
                else:
                    current += num

            return True

        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

Code Explanation

The helper function checks whether a proposed maximum sum is possible:

def can_split(limit: int) -> bool:

We start with one subarray:

parts = 1
current = 0

Then we scan the numbers:

for num in nums:

If adding num would exceed the limit:

if current + num > limit:

we start a new subarray:

parts += 1
current = num

If we already need more than k subarrays, this limit fails:

if parts > k:
    return False

Otherwise, we keep adding to the current subarray:

current += num

The binary search begins with the smallest and largest possible answers:

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

For each midpoint:

mid = (left + right) // 2

If mid works, we try smaller values:

right = mid

If mid fails, the answer must be larger:

left = mid + 1

At the end:

return left

returns the smallest feasible largest sum.

Testing

def test_split_array():
    s = Solution()

    assert s.splitArray([7, 2, 5, 10, 8], 2) == 18
    assert s.splitArray([1, 2, 3, 4, 5], 2) == 9
    assert s.splitArray([1, 4, 4], 3) == 4
    assert s.splitArray([5], 1) == 5
    assert s.splitArray([0, 0, 0, 0], 2) == 0
    assert s.splitArray([2, 3, 1, 2, 4, 3], 5) == 4
    assert s.splitArray([10, 1, 1, 1], 2) == 10

    print("all tests passed")

Test Notes