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

Tested only

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;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?