Example 1
ready- Input
nums = [ 7, 2, 5, 10, 8 ] k = 2- Expected
18- Why
- [7,2,5] and [10,8] keep the largest sum at 18
Split Array Largest Sum
50 min · splitArray()You aren't choosing one best cut. You're choosing several cuts so the heaviest piece is as light as possible.
Given a non-negative integer array nums and an integer k, split the array into
exactly k non-empty contiguous subarrays, meaning each piece contains neighboring
values from the original order. Return the smallest possible value of the largest piece
sum.
A few ground rules:
- Every value belongs to exactly one piece.
- You may place cuts only between adjacent values; reordering isn't allowed.
- Duplicate values and zeros are valid.
Constraints
1 <= nums.length <= 1_0000 <= nums[i] <= 1_000_0001 <= k <= nums.length- The answer is at most
1_000_000_000, so it fits a signed 32-bit integer.
Hints
Guess the answer
Suppose no piece may exceed a candidate limit. Scan left to right, extending the
current piece until the next value would cross that limit, then start a new piece.
Bound the limit
No limit below max(nums) can hold the largest single value. sum(nums) always
works as one piece, so the answer lies between those two numbers.
Search the first workable limit
A larger limit can only reduce the number of pieces the greedy scan needs. Binary
search for the smallest limit that needs at most k pieces.
Follow-up
Which part of the greedy feasibility check stops being trustworthy if negative values are allowed?
Visible cases
Examples
Example 2
ready- Input
nums = [ 1, 2, 3, 4, 5 ] k = 2- Expected
9- Why
- cutting after 3 gives piece sums 6 and 9
Example 3
ready- Input
nums = [ 0, 4, 0, 6 ] k = 3- Expected
6- Why
- zeros don't force the largest piece above 6
Interview signal
Asked at
GoogleAmazonMicrosoft
Try every largest sum
A candidate largest sum ranges from max(nums) through sum(nums). For each candidate,
greedily count the fewest contiguous pieces needed without crossing it.
def split_array(nums: list[int], k: int) -> int:
def pieces_needed(limit: int) -> int:
pieces, current = 1, 0
for value in nums:
if current + value > limit:
pieces += 1
current = 0
current += value
return pieces
for limit in range(max(nums), sum(nums) + 1):
if pieces_needed(limit) <= k:
return limit
return sum(nums)Time O(n · S). Space O(1). Here S is sum(nums). The answer range can contain a
billion integers, so scanning it is the bottleneck.
Binary search the largest sum
For a fixed limit, fill each piece as much as possible before cutting. Because all values are non-negative, cutting earlier can't reduce the total number of pieces. The greedy scan therefore gives the minimum pieces needed for that limit.
If it needs at most k pieces, the limit is feasible, meaning it can support the
required split. Any extra cuts can split existing non-empty pieces until there are
exactly k, without increasing the largest sum.
def split_array(nums: list[int], k: int) -> int:
def pieces_needed(limit: int) -> int:
pieces, current = 1, 0
for value in nums:
if current + value > limit:
pieces += 1
current = 0
current += value
return pieces
left, right = max(nums), sum(nums)
while left < right:
middle = left + (right - left) // 2
if pieces_needed(middle) <= k:
right = middle
else:
left = middle + 1
return leftA feasible middle stays in the interval because it may be optimal. An infeasible one,
along with every smaller limit, can be discarded.
Time O(n log S). Space O(1). Binary search makes O(log S) greedy passes over the array.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
18
Run: visible + custom · Submit: full suite