Hard

Split Array Largest Sum

LAB

Split nums into k non-empty contiguous subarrays minimizing the largest subarray sum.

EXAMPLES

Example 1

Input
{
  "nums": [
    7,
    2,
    5,
    10,
    8
  ],
  "k": 2
}

Output
18

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

Min template. Search space: [max(nums), sum(nums)]. Check: can we split into <= k chunks where each <= mid?

Reveal reference solution +

pythonREFERENCE

def splitArray(self, nums: List[int], k: int) -> int:
    def check(max_sum):
        chunks, curr = 1, 0
        for num in nums:
            if num > max_sum:
                return False
            if curr + num > max_sum:
                chunks += 1
                curr = num
            else:
                curr += num
        return chunks <= k

    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1
    return left

TimeO(n log(sum(nums)))

SpaceO(1)

Open on LeetCode ↗