Koko Eating Bananas

Medium#875search the answer

There are piles of bananas and h hours. Each hour you pick one pile and eat up to k bananas from it; if the pile has fewer, you finish it and wait for the next hour. Find the smallest whole speed k that eats every pile within h hours. Our example: piles [4, 9, 2, 13], h = 6 — the answer is 7.

875 Koko Eating BananasWalkthrough · 1×

Example: Piles [4, 9, 2, 13], h = 6. The top row is the speeds 1..13; below are the hours each pile takes at speed mid.

speed, bananas per hour12345678910111213lopiles49213hours—sum—
speed still possiblemiddle, checked nowruled outthe answer

The slowest speed is 1 banana an hour: lo = 1

01/31
restart · back · play · step
Speed
1function minEatingSpeed(piles, h):
2 lo = 1
3 hi = max(piles) // faster never helps
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 hours = 0
7 for each pile in piles:
8 hours = hours + ceil(pile / mid)
9 if hours <= h:
10 hi = mid // in time: keep mid
11 else:
12 lo = mid + 1
13 return lo
state
lo
1
hi
–
mid
–
pile
–
hours
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The faster you eat, the fewer hours it takes. So over speeds 1, 2, 3, … the checks "in time?" go no, …, no, yes, …, yes, and the answer is the first yes.
  2. A pile takes ceil(pile / speed) hours: at most speed bananas an hour, and never two piles in one hour. So a small pile still costs a whole hour, as the pile of 2 does at speed 6.
  3. If mid is in time, it may be the answer, so hi = mid keeps it. If not, every slower speed is late too: lo = mid + 1.

Complexity

Time O(n log m), where n is the number of piles and m the biggest pile: about log m speeds are tried, and each check walks over all piles. Memory O(1).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.