Koko Eating Bananas: Minimize a Feasible Rate

"Koko Eating Bananas" is a Medium-level staple in Google, Airbnb, DoorDash loops, and it is a textbook fit for the Modified Binary Search pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 8 of 11 in the Modified Binary Search arc.

The Problem

Koko has piles of bananas and h hours; each hour she eats up to k bananas from one pile. Return the minimum integer speed k that finishes all piles within h hours. The template question for minimize-the-feasible-answer, asked in this costume and a dozen others (shipping, splitting, scheduling).

Input:  piles = [3, 6, 7, 11], h = 8
Output: 4
At speed 4: 1 + 2 + 2 + 3 = 8 hours exactly.

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

Hours needed decrease as speed increases — feasibility is monotonic in k, so the minimum feasible k is a boundary. When the answer itself (not an index) has a monotonic yes/no check, search the answer space and write the checker as its own function.

The Approach

Search k in [1, max(piles)]. The checker sums ceiling(pile / k) across piles and compares against h. Feasible pulls hi down (seeking smaller); infeasible pushes lo up. Converge on the first feasible k.

Two idioms worth using: -(-p // k) or math.ceil for ceiling division, and an early-exit in the checker once hours exceed h — the latter matters when piles is long and the interviewer asks about constants.

Python Solution

def min_eating_speed(piles: list[int], h: int) -> int:
    """Minimum integer speed finishing all piles within h hours."""

    def hours_at(k: int) -> int:
        return sum(-(-p // k) for p in piles)   # ceiling division

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_at(mid) <= h:
            hi = mid                   # feasible: try slower... i.e. smaller k
        else:
            lo = mid + 1               # too slow: need more speed
    return lo

Complexity

• Time: O(n log m) — n piles checked per probe, log of max pile probes
• Space: O(1) — the checker is a streaming sum

Interview Tips and Follow-Ups

• State the search bounds with reasons: 1 (speeds below one make no progress) and max(piles) (faster than the biggest pile buys nothing).
• h is guaranteed at least the number of piles — mention why the problem needs that guarantee (each pile costs at least one hour).
• Name the family: Ship Packages (next), Split Array Largest Sum, Minimum Days for Bouquets — one template, many costumes. Interviewers reward the meta-recognition.

More Modified Binary Search problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.