AlgoVisual - Interactive Algorithm Visualization

LeetCode: https://leetcode.com/problems/split-array-largest-sum/

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

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

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

Min-Subarray-Sum Split