Split Array Largest Sum

Split Array Largest Sum looks like a partitioning puzzle, but the winning move is to stop thinking about where to cut and instead binary-search the answer itself — the largest piece-sum you are willing to allow.

The slow way first

The brute-force instinct is to try every way to drop k - 1 cut points into the array, sum each piece, and keep the split whose largest piece is smallest. The number of cut placements explodes combinatorially, so this is hopeless for large arrays.

The question to ask: instead of guessing where to cut, what if I guess the answer? Suppose I claim the largest piece can be at most some value cap. That claim is easy to check — and the smaller cap gets, the harder it is to satisfy. That monotonic yes/no is exactly what binary search feeds on.

The idea: search the value, greedily verify it

Pick a candidate cap. Sweep left to right, greedily growing the current piece until adding the next number would exceed cap; then start a new piece. Count the pieces. If you used k or fewer pieces, cap is feasible. Bigger caps are always feasible, smaller ones eventually are not — so binary-search cap over [max(nums), sum(nums)] and keep the smallest feasible value.

The bounds are the key insight: no piece can be smaller than the largest single element (it sits in some piece alone or with others), and no piece can exceed the total sum (that is just one piece). So the answer always lives in [max(nums), sum(nums)].

Walk through it

Step through the animation for nums = [7, 2, 5, 10, 8], k = 2. The cap label shows the current candidate and the shrinking [lo, hi] window; the feed line narrates the greedy piece count. We test cap = 21 (feasible, 2 pieces), then 15 (infeasible, 3 pieces), then 18 (feasible, 2 pieces), and the window collapses to 18.

Pseudocode

lo = max(nums)            # smallest possible largest-piece
hi = sum(nums)            # one giant piece
while lo < hi:
    cap = (lo + hi) // 2
    if feasible(cap):     # can we fit in k pieces with this cap?
        hi = cap          # cap works -> try smaller
    else:
        lo = cap + 1      # cap too tight -> go bigger
return lo
 
feasible(cap):
    pieces = 1, cur = 0
    for x in nums:
        if cur + x > cap: # next number overflows -> new piece
            pieces += 1, cur = x
        else:
            cur += x
    return pieces <= k

The Python solution

def split_array(nums, k):
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        cap = (lo + hi) // 2
        if feasible(nums, k, cap):
            hi = cap
        else:
            lo = cap + 1
    return lo
 
def feasible(nums, k, cap):
    pieces, cur = 1, 0
    for x in nums:
        if cur + x > cap:
            pieces, cur = pieces + 1, x
        else:
            cur += x
    return pieces <= k

• lo, hi = max(nums), sum(nums) brackets the answer between the largest element and the whole sum.
• The loop runs while lo < hi, halving the candidate range each time — classic binary search on a value.
• feasible does the verification: greedily fill the current piece (cur), and the moment cur + x would exceed cap, start a fresh piece with x.
• When feasible(cap) is true we set hi = cap (keep this answer, hunt for smaller); otherwise lo = cap + 1 (cap was too tight).
• The loop ends with lo == hi — the smallest cap that still passes feasible, which is the answer.

Complexity

Each feasible sweep is O(n), and binary search runs O(log S) times over the value range, for O(n log S) total. We use only a couple of counters, so extra space is O(1).

When this pattern shows up

Practice