Explanation + Ruby 11-liner


  • 7

    I really like Ruby for binary search...

    def split_array(nums, m)
      (nums.max .. nums.inject(:+)).bsearch { |cap|
        subarrays = 0
        sum = cap
        nums.each { |num|
          if (sum += num) > cap
            sum = num
            subarrays += 1
          end
        }
        subarrays <= m
      }
    end
    

    If we can do it with a certain cap like 9 in the example, we can of course also do it with any larger cap. Meaning we can use binary search. And we want to know the smallest cap possible.

    For the binary search, we just need to be able to determine for a certain cap whether it's ok. Meaning whether we can split the array into m subarrays so that no subarray's sum is over this cap. To do that, we determine the minimum number of subarrays we can do with this cap. If it's smaller than or equal to m, this cap is ok. Wait, aren't we supposed to create exactly m subarrays? Yeah, but if we can do it with fewer, we can just split some up so we have exactly m.

    So how to find the minimum number of subarrays we can do with a certain cap? We can do that greedily. Of course it's smart to stuff as many numbers into the first subarray as we can - then we don't need to try to fit them into the remaining subarrays. Same for the remaining subarrays - always stuff as many numbers into them as we can, only start a new subarray when the current number doesn't still fit into the previous subarray.

    The initial range for possible caps is from the maximum in nums (because with a lower cap, we couldn't fit that number into any subarray) to the sum of nums (a larger cap would be useless - we'll never need more room than all numbers combined).


  • 3

    What's interesting about this algorithm is that its complexity is O(N lg sum), and therefore doesn't depend on m at all.


  • 0

    @SergeyTachenov Hmm, interesting. I never thought about that. And the same can be said about the binary search solution(s) for the "Kth Smallest Element in a Sorted Matrix" problem - their runtime doesn't depend on k.


  • 2

    @StefanPochmann Yeah, but it's no big surprise for kth smallest something in a sorted something. But here, if you're thinking about possible brute force solutions and ways to optimize them with DP and whatnot, you end up with huge dependence on m, because you've got lots of splitting points and trying to optimize them all at the same time is going to be very hard. But once you come to this solution and realize it doesn't depend on m at all, it's kind of amazing.

    What's even more amazing, though, is that you could arrive at this solution by giving up on trying to find the actual splitting points and concentrating on finding just the sum instead. And then, when you got it, you realize that you get the splitting points as a side effect!


  • 0

    @SergeyTachenov Did you actually try a different approach? I must admit I pretty much right away had the above idea and never tried any other, so maybe that's why I'm not that amazed, as it's the only way I know :-). After I had written mine, I btw looked at the judge's solution and later also at some of the contest leader's solutions, and I think every single one of them did this binary search approach.

    Good point in your second paragraph, that would be rather funny, if someone wanted to know the splits and arrived at them that way :-)


  • 0

    @StefanPochmann Yeah, I actually tried to find the right split by splitting it uniformly first and then fooling around with splitting points. Didn't work at all.


  • 0

    "To do that, we determine the minimum number of subarrays we can do with this cap. If it's smaller than or equal to m, this cap is ok. Wait, aren't we supposed to create exactly m subarrays? Yeah, but if we can do it with fewer, we can just split some up so we have exactly m."

    is a nice point, it makes the total problem super easy, thanks!


  • 3
    O

    But, what's bad with Python? :-)

    class Solution(object):
        def splitArray(self, nums, m):
            lo, hi = max(nums), sum(nums)
            while lo < hi:
                mid, s, cnt = (lo+hi)//2, 0, 1
                for n in nums:
                    s, cnt = [(s+n,cnt),(n,cnt+1)][s>mid]
                lo, hi = [(lo,mid),(mid+1,hi)][cnt>m]
            return lo
    

  • 0
    H

    @StefanPochmann - Very neat solution. Just a question about the greedy search. Why can't we use another binary search there as well? Wouldn't it lead us to better time complexity solution?


  • 0

    @o_sharp said in Explanation + Ruby 11-liner:

    But, what's bad with Python? :-)

                    s, cnt = [(s+n,cnt),(n,cnt+1)][s>mid]
    

    Correct me if I'm wrong, the above line should be s, cnt = [(s+n,cnt),(n,cnt+1)][s+n>mid], right?
    @o_sharp


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.