Split Array Largest Sum Hard 0 attempts
LeetCode ↗

Split Array Largest Sum

Hard Sorting&Searching LeetCode

Given an array and integer k, split the array into k non-empty subarrays to minimize the largest sum among them.

Example: nums = [7,2,5,10,8], k = 2 → Output: 18

Sample Input
—
Sample Output
—
Constraints
  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= min(50, nums.length)
Test Cases
Case 1
Args: [[7,2,5,10,8],2] Expected: 18
Topics
Sorting&Searching

Binary Search on Answer

function splitArray(nums, k) {
  let lo = Math.max(...nums), hi = nums.reduce((a,b)=>a+b,0);
  while (lo < hi) {
    const mid = (lo+hi)>>1;
    let splits = 1, sum = 0;
    for (const n of nums) { if (sum+n>mid) { splits++; sum=n; } else sum+=n; }
    if (splits <= k) hi = mid; else lo = mid+1;
  }
  return lo;
}

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

Saved in this browser only. Private to you.

JavaScript