unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 410: Split Array Largest Sum

link

Time: \mathcal{O}(n^k), space: \mathcal{O}(k)

class Solution:
    def explore(self, nums: List[int], k: int, groups: List[List[int]], next_start: int) -> float:
        def get_max_group_sum(groups: List[List[int]]) -> int:
            return max( sum(g) for g in groups )
        
        n = len(nums)
        if len(groups) == k:
            return get_max_group_sum(groups)
        
        remaining_count = k-len(groups)
        if remaining_count == 1:
            return self.explore(nums, k, groups + [ nums[next_start:] ], n)

        min_max_group_sum = float('inf')
        for i in range(next_start, n - remaining_count + 1):
            if (s := self.explore(nums, k, groups + [nums[next_start:i+1]], i+1)) < min_max_group_sum:
                min_max_group_sum = s
        return min_max_group_sum


    def splitArray(self, nums: List[int], k: int) -> int:
        return self.explore(nums, k, [], 0)

Observations:

  1. Given a split’s max allowed sum, as we increase max_allowed sum from max(nums) to sum(nums), can_split(max_allowed_sum) evaluates like: False, False, False, True, True, … We want the max_allowed_sum for the left-most True.
  2. Given a split’s max_allowed_sum, if we can split nums into 3 subarrays, we can also split nums into 4 or more subarrays by splitting a subarray.

Time: \mathcal{O}(n \cdot \lg{s}), space: \mathcal{O}(1).

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def can_split(max_sum):
            split_count = 0
            split_sum = 0
            for x in nums:
                split_sum += x
                if split_sum > max_sum:
                    split_count += 1
                    split_sum = x
            
            return split_count+1 <= k
        
        lo, hi = max(nums), sum(nums)
        while lo <= hi:
            mid = (lo + hi) // 2
            if can_split(mid):
                hi = mid-1
            else:
                lo = mid+1
        
        return lo

tanvirdotzaman

Leave a comment