Koko Eating Bananas

The question behind the question

Koko picks one eating speed k (bananas per hour) and keeps it fixed. Each hour she clears at most k bananas from a single pile; a pile smaller than k still costs a full hour. I want the smallest k that finishes every pile within h hours.

The thing to notice is the input I'm searching over. The piles are unsorted, so nothing useful comes from binary searching them. The speed is what I search.

Brute force, then the cut

The obvious version tries every speed from 1 up to max(piles) and returns the first one that fits in h hours. Checking a speed costs O(n), so that's O(n * max(piles)): too slow when piles are large.

The cut: feasibility is monotonic in k. A faster speed never takes more hours, so the set of "works" speeds is a contiguous tail. I binary search the speed range [1, max(piles)] and shrink toward the smallest speed that still fits.

Hours at speed k for one pile is a ceiling division: (pile + k - 1) // k.

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_needed(speed: int) -> int:
        return sum((pile + speed - 1) // speed for pile in piles)
 
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if hours_needed(mid) <= h:
            high = mid          # mid works; it might be the answer, keep it
        else:
            low = mid + 1       # too slow, need more speed
    return low

Why it lands on the answer

The loop keeps the invariant that high is always a speed that finishes in time and low is the lowest candidate still in play. When low == high, that single value is both feasible and minimal, so I return it. I never move high past a working speed, and I never keep a speed I've proven too slow.

The search runs O(log m) iterations where m = max(piles), and each feasibility check is O(n). That gives O(n log m) time and O(1) extra space.