## DEV Community is a community of 638,230 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

# LeetCode 410. Split Array Largest Sum (javascript solution)

### Description:

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

### Solution:

Time Complexity : O(nlog(n))
Space Complexity: O(1)

``````// Binary Search approach
var splitArray = function(nums, m) {
// Check if the passed in threshold can be the max sum of the subarrays
function checkIsFeasable (threshold) {
let count = 1
let total = 0
for (const num of nums){
total += num
if (total > threshold){
total = num
count += 1
if (count > m){
return false
}
}

}
return true
}
// Binary search template
let left = Math.max(...nums), right = nums.reduce((all, item) => all+item)
while(left < right) {
const mid = left + Math.floor((right-left)/2)
if(checkIsFeasable(mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
};
``````