Course4all
Join us on telegram
Home/dsa/Binary Search/Koko Eating Bananas

Koko Eating Bananas

Master this topic with zero to advance depth.

Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards will come back in h hours. Koko can decide her bananas-per-hour eating speed 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. Return the minimum integer k such that she can eat all the bananas within h hours.

Medium

Examples

Input: piles = [3,6,7,11], h = 8
Output: 4
Approach 1

Level I: Brute Force

Intuition

Try every speed k starting from 1 upwards until we find one that allows Koko to finish in h hours.

⏱ $O(Max(Piles) \cdot N)$💾 $O(1)$

Detailed Dry Run

piles=[3,6,7,11], h=8. Try k=1, 2, 3... until 4 fits.

java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        for (int k = 1; ; k++) {
            long hours = 0;
            for (int p : piles) hours += (p + k - 1) / k;
            if (hours <= h) return k;
        }
    }
}
Approach 2

Level III: Optimal (Binary Search on Answer)

Intuition

The time spent eating is a monotonic function of the speed k. We can binary search in the range [1, max(piles)].

⏱ $O(N \cdot \log(Max))$💾 $O(1)$

Detailed Dry Run

piles=[3,6,7,11], h=8. L=1, R=11.

  • Mid 6: 1+1+2+2 = 6 <= 8. R=6.
  • Mid 3: 1+2+3+4 = 10 > 8. L=4.
  • Mid 5: 1+2+2+3 = 8 <= 8. R=5.
  • Mid 4: 1+2+2+3 = 8 <= 8. R=4. Result 4.
java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = 1000000000;
        for (int p : piles) if (p > r) r = p;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (canFinish(piles, h, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    private boolean canFinish(int[] piles, int h, int k) {
        long total = 0;
        for (int p : piles) total += (p + k - 1) / k;
        return total <= h;
    }
}
← Previous QuestionFind the Smallest Divisor Given a Threshold
Next Question →Longest Increasing Subsequence