410.Split Array Largest Sum

Tags: [binary_search], [trick], [recursion], [dp]

Com: {fb}

Link: https://leetcode.com/problems/split-array-largest-sum/#/description

Given an array which consists of non-negative integers and an integerm, you can split the array intomnon-empty continuous subarrays. Write an algorithm to minimize the largest sum among thesemsubarrays.

Note:
Ifnis the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

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.

Solution: Binary Search, Trick

class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        if not nums:
            return 0
        if not m or m < 2:
            return sum(nums)

        max_elem = max(nums)
        total_sum = sum(nums)

        # the max_elem is the smallest possible result
        # the total_sum is the biggest possible result
        return self.binary_search(nums, m, max_elem, total_sum)

    def binary_search(self, nums, m, small, big):
        while small < big:
            mid = small + (big - small) / 2
            if self.is_valid(nums, m, mid):
                # here, we cannot skip mid, because mid maybe the final result.
                big = mid
            else:
                # based on the implementation of is_valid, 
                # not valid means the curr guess max sum (mid) is too small,
                # so next step, we try mid + 1.
                small = mid + 1

        # at this point, small == big.
        return small

    def is_valid(self, nums, m, max_sum):
        # check whether that is valid, if we split the nums into m parts, 
        # and the max sum among all parts is max_sum.
        # Assuming the sum of each part == max_sum, then how many parts we will have,
        # if the number of parts <= m, 
        # we define that the max_sum is valid (max_sum is valid not means the current max_sum is the final result),
        # the max_sum is valid, means next step we can try a smaller max_sum.
        num_of_parts = 0
        curr_sum = 0
        for num in nums:
            curr_sum += num
            if curr_sum > max_sum:
                num_of_parts += 1
                curr_sum = num

            if num_of_parts > m:
                return False

        # remember count the last part.
        num_of_parts += 1
        return num_of_parts <= m

Revelation:

• Because all numbers are non-negative integer, so we know the possible max sum is sum(nums), and the possible minimum sum is max(nums). If there exist negative number, the above assumption is not correct. Once we know the possible min sum and possible max sum, we can using binary search to try to find the final result.

Note:

• Time complexity = O(n + n + lg(sum(nums) - max(nums)) * n) = O(nlg(sum(nums) - max(nums))), n is the number of elements of the given array.
• Space complexity = O(1).

Time Exceeded Limited: Recursion

class Solution(object):

    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        if not nums:
            return 0
        if not m or m < 2:
            return sum(nums)

        left_sum = [0 for _ in xrange(len(nums))]
        left_sum[0] = nums[0]
        for i in xrange(1, len(nums)):
            left_sum[i] += left_sum[i - 1] + nums[i]

        return self.split_arr_helper(nums, m, 0, left_sum)

    def split_arr_helper(self, nums, m, start, left_sum):
        # base case
        if m == 1:
            sub_sum = left_sum[-1]
            if start - 1 >= 0:
                sub_sum -= left_sum[start - 1]

            return sub_sum

        if start >= len(nums):
            return -1

        min_sum = sys.maxint
        for i in xrange(start, len(nums)):
            curr_sub_sum = left_sum[i]
            if start - 1 >= 0:
                curr_sub_sum -= left_sum[start - 1]

            remaining_min_sub_sum = self.split_arr_helper(nums, m - 1, i + 1, left_sum)
            if remaining_min_sub_sum < 0:
                break

            min_sum = min(min_sum, max(curr_sub_sum, remaining_min_sub_sum))

        return min_sum

Revelation:

• Each time, just decide how to cut (partition) the first part.
• The above algorithm is correct not just for non-negative integers, it fit for all kinds of integers.

Note:

• Time complexity = O(n!), n is the number of elements of the given array.

Time Limited Exceeded: DP, Top To Bottom DP

class Solution(object):

    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        if not nums:
            return 0
        if not m or m < 2:
            return sum(nums)

        left_sum = [0 for _ in xrange(len(nums))]
        left_sum[0] = nums[0]
        for i in xrange(1, len(nums)):
            left_sum[i] += left_sum[i - 1] + nums[i]

        memo = {}
        return self.split_arr_helper(nums, m, 0, left_sum, memo)

    def split_arr_helper(self, nums, m, start, left_sum, memo):
        state = '{}->{}'.format(m, start)
        if state in memo:
            return memo[state]

        # base case
        if m == 1:
            sub_sum = left_sum[-1]
            if start - 1 >= 0:
                sub_sum -= left_sum[start - 1]

            memo[state] = sub_sum
            return sub_sum

        if start >= len(nums):
            memo[state] = -1
            return -1

        min_sum = sys.maxint
        for i in xrange(start, len(nums)):
            curr_sub_sum = left_sum[i]
            if start - 1 >= 0:
                curr_sub_sum -= left_sum[start - 1]

            if curr_sub_sum >= left_sum[-1] - curr_sub_sum:
                if m - 1 <= len(nums) - (i + 1):
                    min_sum = min(min_sum, curr_sub_sum)
                break

            remaining_min_sub_sum = self.split_arr_helper(nums, m - 1, i + 1, left_sum, memo)
            if remaining_min_sub_sum < 0:
                break

            min_sum = min(min_sum, max(curr_sub_sum, remaining_min_sub_sum))

        memo[state] = min_sum
        return min_sum

Question:

• Not sure is there the overlapping computation?