Koko Eating Bananas
Find the slowest eating speed that still finishes every pile of bananas in h hours, by binary searching over the speeds.
- Binary search on the answer
- Feasibility check
Before this, know: Classic binary search (week 3), Rounding up a division (ceiling)
Koko the gorilla has some piles of bananas, piles, and h hours before the
guards come back. She picks one eating speed k: how many bananas she eats
per hour. 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 wastes the rest of that
hour (she won’t start another pile in the same hour).
Return the smallest whole-number speed k that lets her finish every pile
within h hours.
Example: piles = [3, 6, 7, 11], h = 8. The answer is 4:
- 3
- 6
- 7
- 11
- 1
- 2
- 2
- 3
The rules that matter:
his at least the number of piles, so an answer always exists.- Piles can be huge: up to 1,000,000,000 bananas. Keep that number in mind.
How many hours does one pile take at speed k? Pile 7 at speed 4: after 1 hour
she has eaten 4 and 3 are left. Those 3 still cost a whole second hour. So
it’s 7 ÷ 4 = 1.75, rounded up to 2.
Rounding up is called the ceiling, written ⌈x⌉. In JavaScript it’s
Math.ceil(x), in Python math.ceil(x). ⌈1.75⌉ = 2, ⌈2⌉ = 2, ⌈0.5⌉ = 1.
The question isn’t “find a value in an array” any more. It’s “find the smallest number that works”. The key is how “works” behaves as the speed grows:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
Eating faster never takes more hours. So the answers line up as no, no, no, yes, yes, yes: one switch from no to yes. Whenever answers line up like that, binary search can find the switch.
Pause and think
Every speed faster than 6 (7, 8, … 11). If 6 already fits in 8 hours, a faster speed fits too, but it can’t be the smallest working speed. So the answer is 6 or slower: search 1..6 next. One test removed half the speeds.
Try speed 1. If she can’t finish in time, try 2, then 3, and so on. The first speed that works is the answer.
Brute force: try 1, 2, 3, ... bananas per hour
piles = [3, 6, 7, 11], h = 8
- 3
- 6
- 7
- 11
- h (hours we have)
- 8
- k (speed)
- —
- total hours
- —
- answer
- —
- Too slow
- Fast enough
Start with the slowest possible speed, k = 1, and go up one at a time.
Which line is running?
function minEatingSpeed(piles, h) {Running now: let k = 1; while (true) { let hours = 0; for (const pile of piles) { hours += Math.ceil(pile / k); } if (hours <= h) return k; // the first speed that is fast enough k++; // too slow: try one banana per hour faster }}Brute force: try every speed
function minEatingSpeed(piles, h) { let k = 1; while (true) { let hours = 0; for (const pile of piles) { hours += Math.ceil(pile / k); } if (hours <= h) return k; // the first speed that is fast enough k++; // too slow: try one banana per hour faster }}import mathdef min_eating_speed(piles, h): k = 1 while True: hours = 0 for pile in piles: hours += math.ceil(pile / k) if hours <= h: return k # the first speed that is fast enough k += 1 # too slow: try one banana per hour fasterEach try walks over all n piles. For [3, 6, 7, 11] the answer is 4, so that’s
4 tries × 4 piles = 16 small steps. Fine.
But with a pile of 1,000,000,000 bananas and very little time, the answer can be
close to a billion. That’s up to a billion tries, each walking all the piles
(up to 10,000): about 10¹³ steps. The time is
O(n × m), where m is the biggest
pile. Far too slow.
In week 3 you binary searched an array for a value. Here there’s no array to search. Instead we search the range of possible answers, 1 to the biggest pile, and at each guess we ask a yes/no question: “is this speed fast enough?” That yes/no function is called a feasibility check (“feasible” means “it works”).
Pattern
Binary search on the answer
Use it when: you need the minimum (or maximum) value that satisfies a condition, and if a value works then every bigger (or smaller) one works too.
Signal words
- “minimum speed”
- “smallest capacity”
- “at least”
- “within h hours”
- “minimize the maximum”
- The answer is between
lo = 1(slowest that makes sense) andhi = max(piles). At the biggest pile’s speed every pile takes 1 hour, sohialways works. - While
lo < hi: trymid = (lo + hi) // 2. - Add up the hours at speed
mid:⌈pile / mid⌉for every pile. - If the total is
≤ h,midworks. The answer ismidor slower:hi = mid(keepmid, it might be the answer). - Otherwise
midis too slow, and so is everything slower:lo = mid + 1. - When
lo === hi, only one speed is left, and it’s the answer.
Watch the number line at the top: the shaded band is the speeds still possible. Red dots are speeds we found too slow, green dots are speeds that work. The first round shows each pile’s ceiling one at a time; later rounds do it in one step.
Binary search on the eating speed
piles = [3, 6, 7, 11], h = 8
- 3
- 6
- 7
- 11
- h (hours we have)
- 8
- mid (speed)
- —
- total hours
- —
- lo
- 1
- hi
- —
- answer
- —
- Speeds still possible (lo..hi)
- Too slow
- Fast enough
- Pile being worked out
The answer is a speed k (bananas per hour). Speed 0 makes no sense, so the slowest speed worth trying is lo = 1.
Which line is running?
function minEatingSpeed(piles, h) {Running now: let lo = 1; // slowest speed that makes sense let hi = Math.max(...piles); // this speed always works while (lo < hi) { const mid = Math.floor((lo + hi) / 2); let hours = 0; for (const pile of piles) { hours += Math.ceil(pile / mid); // a partly eaten pile still costs a full hour } if (hours <= h) { hi = mid; // fast enough: the answer is mid or slower } else { lo = mid + 1; // too slow: the answer is faster than mid } } return lo; // lo === hi: the slowest speed that works}Try the “h = number of piles” edge case: with only 4 hours for 4 piles, Koko must finish one whole pile every hour, so the answer is the biggest pile, 11.
Binary search on the speed
function minEatingSpeed(piles, h) { let lo = 1; // slowest speed that makes sense let hi = Math.max(...piles); // this speed always works while (lo < hi) { const mid = Math.floor((lo + hi) / 2); let hours = 0; for (const pile of piles) { hours += Math.ceil(pile / mid); // a partly eaten pile still costs a full hour } if (hours <= h) { hi = mid; // fast enough: the answer is mid or slower } else { lo = mid + 1; // too slow: the answer is faster than mid } } return lo; // lo === hi: the slowest speed that works}import mathdef min_eating_speed(piles, h): lo = 1 # slowest speed that makes sense hi = max(piles) # this speed always works while lo < hi: mid = (lo + hi) // 2 hours = 0 for pile in piles: hours += math.ceil(pile / mid) # a partly eaten pile still costs a full hour if hours <= h: hi = mid # fast enough: the answer is mid or slower else: lo = mid + 1 # too slow: the answer is faster than mid return lo # lo == hi: the slowest speed that worksPython needs import math at the top (for math.ceil), so its line numbers run
two ahead of JavaScript’s. On LeetCode the Python function sits inside
class Solution as def minEatingSpeed(self, piles, h).
- JS 2 / Py 4: the slowest speed worth trying. Speed 0 would never finish.
- JS 3 / Py 5: the fastest speed we ever need.
Math.max(...piles)spreads the array intoMath.max; Python’smax(piles)does the same. - JS 4 / Py 6:
lo < hi, notlo <= hi. We stop when one candidate is left, because we already know the range always contains a working speed. - JS 5 / Py 7: the speed to test, rounded down.
- JS 6–9 / Py 8–10: the feasibility check. For each pile, the hours are the pile divided by the speed, rounded up, because a partly eaten pile still uses a full hour.
- JS 10–11 / Py 11–12: fast enough. Set
hi = mid, notmid − 1:miditself might be the smallest working speed, so we must keep it in the range. - JS 13 / Py 14: too slow.
midcan’t be the answer, solo = mid + 1. - JS 16 / Py 15:
loandhiare equal, and that speed is the answer.
piles = [3, 6, 7, 11], h = 8:
| lo | hi | mid | hours per pile | total | ≤ 8? | next |
|---|---|---|---|---|---|---|
| 1 | 11 | 6 | 1, 1, 2, 2 | 6 | yes | hi = 6 |
| 1 | 6 | 3 | 1, 2, 3, 4 | 10 | no | lo = 4 |
| 4 | 6 | 5 | 1, 2, 2, 3 | 8 | yes | hi = 5 |
| 4 | 5 | 4 | 1, 2, 2, 3 | 8 | yes | hi = 4 |
| 4 | 4 | — | — | — | lo = hi | return 4 |
Look at the rows where mid = 5 and mid = 4: both speeds need exactly 8 hours. Binary search
doesn’t stop at the first speed that works (5); it keeps squeezing hi down to
find the slowest one.
Brute force
Time
O(n × m)
Up to m speeds (m = the biggest pile), and each one walks all n piles. With m = 1,000,000,000 that's hopeless.
Space
O(1)
Just k and a running total.
Binary search on the speed
Time
O(n × log m)
Each test halves the range of speeds, so about log₂(m) tests: for m = 1,000,000,000 that's only about 30. Each test walks the n piles.
Space
O(1)
lo, hi, mid and a running total.
From a billion tries down to about thirty. That’s what “binary search on the answer” buys you.
What to say out loud:
- “I’m looking for the minimum speed. If a speed works, any faster one works too, so the yes/no answers are sorted.”
- “That means I can binary search on the speed, between 1 and the biggest pile.”
- “The check for one speed is a pass over the piles with a ceiling division.”
- “That’s O(n log m) instead of O(n × m).”
- Mention the ceiling and the
hi = middetail before you’re asked.
Likely follow-ups:
- “Why is max(piles) enough for hi?” Because at that speed every pile takes one
hour, and
h ≥ len(piles). - “Could you make the check faster?” Not really; each speed needs to look at every pile once.
Related problems (same pattern):
- Capacity To Ship Packages Within D Days (LeetCode 1011) and Split Array Largest Sum (LeetCode 410): search the answer, check feasibility greedily.
- Sqrt(x) (LeetCode 69): the biggest x whose square is ≤ n.
- More on this pattern in the week 4 overview.