Split Array Largest Sum

Q: What is the time complexity of Split Array Largest Sum?

The binary search runs in O(n log S) time, where n is the length of nums and S its sum. Each greedy check is one pass over the array, and the range of caps halves after every check: about 29 checks when S = 5 × 10^8 . It uses O(1) extra space. The DP is O(k·n²) time and O(n) space.

Q: Why is the feasibility check monotonic?

If every part of some split sums to at most c , the same split also has every part at most c+1 . So once a cap works, every larger cap works, and once a cap fails, every smaller cap fails. The answers form a run of no followed by a run of yes, which is exactly what binary search needs to find the boundary.

Q: Why does the greedy check find the fewest parts?

Greedy keeps adding values to a part until the next one would pass the cap. Compare it with any valid split, part by part. Each greedy part starts at or after the other split's part with the same number, so its values up to that part's end are a piece of a part that fits under the cap. No value is negative, so the piece fits too, and greedy extends at least as far. Greedy never falls behind, so it covers the array in as few parts as any split can.

Q: Does the binary search work with negative numbers?

No. With negative values, adding a value can lower a sum, so greedy may close a part too early and miss a split that works. Splitting a part can also raise one piece's sum above the whole, so having fewer than k parts no longer means k parts work. The DP makes neither assumption and stays correct, at O(k·n²) time.

HardBinary search Dynamic programming

+10

You get an array nums of non-negative integers and an integer k. Cut nums into exactly k parts, where each part is a non-empty run of neighbouring values and the parts keep their order. Every part has a sum, and the cost of a split is the largest of those sums.

Return the smallest cost that any split into k parts can reach.

Function

splitArray(nums: integer-array, k: integer) → integer

numsinteger-array: the non-negative values, in order
kinteger: the number of contiguous parts to cut them into
Returnsinteger: the smallest possible value of the largest part sum

Constraints

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Every part holds at least one value. A part whose values are all 0 sums to 0, which is allowed.

Examples

Input: nums = [6, 2, 9, 4, 7, 3]k = 3
Output: 13
Explanation: The split [6, 2], [9, 4], [7, 3] has sums 8, 13 and 10, so its cost is 13. No split costs 12: packing parts left to right with every sum at most 12 gives [6, 2], [9], [4, 7], [3], four parts where only three are allowed.

Input: nums = [8, 1, 1, 1, 5]k = 2
Output: 8
Explanation: The 8 sits in some part, so no split can cost less than 8. [8] and [1, 1, 1, 5] both sum to 8, so 8 is reached.

+20 hidden tests on Submit

Follow-up

Each greedy check reads all n values. With prefix sums, a check can find where each part ends by binary search instead. How fast does the whole method get when k is small and nums is long?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The two demands pull against each other: you must use exactly k parts, and you want the biggest part as small as possible. Trying every place for the k-1 cuts explodes, and a dynamic program over prefixes brings that down to O(k·n²), still too slow for 5000 values. The fast idea turns the question around. Instead of searching for the best split, guess a cap and ask whether k parts can stay under it. One greedy pass answers that, the answers only flip once as the cap grows, and binary search finds the flip in about 29 passes.

Dynamic programming over prefixes

Correct, but does not finish on the largest tests

Intuition

Look at the last part of a split. If the first j values form p parts, the last part is some run nums[i..j-1], and the first i values form the other p-1 parts. The cost is the larger of two numbers: the cost of those p-1 parts, and the sum of the last run. Whatever the last run is, you want the first i values split as cheaply as possible, and that best split does not depend on anything to its right. So you can compute it once and reuse it.

Write best[p][j] for the smallest cost of cutting the first j values into p parts. One part has no choice: best[1][j] is the sum of the first j values. For more parts, try every start i of the last part: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), where prefix[j] is the sum of the first j values. The start i runs from p-1, because p-1 non-empty parts need at least p-1 values, up to j-1, because the last part needs one value. The answer is best[k][n]. Row p only reads row p-1, so two rows of length n+1 are enough.

In the first example, cutting [6, 2, 9, 4] into two parts can end the first part after 6 (cost max(6, 15) = 15), after 2 (max(8, 13) = 13) or after 9 (max(17, 4) = 17), so best[2][4] = 13. Then best[3][6] tries the last part [7, 3] and gets max(13, 10) = 13, which no other start beats.

The work is the problem. There are k rows, n ends per row and up to n starts per end: up to k·n²/2 steps. With n = 5000 and k = 2500 the inner loop runs about 1.8 × 10^10 times: 18 seconds even at 10^9 simple steps a second. The DP is still worth knowing: it never assumes the values are non-negative, so it keeps working where the fast method does not.

Algorithm

Build prefix, where prefix[j] is the sum of the first j values.
Set the row for one part: best[j] = prefix[j].
For each part count p from 2 to k, and each end j from p to n, take the minimum over i from p-1 to j-1 of max(best[i], prefix[j] - prefix[i]).
Store those minimums in a new row and make it best.
Return best[n].

def splitArray(nums, k):
    n = len(nums)
    # prefix[j] is the sum of the first j values
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    # best[j]: the smallest largest part when the first j values form one part
    best = prefix[:]
    for parts in range(2, k + 1):
        nxt = [0] * (n + 1)
        for j in range(parts, n + 1):
            lowest = prefix[j]  # never worse than one part holding everything
            for i in range(parts - 1, j):
                # the first i values form parts-1 parts, nums[i..j-1] is the last part
                worst = max(best[i], prefix[j] - prefix[i])
                if worst < lowest:
                    lowest = worst
            nxt[j] = lowest
        best = nxt
    return best[n]

