Here is solutions for Koko Eating Bananas.

1. Understand the Problem

Koko has n piles of bananas. She eats at a fixed speed k bananas/hour.

She has h hours to finish all the piles.

• 🥇 Goal → Find the minimum integer speed k (bananas/hour) such that Koko can finish eating all bananas within h hours.

2. Clarify 3 - 4 Constraints

1. Are pile values sorted? → No.

2. Is h always ≥ number of piles? → Yes.

3. Can she not split piles? → She can only eat from one pile at a time, but partially (ceil).

4. What happens if pile size is smaller than k? → She still takes 1 hour.

3. Explore examples

• Example 1:

piles = [3,6,7,11], h = 8
Possible speeds:
k = 4 → hours = 1 + 2 + 2 + 3 = 8 → ✔ valid
k = 3 → hours = 1 + 2 + 3 + 4 = 10 → ❌ too slow
Answer: 4

• Example 2:

piles = [30,11,23,4,20], h = 5 → Answer: 30

4. Brainstorm 2-3 solutions

4.1. Solution 1: Try all speeds from 1 to max(pile) - O(10^9)

• Worst-case: 10^9 possibilities → ❌ too slow

4.2. Solution 2 (Best): Binary Search over Speed - O(N * log(max_pile - 1))

• Minimum speed = 1

• Maximum speed = max(piles)

• For a speed k, compute total hours required:

total_hours = sum(ceil(pile / k))

=> If total_hours <= h → try smaller speed. If total_hours > h → increase speed

=> We need to check with the speed A, do monkey can completed n piles.

5. Implement solutions

5.1. Brute Force (strat with speed = 1, increase until match) - O(N * max_pile)

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        speed = 1
        while True:
            totalTime = 0
            for pile in piles:
                totalTime += math.ceil(pile / speed)

            if totalTime <= h:
                return speed
            speed += 1
        return speed

• Time: O(N * max_pile).

• Space: O(1)

5.2. Binary Search - O(N * log(max_pile))

• Idea: find the lower_bound totalTime <= hour.

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

            totalTime = 0
            for p in piles:
                totalTime += math.ceil(float(p) / k)
            if totalTime <= h:
                res = k
                r = k - 1
            else:
                l = k + 1
        return res

• Time: O(N * log(max_pile)).

• Space: O(1)