410-split-array-largest-sum

Try it on leetcode

Description

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

 

Example 1:

Input: nums = [7,2,5,10,8], m = 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], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

 

Constraints:

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

Solution(Python)

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        return self.binarySearch(nums, m)

    # Time Complexity: O(n^2*m)
    # Space Complexity: O(n*m)
    def topDownDp(self, nums: List[int], m: int) -> int:
        n = len(nums)

        prefix_sum = [0] + list(itertools.accumulate(nums))

        @functools.lru_cache(None)
        def get_min_largest_split_sum(cur_index, sub_arr_cnt):
            if sub_arr_cnt == 1:
                return prefix_sum[n] - prefix_sum[cur_index]
            min_largst_sum = prefix_sum[n]

            for i in range(cur_index, n - sub_arr_cnt + 1):
                first_split_sum = prefix_sum[i + 1] - prefix_sum[cur_index]

                largest_split_sum = max(
                    first_split_sum, get_min_largest_split_sum(
                        i + 1, sub_arr_cnt - 1)
                )

                min_largst_sum = min(largest_split_sum, min_largst_sum)

                if first_split_sum >= min_largst_sum:
                    break

            return min_largst_sum

        return get_min_largest_split_sum(0, m)

    # Time Complexity: O(nlog(S))
    # Space Complexity: O(1)
    def binarySearch(self, nums: List[int], m: int) -> int:
        def min_subarrays_required(max_sum_allowed):
            cur_sum = 0
            split_req = 0

            for ele in nums:
                if cur_sum + ele <= max_sum_allowed:
                    cur_sum += ele
                else:
                    cur_sum = ele
                    split_req += 1

            return split_req + 1

        left = max(nums)
        right = sum(nums)

        while left <= right:
            max_sum_allowed = (left + right) >> 1

            if min_subarrays_required(max_sum_allowed) <= m:
                right = max_sum_allowed - 1
                minimum_largest_split_sum = max_sum_allowed
            else:
                left = max_sum_allowed + 1

        return minimum_largest_split_sum