Binary search on the largest sum

Intuition

Turn the question around. Pick a cap c and ask: can nums be cut into k parts with every part sum at most c? The answer to the problem is the smallest cap for which the answer is yes. That question is much easier than the original, for two reasons.

First, one greedy pass answers it. Walk left to right and keep adding values to the current part while its sum stays within c; when the next value would push it past c, close the part and start a new one with that value. This uses the fewest parts any split under the cap can use. Compare it with any other valid split, part by part. Both first parts start at the first value, and greedy only stops when the next value does not fit, so the greedy first part ends at least as far right. The greedy second part then starts at or after the other second part. Its values up to that part's end are a piece of it, and with no negative values a piece never sums to more than the whole, so they fit and greedy again reaches at least as far. Greedy never falls behind, so it never needs more parts.

Second, fewer parts than k is as good as exactly k. If greedy needs m < k parts, cut a part that holds two or more values into two. Its pieces sum to no more than the whole, because no value is negative, and since n ≥ k there is always such a part until you reach k. So the test is partsNeeded(c) ≤ k.

Now the key property: the test is monotonic. If cap c works, c+1 works too, since the same split still fits under a larger cap. Over the caps from max(nums) to sum(nums) the answers read no, no, ..., no, yes, yes, ..., yes, and you want the first yes. The range is safe at both ends: no cap below max(nums) can hold that value, and the total always fits in one part. The first yes is also a real cost, not only a bound: if no part of its split summed to exactly c, the cap c-1 would work as well.

Trace the first example, [6, 2, 9, 4, 7, 3] with k = 3. The caps run from 9 to 31. Cap 20 packs [6, 2, 9], [4, 7, 3]: 2 parts, yes, so the range becomes 9 to 20. Cap 14 gives [6, 2], [9, 4], [7, 3]: 3 parts, yes, range 9 to 14. Cap 11 gives [6, 2], [9], [4, 7], [3]: 4 parts, no, range 12 to 14. Cap 13 needs 3 parts, yes, range 12 to 13. Cap 12 needs 4, no, so the answer is 13.

Each pass reads n values and the range halves every time. With a total S of up to 5 × 10^8 that is about 29 passes over 5000 values, roughly 150000 steps.

Algorithm

Set lo = max(nums) and hi = sum(nums).
While lo < hi, take mid = lo + (hi - lo) / 2.
Count the parts greedy needs under cap mid: start with 1 part and a running sum of 0; when adding a value would pass mid, add a part and restart the sum at that value.
If the count is at most k, set hi = mid; otherwise set lo = mid + 1.
Return lo.

def splitArray(nums, k):
    def parts_needed(cap):
        # Fill each part left to right and start a new one only when the next value would pass cap.
        parts, current = 1, 0
        for x in nums:
            if current + x > cap:
                parts += 1
                current = x
            else:
                current += x
        return parts

    lo, hi = max(nums), sum(nums)  # one value per part at best, everything in one part at worst
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid needs more than k parts, so the answer is larger
    return lo

Pitfalls and edge cases

The search is short, so the bugs sit in the greedy check and in the bounds.

Starting lo below max(nums). The greedy check puts a value that is larger than the cap into a part of its own and carries on, so it reports a cap of 5 as fine for [1, 9] with k = 2. Start at the largest value, or make the check fail when a single value exceeds the cap.
Testing partsNeeded(c) == k. Greedy often needs fewer parts than k: for [3, 0, 4] and k = 3, cap 4 packs [3, 0], [4]. With == no cap ever passes. Fewer parts can always be cut further, so test ≤ k.
Counting parts from 0. The first part exists before any value overflows it, so the count starts at 1.
Setting hi = mid - 1 when mid works. That can skip the answer itself. Keep hi = mid and loop while lo < hi.
Starting the DP's i at 0. A cell best[i] with i < p-1 stands for fewer values than parts, which no split can do, and in a row filled with zeros it reads as cost 0. For [100, 1, 1] with k = 3 the DP then reports 2 instead of 100. Start i at p-1.
Overflow at larger limits. Here the total is at most 5 × 10^8, so 32-bit integers hold it. If values reach 10^6, 2148 of them already pass 2^31-1, so use 64-bit sums.

Frequently asked questions4

What is the time complexity of Split Array Largest Sum?

The binary search runs in O(n log S) time, where n is the length of nums and S its sum. Each greedy check is one pass over the array, and the range of caps halves after every check: about 29 checks when S = 5 × 10^8. It uses O(1) extra space. The DP is O(k·n²) time and O(n) space.

Why is the feasibility check monotonic?

If every part of some split sums to at most c, the same split also has every part at most c+1. So once a cap works, every larger cap works, and once a cap fails, every smaller cap fails. The answers form a run of no followed by a run of yes, which is exactly what binary search needs to find the boundary.

Why does the greedy check find the fewest parts?

Greedy keeps adding values to a part until the next one would pass the cap. Compare it with any valid split, part by part. Each greedy part starts at or after the other split's part with the same number, so its values up to that part's end are a piece of a part that fits under the cap. No value is negative, so the piece fits too, and greedy extends at least as far. Greedy never falls behind, so it covers the array in as few parts as any split can.

Does the binary search work with negative numbers?

No. With negative values, adding a value can lower a sum, so greedy may close a part too early and miss a split that works. Splitting a part can also raise one piece's sum above the whole, so having fewer than k parts no longer means k parts work. The DP makes neither assumption and stays correct, at O(k·n²) time.

Python

def splitArray(nums, k):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [6, 2, 9, 4, 7, 3]
k = 3

Expected