Skip to content

875. Koko Eating Bananas

Medium

Description

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

  • 1 <= piles.length <= 10โด
  • piles.length <= h <= 10โน
  • 1 <= piles[i] <= 10โน

Solutions ๐Ÿ”’

Time complexity: \(O(n \log M)\)

Space complexity: \(O(1)\)

Algorithm Template

Modified Binary search: For greedy problems

Case: Problem Function is monotonically decreasing

  • If looking for a minimum
  def fn(arr):

    def check(x): # this function is implemented depending on the problem
        return BOOLEAN

    left = MINIMUM_POSSIBLE_ANSWER
    right = MAXIMUM_POSSIBLE_ANSWER

    while left <= right:
        mid = (left + right) // 2

        if check(mid):
            right = mid - 1
        else:
            left = mid + 1

    return left

Way 1: Algorithmic

Algorithm

We notice that if Koko can eat all the bananas at a speed of k within h hours, then she can also eat all the bananas at a speed of k1 > k within h hours. This shows monotonicity, so we can use binary search to find the smallest k that satisfies the condition.

We define the left boundary of the binary search as \(L=1\) and the right boundary as \(R=max(piles)\).

For each binary search, we take the middle value \(mid= (L+R)//2\), and then calculate the time t required to eat bananas at a speed of \(mid\).

If \(tโ‰คh\), it means that the speed of \(mid\) can meet the condition, and we update the right boundary \(R\) to \(mid\);

otherwise, we update the left boundary \(L\) to \(mid+1\).

Finally, when \(L==R\), we find the smallest k that satisfies the condition.

The time complexity is \(O(n \log M)\), where \(n\) and \(M\) are the length and maximum value of the array piles respectively. The space complexity is \(O(1)\).

from math import ceil

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:

        L , R = 1 , max(piles)                      # L & R are the min & max speed (numbers , not indices) to finish/eat array piles
        ans = R                                     # We are trying to minimize ans (rate of eating)

        while L < R:
            mid = (L+R)//2                          # mid, average speed of koko eating

            t = sum(ceil(x/mid) for x in piles)     # total time to eat each pile at speed mid at loose bound

            if t<=h:                                # when the total time `t` approaches `h` we are sure we found a minimum speed `mid` and store it.
                ans = min(ans,mid)
                R = mid
            else:
                L = mid+1

        return ans # L
equivalency 
t = sum(ceil(x/mid) for x in piles)
            ||
        equivalent
            ||
t = sum((x + mid - 1) // mid for x in piles)

Note

We are applying Binary search on speed array K = [1......max(piles)] i.e K= [1,2,3,4,5,6,7,8,9,10,11] when piles = [3,6,7,11]

\(Speed = Banana/Time\)

\(F(Speed)\) is monotonically decresing so update \(R\) towards \(mid\) when LESS THAN CONDITION

Way 2: Pythonic

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def check(k: int) -> bool:
            return sum((x + k - 1) // k for x in piles) <= h

        return 1 + bisect_left(range(1, max(piles) + 1), True, key=check)
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments