Koko Eating Bananas
Find the slowest eating speed that clears every pile of bananas within h hours by binary searching the range of speeds, in O(n log m) time.
Updated Medium read: 8 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Try every speed | O(n × m) | O(1) |
| Binary search on the speed | O(n log m) | O(1) |
The problem
Koko has several piles of bananas; piles[i] is the number of bananas in pile i. She has h hours to eat them all.
She chooses one eating speed, a whole number of bananas per hour, and keeps to it. Each hour she picks a single pile and eats up to that many bananas from it. If the pile has fewer bananas left than her speed, she finishes the pile and then waits: she does not start another pile until the next hour.
Return the smallest speed at which every banana is eaten within h hours. There are never more piles than hours, so an answer always exists.
piles = [4, 9, 12, 7], h = 6 → 7
piles = [4, 9, 12, 7], h = 4 → 12 (one hour per pile: the speed must cover the largest pile)
piles = [4, 9, 12, 7], h = 10 → 4
piles = [30], h = 7 → 5How long one speed takes
Before looking for the best speed, work out how to judge a single one. A pile of 9 bananas at speed 4 takes three hours: 4, then 4, then the last 1. In general a pile takes pile / speed hours, rounded up, because a part-used hour is still an hour gone. The total is the sum over all piles.
piles = [4, 9, 12, 7], speed = 4
pile 4 → 1 hour
pile 9 → 3 hours
pile 12 → 3 hours
pile 7 → 2 hours
total → 9 hoursBoth approaches below use this calculation, so it gets a function of its own.
JavaScript
function hoursNeeded(piles, speed) {
let hours = 0;
for (const pile of piles) {
hours += Math.ceil(pile / speed);
}
return hours;
}Python
def hours_needed(piles, speed):
hours = 0
for pile in piles:
hours += (pile + speed - 1) // speed # pile / speed, rounded up
return hoursThe Python version rounds up with whole numbers only. Adding speed - 1 before the floor division pushes any remainder over into the next whole hour, and avoids floating-point division altogether.
Approach 1: try every speed
Start at speed 1 and go up by one until the hours fit.
JavaScript
function minEatingSpeedBruteForce(piles, h) {
let speed = 1;
while (hoursNeeded(piles, speed) > h) {
speed++;
}
return speed;
}Python
def min_eating_speed_brute_force(piles, h):
speed = 1
while hours_needed(piles, speed) > h:
speed += 1
return speedThe loop must stop: at a speed equal to the largest pile, each pile takes exactly one hour, and there are at least as many hours as piles.
With n piles and a largest pile of m bananas, up to m speeds are tried and each costs one pass over the piles.
Time O(n × m). Space O(1).
A pile may hold a thousand million bananas. With ten thousand piles as well, that is far too slow.
Approach 2: binary search on the speed
Write the result of the test "does this speed finish within 6 hours?" under each speed for piles = [4, 9, 12, 7]:
speed: 1 2 3 4 5 6 7 8 9 10 11 12
hours: 32 17 12 9 8 7 6 6 5 5 5 4
in 6? no no no no no no yes yes yes yes yes yes
↑
the smallest speed that passesEating faster never takes longer, so the hours only ever fall or stay level as the speed rises. Once a speed passes, every higher one passes too. The row of answers switches from "no" to "yes" exactly once, and binary search can find the switch without testing every speed. This is the "smallest value that passes" form of the binary search on the answer pattern.
Three decisions:
- Range. The lowest speed is 1. The highest worth trying is the largest pile: anything faster still takes one hour per pile, so it gains nothing.
- Test.
hoursNeeded(piles, speed) <= h. - Direction. Failures come first. When the middle passes it may be the answer, so keep it (
hi = mid). When it fails, drop it (lo = mid + 1).
JavaScript
function minEatingSpeed(piles, h) {
let lo = 1;
let hi = Math.max(...piles);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (hoursNeeded(piles, mid) <= h) {
hi = mid; // fast enough: the answer is mid or slower
} else {
lo = mid + 1; // too slow: the answer is faster
}
}
return lo;
}Python
def min_eating_speed(piles, h):
lo = 1
hi = max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if hours_needed(piles, mid) <= h:
hi = mid # fast enough: the answer is mid or slower
else:
lo = mid + 1 # too slow: the answer is faster
return loIt is the same loop as the lower-bound search in Search Insert Position. There, the question asked of the middle was "is this element at least the target?". Here it is "is this speed fast enough?". Nothing else has changed.
Walkthrough
piles = [4, 9, 12, 7], h = 6. The range of speeds starts as 1 to 12.
| lo | hi | mid | Hours at speed mid | Within 6? | Action |
|---|---|---|---|---|---|
| 1 | 12 | 6 | 1 + 2 + 2 + 2 = 7 | No | lo = 7 |
| 7 | 12 | 9 | 1 + 1 + 2 + 1 = 5 | Yes | hi = 9 |
| 7 | 9 | 8 | 1 + 2 + 2 + 1 = 6 | Yes | hi = 8 |
| 7 | 8 | 7 | 1 + 2 + 2 + 1 = 6 | Yes | hi = 7 |
| 7 | 7 | lo equals hi: return 7 |
Four speeds were tested instead of seven. Speed 8 also finishes in six hours, which is why a passing speed cannot simply be returned: a slower one may pass too, and the search keeps going left until none does.
The range holds m speeds, so it is halved about log m times, and each test is one pass over n piles.
Time O(n log m). Space O(1).
Comparing the approaches
| Approach | Time | Space | Tests when the largest pile is 1,000,000,000 |
|---|---|---|---|
| Try every speed | O(n × m) | O(1) | Up to 1,000,000,000 |
| Binary search on the speed | O(n log m) | O(1) | About 30 |
The test is the same in both. All of the gain comes from choosing which speeds to test.
Why sorting the piles does not help
It is tempting to sort piles first because the word "binary search" is in the air. The piles are never searched. The search runs over speeds, which are consecutive whole numbers and so already in order. The piles are only added up, and a sum does not care about order.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python. minEatingSpeed calls hoursNeeded, so copy that function as well.
JavaScript
console.log(hoursNeeded([4, 9, 12, 7], 4)); // 9
console.log(minEatingSpeed([4, 9, 12, 7], 6)); // 7
console.log(minEatingSpeed([4, 9, 12, 7], 4)); // 12
console.log(minEatingSpeed([4, 9, 12, 7], 10)); // 4
console.log(minEatingSpeed([30], 7)); // 5Python
print(hours_needed([4, 9, 12, 7], 4)) # 9
print(min_eating_speed([4, 9, 12, 7], 6)) # 7
print(min_eating_speed([4, 9, 12, 7], 4)) # 12
print(min_eating_speed([4, 9, 12, 7], 10)) # 4
print(min_eating_speed([30], 7)) # 5The comment after each line is the result you should see.
Common mistakes
- Starting the range at 0. Speed 0 divides by zero, and in JavaScript that quietly gives
Infinityhours instead of an error. The slowest real speed is 1. - Rounding the hours down.
Math.floor(pile / speed)says a pile of 9 at speed 4 takes two hours. The last banana needs a third. - Dividing the total by the speed.
sum(piles) / speedassumes Koko can move to a new pile in the middle of an hour. She cannot, so each pile is rounded up separately. - Returning the first speed that passes. A slower speed might pass as well. Keep the passing speed in the range and carry on.
- Using
hi = mid - 1withlo < hi. That throws away a speed that might be the answer. In this template the passing branch ishi = mid. - Setting the top of the range to the sum of the piles. It still works, but the largest pile is a tighter limit and just as easy to justify.
- Overflow in other languages. With many large piles at a low speed, the hours can exceed a 32-bit integer. Use a 64-bit type in Java or C++.
Original problem: LeetCode 875: Koko Eating Bananas