Problem 17 · Binary Search

Koko Eating Bananas

MediumClassic DSA & systems

01Problem

Given pile sizes and h hours, find the minimum integer eating speed k so all piles are finished within h hours (one pile per hour max).

02Key insight

Binary search on the answer: feasibility (hours needed at speed k) is monotonic in k, so find the smallest feasible k in [1, max(piles)].

03Solution

solution.pypython12 lines

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours(k: int) -> int:
        return sum((p + k - 1) // k for p in piles)  # ceil division

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

Try it first.

TimeO(n log max(piles))

SpaceO(1)

tests.py · 4 passing

tests.pypython4 lines

assert min_eating_speed([3,6,7,11], 8) == 4
assert min_eating_speed([30,11,23,4,20], 5) == 30
assert min_eating_speed([30,11,23,4,20], 6) == 23
assert min_eating_speed([1], 1) == 1

04Staff-level follow-up

Where does this pattern show up in real systems? Capacity planning: minimum workers/throughput to meet an SLA, or minimum shard size to fit partitions into N nodes, whenever feasibility is monotonic.