Koko Eating Bananas

Koko Eating Bananas looks like a math puzzle, but it is really a disguised binary search — the trick is realizing you can search the answer itself instead of the input.

The slow way first

The brute force: try every speed k = 1, 2, 3, … up to the largest pile. For each k, add up the hours and stop at the first speed that fits in h. Computing hours for one speed is O(n), and there are up to max(piles) speeds, so this is O(n · max(piles)) — far too slow when piles hold billions of bananas.

The question to ask: is there structure I can exploit? Yes — faster is always feasible. If speed k finishes in time, so does every speed above it. The feasibility test flips from "no" to "yes" exactly once as k grows. That monotonic boundary is the signature of binary search.

The idea: binary search on the answer

Don't search the array — search the range of possible speeds, 1 … max(piles). For a candidate mid, ask one yes/no question: can Koko finish at speed mid? Compute hours = sum(ceil(p / mid)).

• If hours <= h, speed mid works, but a slower one might too → keep the left half (hi = mid).
• If hours > h, mid is too slow → discard it and everything below (lo = mid + 1).

The loop shrinks [lo, hi] until they meet. Because we always pull hi down to the slowest speed that still works, the value they converge on is the minimum.

Walk through it

Step through the animation. The cells are candidate speeds 1 … 11 (the biggest pile is 11). lo, mid, and hi bracket the live range. At mid = 6 hours are 5 ≤ 8, so we keep 1…6. At mid = 3 hours are 10 > 8, so we jump up to 4…6. Then mid = 5 works and mid = 4 works, pulling hi down to 4 — where lo and hi finally meet. Answer: 4.

Pseudocode

lo = 1, hi = max(piles)            # smallest and largest possible speed
while lo < hi:
    mid = (lo + hi) // 2
    if hours_needed(piles, mid) <= h:
        hi = mid                   # feasible: this could be the answer, look slower
    else:
        lo = mid + 1               # too slow: must go faster
return lo                          # lo == hi == the minimum speed
 
hours_needed(piles, k):
    return sum( ceil(pile / k) for each pile )   # each pile takes ceil(pile/k) hours

The Python solution

import math
 
def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(piles, mid) <= h:
            hi = mid          # mid works, try slower
        else:
            lo = mid + 1      # too slow, go faster
    return lo
 
def hours(piles, k):
    return sum(math.ceil(p / k) for p in piles)

• lo, hi = 1, max(piles) brackets every speed worth trying — eating faster than the biggest pile never helps.
• The loop condition is lo < hi (not <=): we are converging a range to a single point, not hunting for a specific value.
• hours(piles, mid) <= h is the feasibility test. math.ceil(p / k) is the hours for one pile, since a partial pile still costs a whole hour.
• On feasible we set hi = mid (not mid - 1) — mid might be the answer, so we keep it in the range.
• When lo == hi the loop exits and that shared value is the smallest feasible speed.

Complexity

We replace a linear scan over speeds with a binary search, turning max(piles) into log max(piles). Each feasibility check is still O(n) to sum the piles, so the total is O(n · log max(piles)) with only O(1) extra space.

When this pattern shows up

Practice