Leetcode Binary Search Problem Set (2) - Hard

  • 410.Split Array Largest Sum

410. Split Array Largest Sum

min largest sum in range: [max(nums), sum(nums) + 1)
Basic idea is directly search the correct answer.

Given upper bound [max_sum], calculate the number of subarray that nums need to split into [cnt]

1
2
3
4
if cnt > m:  # given max_sum is too small
    lo = max_sum + 1
else:
    hi = max_sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def splitArray(self, nums: List[int], m: int) -> int:
    
    def splitable(max_sum):
        """
        split nums into k groups, sum of each group <= max_sum
        """
        cur_sum = 0
        cnt = 1
        for n in nums:
            cur_sum += n
            if cur_sum > max_sum:
                cnt += 1
                cur_sum = n
                if cnt > m:  # max_sum too small
                    return False
        return True
    
    lo = max(nums)
    hi = sum(nums) + 1
    while lo < hi:
        max_sum = lo + (hi - lo ) // 2
        if not splitable(max_sum):
            lo = max_sum + 1
        else:
            hi = max_sum
    return lo