Koko Eating Bananas

mediumBinary Search64 stepsJava · Python · C++

Find the smallest eating speed k so Koko finishes all piles within h hours. Higher speeds only make it easier, so the feasible speeds form a range [answer, max]. Binary search k between 1 and the largest pile, checking total hours each time.

▶ Watch the animated trace

Traced input: piles = [3, 6, 7, 11], h = 8 → 4. Original problem: neetcode.io/problems/eating-bananas

Complexity

BestO(n log m)

AverageO(n log m)

WorstO(n log m)

SpaceO(1)

m = largest pile. Each check is one pass over the piles.

Key idea

Hours at speed k: sum of ceil(pile / k).
Feasibility is monotonic: if k works, k + 1 works too.
Binary search for the first k that works.
(p + k - 1) / k is an integer ceiling.

Common mistakes

Summing hours in an int can overflow for large inputs; use long.
Upper bound must be max(piles); any faster gives the same hours.
Using float division for the ceiling.

Solution

Java

int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi) {
        int k = lo + (hi - lo) / 2;
        long hours = 0;
        for (int p : piles) hours += (p + k - 1) / k;
        if (hours <= h) hi = k;
        else lo = k + 1;
    }
    return lo;
}

Python

def minEatingSpeed(piles: List[int], h: int) -> int:
    lo, hi = 1, max(piles)
    while lo < hi:
        k = (lo + hi) // 2
        hours = sum((p + k - 1) // k for p in piles)
        if hours <= h: hi = k
        else: lo = k + 1
    return lo

C++

int minEatingSpeed(vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int k = lo + (hi - lo) / 2;
        long long hours = 0;
        for (int p : piles) hours += (p + k - 1) / k;
        if (hours <= h) hi = k;
        else lo = k + 1;
    }
    return lo;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
h equals the number of piles One hour per pile means eating the biggest pile in one hour.	`piles = [30, 11, 23, 4, 20], h = 5`	`30`
Plenty of time Speed 1 already fits.	`piles = [5, 5], h = 100`	`1`
Single pile ceil(10 / 4) = 3 hours; speed 3 would need 4.	`piles = [10], h = 3`	`4`
Huge pile (overflow check) Hours are summed in a long, so nothing overflows.	`piles = [1000000000], h = 2`	`500000000`