This problem can feel tricky at first, but it becomes easier once you understand what you're really being asked: "What's the slowest speed Koko can eat at and still finish all the bananas in h
hours or less?"
The idea is to check different eating speeds and simulate how many hours Koko would take at each one. The smaller the speed, the longer it takes. The larger the speed, the faster she finishes. So we’re looking for the minimum speed that still allows her to finish on time.
What Happens at a Certain Speed?
Let’s say we try a speed of k
bananas per hour. For every pile, we calculate how many hours Koko would take to eat that pile: it's ceil(pile / k)
hours. We add up these hours for all piles. If the total time is less than or equal to h
, then this speed k
works — but maybe there’s a slower speed that also works, so we try smaller values. If the total time is more than h
, then she’s eating too slow and we need to try higher speeds.
How Do We Find the Best Speed Efficiently?
Instead of testing every possible speed from 1 to the maximum pile size (which could be huge), we use binary search. This helps us quickly zero in on the minimum valid speed. Here's the intuition:
low
starts at 1 — the slowest possible eating speed.
high
is the largest pile — the fastest she'd ever need to eat (if there's just one hour).
- We pick a
mid
speed between low
and high
and check if it’s fast enough.
- If it is, we try to find a slower valid speed (search left); if not, we try faster (search right).
Different Cases to Think About
- Exact Fit: When
h
is equal to the total number of piles, Koko must eat at least one pile per hour. So her speed must be high enough to finish any one pile in one hour.
- Relaxed Time: If
h
is very large, she can afford to eat slowly.
- Only One Pile: The answer is simply
ceil(pile / h)
.
- Empty Piles List: If there are no piles, Koko doesn’t need to eat. So the answer is
0
.
By adjusting the speed intelligently using binary search, we quickly find the minimum speed at which she can still meet her goal.