{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Koko Eating Bananas – Solution & Complexity

Interview solutions
/
Koko Eating Bananas

Solution Walkthrough

  1. Step 1: Recognize a monotonic predicate

    • Define feasible(k) = "Koko finishes within h hours at speed k".
    • If a speed works, every larger speed also works, and if a speed fails, every smaller speed also fails.
    • That monotonic yes/no boundary is the hallmark of binary-searching the answer rather than a sorted array.

  2. Step 2: Compute hours at a given speed

    • At speed k, a pile of p bananas takes ceil(p / k) hours because only one pile is eaten per hour.
    • Sum ceil(p / k) over all piles; the speed is feasible when that total is <= h.
    • Use integer math: ceil(p / k) is (p + k - 1) / k with integer division.

  3. Step 3: Bound the search

    • The slowest sensible speed is 1 banana per hour.
    • The fastest useful speed is max(piles): going faster never reduces the hour count below one pile per hour.
    • So the answer lies in [1, max(piles)].

  4. Step 4: Brute-force baseline

    • Try speeds 1, 2, 3, ... and stop at the first feasible one.
    • Correct but up to O(max(piles) * n) time — fine as a reference, too slow for the largest inputs.
    import math

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_at(k: int) -> int:
        return sum(math.ceil(p / k) for p in piles)

    k = 1
    while hours_at(k) > h:
        k += 1
    return k

  5. Step 5: Binary search the speed

    • Search the boundary in [1, max(piles)].
    • When mid is feasible, it might still be too fast, so keep it and move hi down to mid.
    • When mid is infeasible, discard it and everything slower by setting lo = mid + 1.
    • The loop converges on the smallest feasible speed.
    import math

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_at(k: int) -> int:
        return sum(math.ceil(p / k) for p in piles)

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_at(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

  6. Step 6: Common mistakes

    • Using floating-point division and round instead of a true ceiling — off-by-one hours creep in.
    • Setting hi = mid - 1 when mid is feasible, which can skip the real answer.
    • Starting hi above max(piles), which still works but wastes iterations.

FAQ

See also

Practice Koko Eating Bananas online (run code in the browser)Binary Search solution (easy)Find Minimum in Rotated Sorted Array solution (medium)Longest Increasing Subsequence solution (hard)Median of Two Sorted Arrays solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?