Binary Search on Answer: Find the Minimal Maximum Subarray Sum

Use binary search over the possible maximum subarray sum to find the smallest value that allows splitting into at most k subarrays.

binary-search arrays greedy subarray-sum

You are given a list of non-negative integers `nums` and an integer `k`. You must split `nums` into **at most** `k` contiguous subarrays (you may use fewer). The goal is to minimize the maximum sum among these subarrays.

Write a function:

```python
def split_array(nums, k):
    pass
```

Return the **minimal possible value** of the largest subarray sum after an optimal split.

For example, `nums = [7, 2, 5, 10, 8]` and `k = 2`. The optimal split is `[7, 2, 5]` and `[10, 8]`, giving max sums 14 and 18, so the result is 18. If you split as `[7]` and `[2, 5, 10, 8]`, the max is 25, which is worse.

Constraints

1 <= len(nums) <= 10^5
0 <= nums[i] <= 10^9
1 <= k <= len(nums)
The sum of all numbers fits in a 64-bit integer.

Your solution must run in O(n log(sum(nums))) time.

Example

```python
>>> split_array([7, 2, 5, 10, 8], 2)
18
>>> split_array([1, 2, 3, 4, 5], 1)
15
>>> split_array([1, 2, 3, 4, 5], 5)
5
>>> split_array([5, 5, 5, 5], 2)
10
```

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of checking: can we split nums into at most k subarrays such that each subarray sum does not exceed a given limit X?

The check can be done greedily by iterating and forming a new subarray whenever adding the next element would exceed X.

Binary search the answer between max(nums) and sum(nums).

The check function runs in O(n), so total is O(n log(total)).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.