BinarySearch 0808 Split List to Minimize Largest Sum

Problem statement

https://binarysearch.com/problems/Split-List-to-Minimize-Largest-Sum/

Solution

Equal to Leetcode 0410. Split Array Largest Sum.

Complexity

Time complexity of this approach is O(n * log(SUM)), where SUM is sum of all numbers in array. Space complexity is O(1).

Code

class Solution:
    def solve(self, nums, m):
        def check(Q):
            if max(nums) > Q: return False
            acc, ans = 0, 1
            for num in nums:
                if acc + num <= Q:
                    acc += num
                else:
                    acc = num
                    ans += 1
            return ans <= m
        
        beg, end = max(nums) - 1, sum(nums)
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid):
                end = mid
            else:
                beg = mid
        
        return end