Koko Eating Bananas

How it works

Instead of checking every speed one by one, we notice that the total time needed decreases as the eating speed increases. This means the answer lies in a sorted search space from 1 to max(piles).

Because the search space is ordered, we can use binary search to efficiently find the smallest speed that allows finishing the piles within h hours.

Steps

1. Set the search range:
   • left = 1 (minimum possible speed)
   • right = max(piles) (maximum needed speed)
2. While left <= right:
   • Let mid be the current speed to test.
   • Compute the total hours needed using this speed.
3. If the total hours is within the allowed time h:
   • This speed works, so record it.
   • Try to find a smaller working speed by searching the left half.
4. Otherwise:
   • Speed is too slow, so search in the right half.
5. After the search ends, return the smallest valid speed found.

Complexity

• Time complexity: O(n * log m)
• Space complexity: O(1)

Where n is the length of the input array piles and m is the maximum number of bananas in a pile.

Things to watch for

Using Integer Division Instead of Ceiling

When calculating hours needed per pile, you must round up since Koko spends a full hour even if fewer bananas remain. Using regular integer division gives wrong results.

Setting Wrong Binary Search Bounds

The minimum speed is 1 (not 0, which would cause division by zero). The maximum speed needed is max(piles) since eating faster than the largest pile provides no benefit.

Integer Overflow in Total Time

When summing hours across all piles, the total can exceed 32-bit integer limits for large inputs. Use a long integer type in languages like Java/C++.

from typing import List
import math

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

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1;
        int r = *max_element(piles.begin(), piles.end());
        int res = r;

        while (l <= r) {
            int k = (l + r) / 2;

            long long totalTime = 0;
            for (int p : piles) {
                totalTime += ceil(static_cast<double>(p) / k);
            }
            if (totalTime <= h) {
                res = k;
                r = k - 1;
            } else {
                l = k + 1;
            }
        }
        return res;
    }
};