HardArrayBinary SearchGreedy

Split Array Largest Sum

1 approach, code in every language

You are given an array of non-negative integers and a positive integer k. Cut the array into exactly k contiguous, non-empty pieces without reordering any elements. Every element must belong to exactly one piece.

Among all the ways to make these cuts, look at the piece whose element sum is the largest. Your goal is to arrange the cuts so that this largest piece sum is as small as possible, and return that minimized value.

Example 1

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

Output: 18

The best split is [7, 2, 5] and [10, 8], giving piece sums of 14 and 18. The largest is 18, and no other 2-way split lowers that maximum.

Example 2

Input: nums = [1, 4, 4], k = 3

Output: 4

Each element becomes its own piece: [1], [4], [4]. The largest piece sum is 4, which cannot be reduced with three pieces.

Constraints

1 <= nums.length <= 10^3
0 <= nums[i] <= 10^6
1 <= k <= nums.length

Binary Search on the Answer

Search the range of possible 'largest sum' values and greedily check whether each candidate lets us stay within k pieces.

Loading animation…

Intuition

The answer must be at least the biggest single element (that element has to fit inside some piece) and at most the total sum (one piece holding everything). For any candidate limit, a simple greedy pass tells us the fewest pieces needed to keep every piece sum at or below that limit. As the limit grows, the number of required pieces only shrinks, so feasibility is monotonic. That monotonic yes/no boundary is exactly what binary search exploits, letting us converge on the smallest limit that still fits in k pieces.

Algorithm walkthrough

1Set lo to the maximum element and hi to the sum of all elements; the answer lives in [lo, hi].
2Take mid = (lo + hi) / 2 as a candidate for the largest allowed piece sum.
3Greedily walk the array, starting a new piece whenever adding the next element would exceed mid, and count how many pieces result.
4If the count is at most k, mid is achievable, so move hi down to mid; otherwise raise lo to mid + 1.
5When lo meets hi, that value is the minimized largest piece sum.

Implementation

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def canSplit(limit: int) -> bool:
            pieces, current = 1, 0
            for num in nums:
                if current + num > limit:
                    pieces += 1
                    current = num
                    if pieces > k:
                        return False
                else:
                    current += num
            return True

        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if canSplit(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Time

O(n log S) where S is the total sum of the array

Space

O(1)

Each greedy feasibility check is O(n); binary search runs about log S of them.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Balanced Truckloads is our own problem on the technique behind Split Array Largest Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free