Typorithm · hard

Split Array Largest Sum

split-array-largest-sumbinary-search-answeranswer-spaceminimize-maxgreedy-count

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Split Array Largest Sum

Binary Search on Answer

Binary search the largest allowed subarray sum; greedily count pieces, minimizing the cap that fits within m subarrays.

We want to split nums into m contiguous parts, minimizing the largest part's sum.

Binary search that largest sum between the biggest element and the total.

For a candidate cap, greedily count how many pieces it forces; if at most m, the cap is feasible — search lower.

Search the max-subarray-sum cap.

Greedily count pieces under the cap.

Feasible when pieces <= m.

function splitArray(nums, m) {
  let lo = Math.max(...nums);
  let hi = nums.reduce((a, b) => a + b, 0);

  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    let pieces = 1;
    let sum = 0;
    for (const num of nums) {
      if (sum + num > mid) {
        pieces += 1;
        sum = 0;
      }
      sum += num;
    }
    if (pieces <= m) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }

  return lo;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Lower bound

The largest sum is at least the biggest single element.

let lo = Math.max(...nums)

2. Candidate cap

Binary search the allowed maximum subarray sum.

const mid = (lo + hi) >> 1

3. Cut a piece

Start a new subarray when adding would exceed the cap.

if (sum + num > mid) {
        pieces += 1;
        sum = 0;
      }

4. Few enough pieces

If it splits into at most m parts, try a smaller cap.

if (pieces <= m) {
      hi = mid;
    }

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.