Koko Eating Bananas

Problem

Koko has piles of bananas and h hours before the guards return. Each hour she picks one pile and eats up to k bananas from it (if the pile has fewer than k, she finishes it and stops for that hour). Find the smallest integer eating speed k that lets her finish every pile within h hours.

My notes

10 MIN00:00unlocks in 10:00

Signal

"Find the minimum/maximum value of a parameter such that some condition holds" is binary search on the answer, not on the input array. Whenever feasibility at speed k is monotonic — if k works, every larger k also works — you can binary search over k itself.

Approach

The search space is eating speed, from 1 to max(piles). For a candidate speed, compute the hours needed as the sum of ceil(pile / speed) over all piles — a feasibility check, not a full simulation. Binary search for the smallest speed whose hours-needed is <= h.

Skeleton

def hours_needed(speed):
    return sum(ceil(pile / speed) for pile in piles)

left, right = 1, max(piles)
while left < right:
    mid = (left + right) // 2
    if hours_needed(mid) <= h:
        right = mid       # feasible — try slower
    else:
        left = mid + 1    # too slow — must eat faster
return left

Solution

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_needed(speed: int) -> int:
        return sum(math.ceil(pile / speed) for pile in piles)

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if hours_needed(mid) <= h:
            right = mid
        else:
            left = mid + 1
    return left

Complexity

O(n log m) time, where n is the number of piles and m is the largest pile — each of the O(log m) binary search steps scans all n piles. O(1) space.

Pitfalls

This is a "search for the boundary" binary search (left < right, converging to a single point), not the "find an exact match" form — using left <= right with left = mid + 1 / right = mid - 1 here will loop forever or skip the answer.
pile // speed truncates instead of rounding up — you need ceiling division (math.ceil(pile / speed) or -(-pile // speed)), since any leftover bananas still cost a full hour.
The recognizable twist: the interviewer isn't asking you to search the piles, they're asking you to search the space of possible answers — spotting that reframing is the whole problem.

locked10:00 left