LeetCode 410. Split Array Largest Sum (javascript solution)

#algorithms #javascript

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
};