Skip to content

410. Split Array Largest Sum

Array Binary Search Dynamic Programming Greedy Prefix Sum

Problem - Split Array Largest Sum

Hard

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

 

Example 1:

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= k <= min(50, nums.length)

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:

        def checker(max_val):
            sum_val = inf
            count = 0
            for val in nums:
                sum_val += val
                if sum_val > max_val:
                    sum_val = val
                    count += 1
            return count <= k

        left, right = max(nums), sum(nums)
        # return left + bisect_left(range(left, right + 1), True, key=checker)
        while right > left:
            mid = (left + right) // 2
            if checker(mid): # Can split the array
                right = mid
            else:
                left = mid + 1

        return left

Submission Stats:

  • Runtime: 2 ms (71.50%)
  • Memory: 18 MB (41.70%)