< Back




875. Koko Eating Bananas

We're given a list of piles of bananas where piles[i] describes the number of bananas in the pile.
We're given a time limit, h, where we need to eat all of the bananas. We're asked to find the minimum
rate, k, at which we need to eat the bananas.

Using binary search, we kind search for the minimum rate at which we can eat all the bananas within
the given time. We do this by creating our own range, 1 to max(piles), that describes the rates we
can choose from. We binary search through this range of rates, and at each selection, we iterate
through the piles and calculate the time it would take to eat all the bananas at the selected rate.

If the time it takes to eat all the bananas at our current rate is too fast, such that t, time, is
less than our limit, h, we reduce our range by half, setting r = k. Now we can select from a slower
rate, because we're looking for the minimum. If we take too much time such that t, time, is greater
than our limit, h, we know we need to speed up the rate, setting l = k + 1.

Eventually the binary search will succeed and r will be the minimum rate at which we can eat all the
bananas within the given time.

The solution is as follows:


  from math import ceil

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

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

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

              if t <= h:
                  r = k
              else:
                  l = k + 1

          return r


_ Time Complexity:

  O(n log(m)) - Where m is the maximum number in piles and n is the nummber of piles. We binary
  search through a range of (1, m) and operate on each pile during each step of the search.

_ Space Complexity:

  O(1) - We use constant space to conduct our search.