# 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

| Item | Meaning |
|---|---|
| Input | Array `nums` and integer `k` |
| Output | Minimum possible largest subarray sum |
| Split rule | Exactly `k` non-empty subarrays |
| Subarray rule | Each part must be contiguous |
| Objective | Minimize the maximum sum among all parts |

Example function shape:

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

## Examples

Example 1:

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

Possible splits include:

```text
[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:

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

The largest subarray sum is:

```python
18
```

So the answer is:

```python
18
```

Example 2:

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

The best split is:

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

The sums are:

```python
6
9
```

The largest sum is `9`, so the answer is:

```python
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.

```python
left = max(nums)
```

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

```python
right = sum(nums)
```

So the answer is somewhere in:

```python
[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:

| Limit | Result |
|---|---|
| Too small | Impossible |
| Large enough | Possible |

So we can binary search for the smallest feasible limit.

## Algorithm

Set:

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

Define a helper function:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log S)` | Each feasibility check scans `nums`, and binary search spans the sum range |
| Space | `O(1)` | Only counters and bounds are used |

Here:

| Symbol | Meaning |
|---|---|
| `n` | Length of `nums` |
| `S` | `sum(nums) - max(nums)` search range size |

## Implementation

```python
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:

```python
def can_split(limit: int) -> bool:
```

We start with one subarray:

```python
parts = 1
current = 0
```

Then we scan the numbers:

```python
for num in nums:
```

If adding `num` would exceed the limit:

```python
if current + num > limit:
```

we start a new subarray:

```python
parts += 1
current = num
```

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

```python
if parts > k:
    return False
```

Otherwise, we keep adding to the current subarray:

```python
current += num
```

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

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

For each midpoint:

```python
mid = (left + right) // 2
```

If `mid` works, we try smaller values:

```python
right = mid
```

If `mid` fails, the answer must be larger:

```python
left = mid + 1
```

At the end:

```python
return left
```

returns the smallest feasible largest sum.

## Testing

```python
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

| Test | Why |
|---|---|
| `[7,2,5,10,8]`, `k = 2` | Standard example |
| `[1,2,3,4,5]`, `k = 2` | Standard example with increasing values |
| `[1,4,4]`, `k = 3` | Each subarray can contain one element |
| `[5]`, `k = 1` | Minimum input |
| All zeroes | Checks zero-valued sums |
| `k` close to `n` | Many small parts |
| Large first element | Answer cannot be below `max(nums)` |