Problem Statement

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.

Additional information

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

Example 1:

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

Output: 4

Explanation: At speed 4:

• Pile 1 (3): 1 hour
• Pile 2 (6): 2 hours (4 + 2)
• Pile 3 (7): 2 hours (4 + 3)
• Pile 4 (11): 3 hours (4 + 4 + 3)
• Total time = 1 + 2 + 2 + 3 = 8 hours.

Example 2:

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

Output: 30

Explanation: Since h equals the number of piles, Koko must eat every pile in exactly 1 hour. The speed must be the maximum pile size (30).

Example 3:

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

Output: 23

Brute Force

Intuition
We can start checking eating speeds from k = 1 upwards. For each speed k, we calculate the total hours required to finish all piles. If the total hours are less than or equal to h, then k is our answer.

Algorithm

1. Start with speed k = 1.
2. Loop indefinitely:

• Calculate hours = 0.
• For each pile p, add ceil(p / k) to hours.
• If hours <= h, return k.
• Else, increment k.

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    speed = 1
    while True:
        hours = 0
        for p in piles:
            hours += math.ceil(p / speed)
        
        if hours <= h:
            return speed
        speed += 1

Time & Space Complexity

• Time complexity: O(n * m)

• Reason: Where m is the maximum number of bananas in a pile and n is the number of piles. In the worst case, we check every speed up to max(piles).

• Space complexity: O(1)

• Reason: Constant extra space.

Binary Search on Answer (Optimal)

Intuition
The possible values for k range from 1 to max(piles). Notice that the relationship between speed and time is monotonic: if Koko eats faster (higher k), the time taken decreases. This allows us to use Binary Search.

Instead of checking every number linearly, we pick a middle speed mid. If mid is sufficient to finish in h hours, we try a smaller speed (store mid as a potential answer and move right to mid - 1). If mid is too slow, we must increase the speed (move left to mid + 1).

Algorithm

1. Initialize l = 1 and r = max(piles).
2. Initialize res = r (worst-case answer).
3. While l <= r:

• Calculate k = (l + r) // 2.

• Calculate total hours needed at speed k: hours = sum(ceil(p / k) for p in piles). Note: Integer ceiling is (p + k - 1) // k.

• If hours <= h:

• res = k (This speed works, try to find a smaller one).

• r = k - 1.

• Else (hours > h):

• l = k + 1 (Too slow, need faster speed).

4. Return res.

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    l, r = 1, max(piles)
    res = r

    while l <= r:
        k = (l + r) // 2
        hours = 0
        for p in piles:
            # Equivalent to math.ceil(p / k)
            hours += (p + k - 1) // k
            
        if hours <= h:
            res = k
            r = k - 1
        else:
            l = k + 1
            
    return res

Time & Space Complexity

• Time complexity: O(n log m)

• Reason: The binary search range is m (max pile size), taking O(log m) steps. In each step, we iterate through the n piles.

• Space complexity: O(1)

• Reason: We only use a few variables for pointers.