hard

Split Array Largest Sum

Split an array into a fixed number of parts to minimize the largest part sum.

1. Define the problem

Split Array Largest Sum

Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays such that the largest sum among these subarrays is as small as possible. Return that minimized largest sum. Instead of trying every way to split the array, flip the question around: guess a candidate cap on the largest allowed subarray sum, and check whether nums can be split into k or fewer pieces without any piece exceeding that cap. That check is a simple greedy pass — keep adding numbers to the current piece until adding one more would exceed the cap, then start a new piece. Because a bigger cap always makes splitting easier (never harder), the feasibility check flips from false to true exactly once as the cap increases — which means binary search on the answer can find the smallest cap that still works, between the largest single value (the loosest lower bound) and the total sum (the loosest upper bound).

Constraints

  • 1 ≤ nums.length ≤ 1000
  • 0 ≤ numsi ≤ 106
  • 1 ≤ k ≤ min(50, nums.length)

Example

Inputnums = [7, 2, 5, 10, 8], k = 2
Output18

Explanation Split into [7, 2, 5] and [10, 8]. The largest sum is 18, the smallest possible largest sum for any split into 2 pieces.

2. Know the words first

In plain terms

Binary search on the answer
Instead of searching an array, searching a range of possible answer values — narrowing in on the smallest (or largest) value that still satisfies some feasibility check.
3. Visualize the solution

Binary search a cap, greedily check if it splits into k pieces

Binary search a cap, greedily check if it splits into k pieces
Statusinit

nums=[3,2,4], k=2. The answer is somewhere between 4 and 9, so the box starts across the whole row.

What happens in this step

lo = max(nums) = 4 (no cap can be smaller than the largest single number, because that number has to sit in some piece)
hi = sum(nums) = 9 (one giant piece always works, and it needs only 1 piece)

Nothing has been checked yet, so every cell is blank.
Step 1 of 5

Steps to visualize

  1. The walkthrough uses a smaller example: nums = [3, 2, 4] with k = 2.
  2. The row is every cap the answer could be, from the largest single number (4) up to the total sum (9).
  3. A cell shows how many pieces the greedy split needs at that cap, and stays blank until the search actually checks it.
  4. The box marks the caps still in play; start it across the whole row.
  5. Check the cap in the middle: walk the array, starting a new piece whenever adding the next number would go over the cap.
  6. If the walk fits in k pieces or fewer, that cap works — keep it and drop everything above it.
  7. If it needs more than k pieces, the cap is too tight — drop it and everything below it.
  8. When the box closes on one cap, that is the smallest cap that still works.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Binary search a cap, greedily check if it splits into k pieces
Statusinit

nums=[3,2,4], k=2. The answer is somewhere between 4 and 9, so the box starts across the whole row.

What happens in this step

lo = max(nums) = 4 (no cap can be smaller than the largest single number, because that number has to sit in some piece)
hi = sum(nums) = 9 (one giant piece always works, and it needs only 1 piece)

Nothing has been checked yet, so every cell is blank.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function splitArray(nums, k) {
  const canSplit = (cap) => {
    let pieces = 1;
    let current = 0;

    for (const num of nums) {
      if (current + num > cap) {
        pieces++;
        current = num;
      } else {
        current += num;
      }
    }

    return pieces <= k;
  };

  let lo = Math.max(...nums);
  let hi = nums.reduce((sum, num) => sum + num, 0);

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canSplit(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }

  return lo;
}
Time
O(n log(sum - max))
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [7, 2, 5, 10, 8], k = 218example from the docstring
nums = [1], k = 11smallest valid input: a single element and a single piece
nums = [1, 4, 4], k = 34k equal to the array length, so every element is its own piece
nums = [2, 3, 1, 1, 4], k = 111k = 1 forces a single piece covering the whole array
nums = [5, 5, 5, 5], k = 210uniform values that split evenly
nums = [0, 0, 0, 5], k = 25zero-valued elements that add no weight to a piece

Keep reading