Koko Eating Bananas

Share

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. Find the minimum eating speed k such that Koko can eat all 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

Solution Approach

Binary search on the answer: search speed k in range [1, max(piles)]. For a given k, compute hours needed = sum(ceil(pile/k)). If hours <= h, try smaller k.

  • lo=1, hi=max(piles).
  • For each mid speed, compute total hours needed.
  • If hours <= h: possible, try smaller (hi=mid).
  • Else: too slow, increase speed (lo=mid+1).
Java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1, hi = 0;
        for (int p : piles) hi = Math.max(hi, p);
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            long hours = 0;
            for (int p : piles) hours += (p + mid - 1) / mid;
            if (hours <= h) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}
  • Time Complexity: O(N log M) where M=max pile
  • Space Complexity: O(1)