Problem Description

Koko loves to eat bananas. There are n piles of bananas, the i-th 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

My Idea

In the worst case k has to be the largest amount of any pile. This lead me to my initial idea of trying each value from 1 till max(piles) until i find the first one, which results in a time-to-eat that is smaller than or equal to h. This yield a time complexity of O(max(piles)*n), which was too slow to pass the requirements of LeetCode. This lead me to my next idea, which was utilizing binary search to reduce the problem space. The binary search was used on the ’list’ of possible speeds k and yielded a time complexity of O(n log max(piles)).

My solution

# Time Complexiy: O(n log max(piles))
def minEatingSpeed(piles: list[int], h: int) -> int:
    l = 1
    r = max(piles)
    k=max(piles)
    while(l<=r):
        mid = (l+r) //2
        t=0
        for p in piles:
            t+= -(-p // mid)
        if t>h:
            l=mid+1
        else:
            k = min(k,mid)
            r=mid-1
    return k


# Time Complexity: O(max(piles)*n)
def minEatingSpeedInitial(piles: list[int], h: int) -> int:
    maxValue = max(piles)
    for k in range(1,maxValue+1):
        t=0
        for p in piles:
            t+= -(-p // k)
        if t<=h:
            return k