Koko Eating Bananas
Problem statement
There are several piles of bananas, and Koko has h hours before the guards return. She picks one constant eating speed k (bananas per hour) and keeps it for the whole time. Each hour she picks one pile and eats k bananas from it — or, if the pile has fewer than k left, she finishes that pile and stops for the hour (she doesn't move on to another pile in the same hour).
Find the smallest whole-number speed k that still lets her finish every pile within h hours.
Examples
Example 1
Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation: at speed 4, the piles take 1 + 2 + 2 + 3 = 8 hours (each pile's hours are its size divided by 4, rounded up). That exactly fits the 8-hour budget, and no slower speed does.
Example 2
Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Explanation: with only 5 hours and 5 piles, Koko has exactly one hour per pile, so she has to clear the biggest pile — 30 bananas — in a single hour.
Example 3
Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23
Explanation: with one extra hour to spare, a speed of 23 works: the piles take 2 + 1 + 1 + 1 + 1 = 6 hours.
Hints
Approach
Optimal: Binary search on the speed
Intuition
The brute-force approach checks every speed one at a time, but it doesn't need to: as speed goes up, the hours needed only ever goes down (never up). That's a monotonic relationship — exactly the shape binary search is built for. Instead of searching a sorted list of values, this binary searches a sorted list of possible answers: every speed from 1 to the biggest pile, ordered from slowest to fastest. At each guess, check whether that speed finishes in time; if it does, it's a candidate, but try an even slower one; if it doesn't, this speed and everything slower is out, so try faster.
Steps
- Set
left = 1(the slowest speed worth trying) andright = max(piles)(the fastest speed worth trying — nothing faster helps, since it never takes less than one hour to clear a pile). - While
left <= right: letspeed = (left + right) // 2. - Compute the total hours at this
speed, the same way as the brute-force approach. - If the hours fit within
h, this speed works — remember it, then try to find something slower:right = speed - 1. - Otherwise this speed is too slow — search faster speeds:
left = speed + 1. - Once the loop ends, the smallest working speed found is the answer.
Dry run
piles = [3, 6, 7, 11], h = 8. Speed range starts at [1, 11].
| step | left | right | speed | hours | fits? | action |
|---|---|---|---|---|---|---|
| 1 | 1 | 11 | 6 | 1+1+2+2 = 6 | yes | remember 6, try slower → right = 5 |
| 2 | 1 | 5 | 3 | 1+2+3+4 = 10 | no | too slow → left = 4 |
| 3 | 4 | 5 | 4 | 1+2+2+3 = 8 | yes | remember 4, try slower → right = 3 |
| end | 4 | 3 | — | — | — | left > right → return 4 |
Edge cases: a single pile with h = 1 forces speed up to that pile's full size, since there's only one hour to clear it — the binary search still finds that correctly because right starts at exactly that pile's size.
Complexity
Time O(n log m) - Binary search over the speed range `[1, m]` takes about log₂(m) steps, and each step costs O(n) to add up the hours across all piles.
Space O(1) - Two or three index-like variables, regardless of how many piles there are or how big they are.
import math
class Solution:
def minEatingSpeed(self, piles: list[int], h: int) -> int:
left, right = 1, max(piles)
res = right
while left <= right:
speed = (left + right) // 2
hours = sum(math.ceil(pile / speed) for pile in piles)
if hours <= h:
res = speed
right = speed - 1
else:
left = speed + 1
return res
if __name__ == "__main__":
print(Solution().minEatingSpeed([3, 6, 7, 11], 8)) # 4
print(Solution().minEatingSpeed([30, 11, 23, 4, 20], 5)) # 30
print(Solution().minEatingSpeed([30, 11, 23, 4, 20], 6)) # 23RecapThe whole problem in a few lines, for the night before
- Spot it: "minimum/maximum value that satisfies a condition, and the condition gets easier as the value increases" — binary search on the answer, not on an array
- Idea: binary search over the range of possible speeds; at each guess, simulate whether that speed finishes in time
- Cost: O(n log m) time, O(1) space, where n is the number of piles and m is the largest pile
- Trap: using integer division instead of rounding up when computing hours per pile — a partial hour still costs a full hour
Interview follow-ups
The piles can now be refilled while Koko eats — new bananas can arrive mid-run. How would that change things?
The monotonic relationship that makes binary search work — faster speed always means fewer or equal hours — no longer holds cleanly if the total workload can grow while she's still eating, since a speed that used to be "fast enough" might not stay that way. You'd need to know the arrival pattern (a fixed total by a deadline, or an ongoing rate) to decide whether this is still a single binary search or needs to become an ongoing rate-vs-arrival-rate comparison, closer to a queueing problem than a one-shot search.
hcan now be enormous — up to 10^9 as the constraints allow — while there are relatively few piles. Does the approach still hold up?Yes, without any change: the binary search's cost depends on the size of the speed range (bounded by the largest pile, at most 10^9) and the number of piles, not on
hitself —honly appears as a comparison value inside each check, so an enormoushjust makes it more likely that a slow speed already succeeds, which the search finds just as quickly.
Frequently asked questions
Binary search only needs one thing: a range of candidate answers where "does this answer work?" flips from no to yes (or yes to no) exactly once as you move through the range. Here the candidates are speeds from 1 to the biggest pile, and "finishes within h hours" goes from false to true as speed increases and never flips back — that single flip is what makes binary search valid, whether or not there's an actual array involved.
A speed of 0 bananas per hour would mean Koko eats nothing, ever, and no finite number of hours could clear a nonempty pile — worse, it would make the hours-per-pile division blow up. The smallest speed that could possibly work is 1, so that's the natural lower bound.
Because Koko doesn't get credit for a partial hour. If a pile has 7 bananas and she eats 4 per hour, she needs 2 hours: 4 in the first, 3 in the second, and that second hour is spent even though she didn't eat a full 4. Rounding down would undercount the hours and could make an invalid speed look valid.
This is a rate-sizing problem: given a fixed amount of work (bananas) and a fixed deadline (hours), find the minimum throughput (bananas per hour) that clears it in time. The same shape shows up when sizing a worker pool's processing rate to drain a queue before an SLA, or picking the minimum bandwidth that finishes a batch of transfers within a maintenance window.
