Split an array into m subarrays such that the largest subarray sum is minimized

Question

This is a Leetcode problem -

Given an array 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.

Note -

If n is the length of the array, assume the following constraints are satisfied:

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

Here is my solution to this challenge -

class Solution(object):

    def __init__(self, nums, m):
        self.nums = nums
        self.m = m
    def split_array(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        min_res = max(nums)
        max_res = sum(nums)
        low, high = min_res, max_res
        while low + 1 < high:
            mid = low + (high - low)//2
            if self.is_valid(nums, m, mid):
                high = mid
            else:
                low = mid
        if self.is_valid(nums, m, low):
            return low
        return high

    def is_valid(self, nums, m, n):
        count, current = 1, 0
        for i in range(len(nums)):
            if nums[i] > n:
                return False
            current += nums[i]
            if current > n:
                current = nums[i]
                count += 1
        if count > m:
            return False
        return True

Here, I just optimize the binary search method (technique used to search an element in a sorted list), change the condition of low <= high to low + 1 < high and mid = low + (high - low) / 2 in case low + high is larger than the max int.

Here is an example input/output -

output = Solution([7,2,5,10,8], 2)
print(output.split_array([7,2,5,10,8], 2))
>>> 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.

Here is the time for this output -

%timeit output.split_array([7,2,5,10,8], 2)
12.7 µs ± 512 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

So, I would like to know whether I could make this program shorter and more efficient.

Answer 1

(Sort of) Unnecessary OOP

A lot of things like LeetCode will require that the solution is in a class for likely submission reasons, but if we concern ourselves with only the task at hand, I would recommend you get rid of the class and just use functions for this. (And if get rid of the unnecessary class, you'll shorten the code, although, I wouldn't encourage you to be preoccupied with shortening your code.)

Also, if you had to keep the class (for whatever reason), observe:

def __init__(self, nums, m):
    self.nums = nums
    self.m = m

When you pass parameters like this, you can reuse them over and over again. They are sort of like pseudo-global variables. So you would need to do:

def is_valid(self, nums, m, n):

it would just be:

def is_valid(self):

and (in general) you would access self.m and self.n.

Iterate over the iterables, not over the len of the iterable.

Unless you are mutating nums (which I don't believe you are) the more idiomatic way of doing this is iterating through the iterable so:

for i in range(len(nums)):

becomes:

for num in nums:

and instances of nums[i] are replaced by num, for example if nums[i] > n: becomes if num > n:.

Side note: if you were to need the value i and nums[i], you might want to consider utilizing enumerate if you need both.

Answer 2

if nums[i] > n:
    return False

This is unnecesary, you are starting the binary search with max(nums) as minimum, so n will always be at leat equal to max nums[i].

Why is both your constructor and split_array method taking in the parameters of the problem? Either only take them on constructor or make split_array a static method without using constructor.

Why you have min_res and max_res? Either use those in the binary search or just replace them with low and high, no reason to have both those and low/high variables.

If you keep an array of accumulated sums of the array you can change is_valid to do binary search to find the index of the next group. This would change complexity from O(|n| * log(sum(n))) to O(m * log(|n|) * log(sum(n))). For such small amount of n, this is probably not worth doing in this case but its definitly better if you have small m and big n. Instead of reimplementing binary search for this, you could actually use bisect