Split Array Largest Sum [LeetCode #410].md

Split Array Largest Sum [LeetCode #410]

Problem

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.

---

Goal

Among all subarrays, there exists a maximum sum. Our goal is to optimize the splitting, such that the maximum sum has the smallest value.

Binary Search

Let's denote the maximum sum as max_sum, and the length of nums as n.

• The smallest value we can get for max_sum is max(nums), in which m = n, that the array nums is splitted into n parts, and each part contains only 1 item.
• The largest value we can get for max_sum is sum(nums), in which m = 1. As a result, max_sum will always be in this range.
  

To start the binary search, let's initialize the left bound and the right bound as left = max(nums) and right = sum(nums).

We need to narrow the range to get the value of max_sum given a particular m. Assume that we pick a mid value, denoted as mid, and begin to split the array nums such that the sum of each subarray is less than or equal to the value of mid. We count the number of subarrays and denote it as n_subs:

• If n_subs > m, this means that the mid we pick is too small. We could solve this by increasing the value of left such that left = mid+1.
• If n_subs < m, this means that the mid we pick is too large, that the array nums cannot be splitted into m subarrays. In this case, we could decrease the value of right to mid-1

Example

nums = [7, 2, 5, 10, 8]
m = 2

To start, we have:

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

As long as left <= right, we need to narrow the search range. I will use enumeration to denote each loop.
[1]

mid = (10+32) // 2 = 21
subarray = [[7, 2, 5], [10, 8]]
n_subs = 2 => right = 21-1 = 20, ans = 21

[2]

mid = (10+20) // 2 = 15
subarray = [[7, 2, 5], [10], [8]]
n_subs = 3 => left = 15+1 = 16

[3]

mid = (16+20) // 2 = 18
subarray = [[7, 2, 5], [10, 8]]
n_subs = 2 => right = 18-1 = 17, ans = 18

[4]

mid = (16+17) // 2 = 16
subarray = [[7, 2, 5], [10], [8]]
n_subs = 3 => left = 16+1 = 17

[5]

mid = (17+17) // 2 = 17
subarray = [[7, 2, 5], [10], [8]]
n_subs = 3 => left = 17+1 = 18
left > right => break loop

Code

def splitArray(self, nums, m):
    def calc_sub(largest):
        curr_sum, n_subs = 0, 1
        for n in nums:
            curr_sum += n
            if curr_sum > largest:
                n_subs += 1
                curr_sum = n
        return n_subs

    left, right = max(nums), sum(nums)
    ans = 0
    
    while left <= right:
        mid = (left + right) // 2
        if calc_sub(mid) > m:
            left = mid+1
        else:
            right = mid-1
            ans = mid

    return ans