Python Binary Search


  • 0
    class Solution(object):
        def splitArray(self, nums, m):
            left, right = max(nums) - 1, sum(nums)
            while right - left > 1:
                mid = (left + right) >> 1
                idx, s, cnt = 0, 0, 0
                while idx < len(nums):
                    while idx < len(nums) and s + nums[idx] <= mid:
                        s += nums[idx]
                        idx += 1
                    if idx == len(nums):
                        cnt += 1
                    else:
                        cnt += 1
                        s = 0
                if  cnt <= m:
                    right = mid
                else:
                    left = mid
            return right
    

Log in to reply
 

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