Koko Eating Bananas - Leetcode Solution

Sure! Here's a detailed solution to the Koko Eating Bananas problem on LeetCode.

Problem Statement:

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 starts picking up from the next pile.

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 Input:

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

Solution:

To solve this problem we need to understand that Koko can eat at a certain speed, K bananas per hour, and we need to find the minimum possible value of K that will allow Koko to eat all the bananas within H hours.

We can use binary search to get the minimum value of K.

We know that the minimum and maximum values of K are 1 and max(piles) respectively. Therefore, we need to search in between 1 and max(piles).

We can perform a binary search of all possible K values within the range. At each iteration, we will calculate the time Koko needs to eat all the bananas for a particular value of K. If the time is less than or equal to H, the search is continued on the left side of the mid value. Otherwise, we continue on the right side of the mid value.

Finally, the minimum K will be the answer when the search is complete.

Here's the python code that implements the above solution.

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        left, right = 1, max(piles)
        while left < right:
            mid = (left + right) // 2
            time = sum((pile-1) // mid + 1 for pile in piles)
            if time > H:
                left = mid + 1
            else:
                right = mid
        return left

In this code, we first initialize the left and right values. Then we check if the left value is lesser than the right value. While left is less than right, we find the mid value.

Then, we calculate the time Koko needs to eat all the bananas at mid speed. We will check if this time is less than H. If the time is less than H, then Koko can eat at a faster speed, so we search for lower value of K. If the time is greater than H, then Koko cannot eat at such an intense speed, so we search for a higher value of K.

Finally we return the minimum speed needed by Koko to eat all the bananas within H hours.

Complexity Analysis:

Time Complexity:

The time complexity of this solution is O(n log W), where n is the number of piles and W is the maximum number of bananas in a pile. We do a binary search of all possible K values within the range, O(logW), and for each K value, we calculate the time Koko needs to eat all the bananas, which takes O(n).

Space Complexity:

The space complexity of this solution is O(1) as we use constant space to store the left, right and mid values and we calculate time on the fly.

1