Koko Eating Bananas

Find the slowest eating speed that finishes all piles within the time limit.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Koko Eating Bananas: Binary-search the first speed whose ceiling-division total is at most 8 hours.

Input and goalFind the slowest eating speed that finishes all piles within the time limit.

Test the initial midpointInitialize left=1 and right=max(piles)=11, then test speed floor((1+11)/2)=6. Hours are 1+1+2+2=6, so 6 <= 8 and right becomes 6.

left1021324354speed65768798109right1110

inputpiles [3,6,7,11], hours 8testedk=6: ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)=1+1+2+2=6decision6 <= 8: right = 6

Recognize it

The answer is numeric, bounded from 1 to max(piles), and feasibility changes only once: if speed k finishes in time, every faster speed also finishes.

Keep true

The minimum feasible speed always remains in inclusive [left, right]. An infeasible midpoint and every slower speed are removed; a feasible midpoint is retained as right.

Reuse it

For capacity, rate, and threshold problems, define a monotone yes/no test, choose bounds that contain the answer, and retain the midpoint on the side that may hold the first true value.

Pattern: Binary search on the answer.

Simple idea: Try a speed. If it is fast enough, a faster speed is also fast enough. This creates one false-to-true boundary. Search for the first true speed.

def min_eating_speed(piles: list[int], hours: int) -> int:
   left, right = 1, max(piles)

   while left < right:
      speed = (left + right) // 2
      time = sum((pile + speed - 1) // speed for pile in piles)
      if time <= hours:
         right = speed
      else:
         left = speed + 1
   return left

Cost: $O(n\log m)$ time and $O(1)$ space, where $m$ is the largest pile.