2.3 Allocation Problems

Demo: Split Array Largest Sum — LC 410 (Hard — Google High)

Statement (Demo): Given a non-negative integer array nums and an integer k, split the array into k contiguous non-empty subarrays so that the largest subarray sum is as small as possible. Return that sum. Example: nums=[7,2,5,10,8], k=2 → 18 | ⚡ n ≤ 1000, 1 ≤ k ≤ min(50, n), 0 ≤ nums[i] ≤ 10⁶

Approach: The answer ranges from max(nums) (one element per part) to sum(nums) (everything in one part). For each cap, greedily count how many parts are needed — if it fits in k parts, lower the cap.

function splitArray(nums, k) {
  const canSplit = (cap) => {
    let parts = 1,
      sum = 0;
    for (const x of nums) {
      if (sum + x > cap) {
        parts++;
        sum = 0;
      }
      sum += x;
    }
    return parts <= k;
  };
  let lo = Math.max(...nums),
    hi = nums.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (canSplit(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Complexity: Time O(n log sum), Space O(1)