Split Array Largest Sum (LeetCode 410)

The problem

You get an array nums of non-negative integers and an integer k. Split nums into exactly k non-empty contiguous subarrays. Each split has a “largest sum” (the biggest subarray total). Return the smallest possible largest sum over all ways to split.

Input:  nums = [7, 2, 5, 10, 8], k = 2
Output: 18

Splitting as [7, 2, 5] and [10, 8] gives sums 14 and 18. Every other split has a larger maximum.

How to think about it

Start with brute force. Try every way to place k - 1 cut points among n - 1 gaps, compute each split’s largest sum, and take the minimum. That is C(n − 1, k − 1) splits, which is exponential. A DP over “first i elements in j pieces” is O(k · n²), which passes but is slow and harder to write.

Flip the question. Instead of “what’s the best split?”, ask ”given a cap c, can I split into at most k pieces with every piece <= c?” That is easy greedily: keep adding elements to the current piece; when the next one would push it past c, start a new piece. Making a piece end earlier than necessary never helps, so the greedy count is the minimum number of pieces for that cap.

The key insight: feasibility is monotonic, so binary-search the cap. A bigger cap never needs more pieces. So answers to “is cap c feasible?” go no, no, …, yes, yes, and the answer is the first yes. The cap is at least max(nums) (each element must fit in some piece) and at most sum(nums) (one piece). “At most k pieces” is enough: as long as n >= k, a split with fewer pieces can always be cut further without raising its maximum.

Which pattern is this? Search on the answer, the “minimise the maximum” variety. The tell is the phrase “minimise the largest” (or “maximise the smallest”). It’s the same algorithm as Capacity To Ship Packages.

Approach

1. Define ok(cap): count pieces greedily, starting a new piece whenever cur + x > cap. Return pieces <= k.
2. Set lo = max(nums), hi = sum(nums).
3. While lo < hi: let mid = (lo + hi) // 2. If ok(mid), set hi = mid; else set lo = mid + 1.
4. Return lo.

Solution

def split_array(nums, k):
    def ok(cap):
        pieces = 1; cur = 0
        for x in nums:
            if cur + x > cap: pieces += 1; cur = 0   # x starts a new piece
            cur += x
        return pieces <= k                           # fewer pieces can always be split more
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid): hi = mid
        else: lo = mid + 1
    return lo
# split_array([7,2,5,10,8], 2) -> 18

Dry run

On nums = [7, 2, 5, 10, 8], k = 2, the search starts with lo = 10, hi = 32:

Now lo == hi == 18. At cap 18 the greedy split is [7, 2, 5] and [10, 8], so the answer is 18.

Complexity

• Time: O(n log S), where S = sum(nums). O(log S) binary-search steps, each an O(n) greedy pass.
• Space: O(1).

Edge cases and pitfalls

• k == 1 gives sum(nums); k == len(nums) gives max(nums).
• Starting lo below max(nums) makes the greedy count silently wrong, because a single element bigger than the cap would be placed in its own “piece” that breaks the cap.
• Zeros in nums are fine; they never force a new piece.
• Checking pieces == k instead of <= k breaks monotonicity and gives wrong answers.
• The answer is always a real subarray sum, even though you search over every integer. The first feasible cap must be achieved exactly by some piece, or a smaller cap would also work.

Related problems

• Capacity To Ship Packages Within D Days (LeetCode 1011): the same algorithm, phrased as ship capacity and days.
• Koko Eating Bananas (LeetCode 875): search on the answer with a different feasibility check.
• Minimum Cost to Cut a Stick (LeetCode 1547): another “where to cut” problem, solved with interval DP instead.