0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the edit @200_success \$\endgroup\$ – Justin May 28 at 16:32
4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$
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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.