Skip to content
AlgoVisual

Min-Subarray-Sum Split

LeetCode

01 · Question

Given a non-empty array with n positive integers, arr, and a number k with 1 <= k <= n, the goal is to split arr into k non-empty subarrays so that the largest sum across all subarrays is minimized. Return the largest sum across all k subarrays after making it as small as possible. Each subarray must contain at least one value.

Example 1:

  • Input: arr = [10, 5, 8, 9, 11], k = 3
  • Output: 17 (Split: [10, 5], [8, 9], [11]. Sums: 15, 17, 11. Max: 17)

Example 2:

  • Input: arr = [10, 10, 10, 10, 10], k = 2
  • Output: 30

02 · Solution

Reference solution

1def splitArray(nums: List[int], k: int) -> int:
2    def canSplit(max_sum):
3        count = 1
4        current_sum = 0
5        for num in nums:
6            if current_sum + num > max_sum:
7                count += 1
8                current_sum = num
9            else:
10                current_sum += num
11        return count <= k
12

13    l, r = max(nums), sum(nums)
14    while l < r:
15        mid = (l + r) // 2
16        if canSplit(mid):
17            r = mid
18        else:
19            l = mid + 1
20    return l
Previous
Search in Huge Array
Next
Water Refilling