Problem Statement in English

There are n piles of bananas. Each pile has piles[i] bananas.

Koko can eat k bananas per hour. However, once she starts on a pile, even if she finishes the pile before the hour is up, she waits until the next hour to start on the next pile.

You have to calculate a minimal k so that she’s able to eat all the bananas within h hours. She clearly likes to relish her food.

Approach

You’re probably thinking, how about I work my way up from the minimum number of bananas that she can eat per hour - 1 (eating 0 bananas per hour is a scam), and keep going until Koko is able to eat all the bananas within h hours?

That would work. But let’s look at the constraints provided:

  • there can be upto a billion bananas in piles[i]
  • h <= a billion
  • there can be upto 10k piles

So we’ve found the catch. You are not brute forcing this problem. It can send you on a really long wild goose chase.

Let’s figure out how to manage the scale later. For now let’s break this down into smaller steps. Make it less daunting.

Step 1: Calculate if a k allows Koko to eat piles within h hours

  • Step 1.1: Calculate hours taken to eat piles[i] for a given k
    It’s easier to explain this with an example.

Let’s say you have piles[i] = 5 bananas, and k = 2. Then you’d need 3 hours right? 1 hour for the first 2, 1 hour for the next 2, and 1 hour for the last one.

So all you really need to do is ceil(piles[i]/k). This gives you the amount

  • Step 1.2: Calculate hours taken to eat piles for a given k
    This is easy, you just need to sum up the hours taken for every piles[i]

Step 2: The scale

Here’s the thing, we know the lowest and highest value that k can take.

1 <= k <= max(piles)

You will always be able to eat all piles within h hours, if your k = the number of bananas in the biggest pile. Think about it.

Yea?

Our solution space is therefore [1, max(piles)].

So…how about we cut down our search space, by applying binary search?

Here’s how we move the pointers:

  • if a particular k value allows Koko to finish the piles with the deadline, then we should try a lower value for k (right = mid - 1)

  • if a particular k value results in Koko not finishing the piles within the deadline, we need to go higher (left = mid + 1)

Solution in Python


from math import ceil

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        res = r

        while l <= r:
            k = (l + r) // 2
            hours = 0

            for pile in piles:
                hours += ceil(pile / k)

            if hours <= h:
                res = min(k, res)
                r = k - 1
            else:
                l = k + 1
        return res

Complexity

  • Time: $O(nlogn)$
    This is is because we search the solution space with logarithmic compelxity thanks to the binary search, and on each possible solution, we iterate through piles to calculate total time taken to eat all of them.

  • Space: $O(1)$
    We don’t store much extra apart from a few integer variables.

Mistakes I Made

A really crappy binary search implementation prior to this. Hehe.

And we are done.