Split Array Largest Sum Hard 0 attempts
LeetCode ↗

Split Array Largest Sum

Hard Sorting&Searching LeetCode

You have an array nums of non-negative integers and need to divide it into k contiguous, non-empty pieces. Each way of splitting it produces k subarray sums — choose the split that keeps the largest of those sums as small as possible, and return that minimized value.

Input Format
Implement splitArray(nums, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
nums = [7,2,5,10,8]
k = 2
Output
18

Example 2

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

Binary Search on Answer

javascript
function splitArray(nums, k) {
  let lo = Math.max(...nums), hi = nums.reduce((a,b)=>a+b,0);
  while (lo < hi) {
    const mid = Math.floor(lo + (hi-lo)/2);
    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