> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Split Array Largest Sum Python Solution

> Tested Python solution for LeetCode 410 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 410, Hard. Topics: Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum. [View on LeetCode](https://leetcode.com/problems/split-array-largest-sum/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 410   # by problem number
lcpy gen -s split_array_largest_sum   # by problem name
```

## Problem

Given an integer array `nums` and an integer `k`, split `nums` into `k` non-empty subarrays such that the largest sum of any subarray is **minimized**.

Return *the minimized largest sum of the split*.

A **subarray** is a contiguous part of the array.

### Examples

```
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
```

```
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
```

### Constraints

* 1 \<= nums.length \<= 1000
* 0 \<= nums\[i] \<= 10^6
* 1 \<= k \<= min(50, nums.length)

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/split_array_largest_sum/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/split_array_largest_sum/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n * log(sum(nums))) binary search on the answer
    # Space: O(1)
    def split_array(self, nums: list[int], k: int) -> int:
        # Lower bound: a single element must fit. Upper bound: sum of all elements.
        low = max(nums)
        high = sum(nums)

        def count_subarrays(capacity: int) -> int:
            """Minimum subarrays needed so no subarray sum exceeds capacity."""
            subarrays = 1
            current = 0
            for value in nums:
                if current + value > capacity:
                    subarrays += 1
                    current = value
                else:
                    current += value
            return subarrays

        # Binary search for smallest capacity that fits within k subarrays.
        while low < high:
            mid = (low + high) // 2
            if count_subarrays(mid) <= k:
                high = mid
            else:
                low = mid + 1
        return low
```

## Complexity

| Time                                               | Space |
| -------------------------------------------------- | ----- |
| O(n \* log(sum(nums))) binary search on the answer | O(1)  |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).