GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #410 - Split Array Largest Sum - LeetCode JavaScript Solutions

#410 - Split Array Largest Sum

Hard • View on LeetCode • View on GitHub

Array Dynamic Programming Greedy Binary Search Prefix Sum

Problem Description

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function(nums, k) {
  let left = Math.max(...nums);
  let right = nums.reduce((a, b) => a + b);

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    let count = 1;
    let sum = 0;

    for (const num of nums) {
      if (sum + num <= mid) {
        sum += num;
      } else {
        count++;
        sum = num;
      }
    }

    if (count > k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
};

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.