Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Split Array Largest Sum

Problem (restated)

Split nums into m non-empty continuous subarrays to minimize the largest subarray sum.

Intuition

Feasibility is monotonic in the allowed max sum. binary search the answer.

Approaches

Binary search on max sum

Unverified

Time O(n log S)Space O(1)

Idea. lo=max(nums), hi=sum(nums). canSplit(mid): greedy count pieces needed ≤ m.

Walkthrough. [7,2,5,10,8], m=2 → answer 18 ([7,2,5] and [10,8]).

Trade-offs. DP is O(n²m); BS-on-answer is cleaner for interviews.

Solution

export function splitArray(nums: number[], m: number): number {
  let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let pieces = 1, load = 0;
    for (const x of nums) {
      if (load + x > cap) { pieces++; load = 0; }
      load += x;
    }
    return pieces <= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

export function splitArray(nums: number[], m: number): number {
  let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let pieces = 1, load = 0;
    for (const x of nums) {
      if (load + x > cap) { pieces++; load = 0; }
      load += x;
    }
    return pieces <= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

Template connection

Binary search on the maximum load; greedy split-count is the feasibility check.

Reflection

“Minimize the largest piece sum” is monotone: a larger capacity eventually fits in m pieces. Why is lo = max(nums)?
feasible(cap) counts pieces in one pass. More than m pieces means the capacity is too small.
The ends: m = 1 is the whole array, and m = n is one element per piece.