# 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 < 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.

• Thanks for the edit @200_success May 28, 2019 at 16:32

# (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.

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