Split an array into m subarrays such that the largest subarray sum is minimized 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 &lt; 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] &gt; n:
                return False
            current += nums[i]
            if current &gt; n:
                current = nums[i]
                count += 1
        if count &gt; 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 &lt;= high to low + 1 &lt; 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))
&gt;&gt;&gt; 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.
(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] &gt; n: becomes if num &gt; 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.