Binary Search Solution with JavaScript. 100% beat


  • 0
    S

    We do binary search generally for index, but we do binary search for possible answers.

    The smallest possible solution is the maximum number in this array, and largest possible solution is the sum for all elements. So we can pick mid of smallest and largest solution and for loop to find whether it can split to m array. Keep doing this and find answer. In checkNumSubarray will return minimum split parts, this solution can reach. It can be larger than that.

    For example, [2,4,3,3], 6 can split to [2,4] [3,3] and can also split to [2],[4],[3,3].

    var splitArray = function(nums, m) {
        var sum = 0;
        var max = -Infinity;
        for(var i = 0; i < nums.length; i++){
            max = Math.max(max, nums[i]);
            sum += nums[i];
        }
        var start = max, end = sum;
        while(start < end){
            var mid = Math.floor(start + (end - start) / 2);
            if(checkNumSubarray(nums, mid) <= m){
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    };
    
    function checkNumSubarray(nums, subSum){
        var count = 1;
        var sum = 0;
        for(var i = 0; i < nums.length; i++){
            if(sum + nums[i] > subSum){
                count++;
                sum = 0;
            }
            sum += nums[i];
        }
        return count;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.