Very Concise 20-Lines Java Code to Binary Search Smallest Sum


  • 1
    O
        public int splitArray(int[] nums, int m) {
            int n = nums.length;
            long suml = nums[0], sumr = 0;
            for (int i = 0; i < n; 
                suml = Math.max(nums[i], suml), sumr += nums[i++]);
            
            while (suml < sumr) {
                long mid = (suml + sumr) / 2, m1 = 0;
                for (int i = 0, sumc = 0; i < n && m1 < m; sumc += nums[i++])
                    if (sumc + nums[i] > mid) {
                        m1++;
                        sumc = 0;
                    } 
                
                if (m1 < m)
                    sumr = mid;
                else
                    suml = mid + 1;
            }
            
            return (int)suml;
        }
    

Log in to reply
 

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