Statement▼
Koko has piles[i] bananas. The guards have left and will return in h hours, and Koko must finish all the bananas before they come back.
Before eating, Koko chooses an integer as an eating speed
In each hour, Koko selects one pile of bananas and eats from it according to the following rules:
If the pile contains at least
k bananas, she eats exactlyk bananas from it.If the pile contains fewer than
k bananas, she eats all the bananas from that pile and does not eat from any other pile during that hour.
Your task is to return the minimum eating speed h hours before the guards return.
Constraints:
1 ≤ piles.length≤ 103 piles.length≤ h≤ 109 1 ≤ piles[i]≤ 104
Solution
The intuition behind this solution is that we don’t need to try every possible eating speed from 1 to the maximum pile size, because that would be inefficient. Instead, we can use the fact that the problem has a monotonic pass/fail behavior:
If Koko can finish eating all the bananas at some speed
kwithinhhours, then she can also finish at any faster speed, because eating faster never increases the time needed.Conversely, if she cannot finish at speed
k, she cannot finish at any slower speed either, because eating slower only takes longer.
This means the set of all possible speeds naturally splits into two regions:
Failing speeds on the left (too slow)
Succeeding speeds on the right (fast enough)
There is a single boundary point between these regions, and our task is to find the smallest successful speed. Binary search is the most efficient way to find the answer because the search space is ordered and follows this monotonic pass/fail behavior. Binary search works by repeatedly checking the middle speed and then narrowing the range to only the half that could contain the boundary.
Let’s break down the key steps of the solution:
Initialize
leftto 1 andrightto the maximum number of bananas in any pile.Iterate while
leftis less thanright:Calculate the middle speed
midas the average ofleftandright.Compute the total number of hours required at this speed:
hours= sum( (pile + mid - 1)If
hoursare less than or equal toh, it meansmidis fast enough, so move the search space to the left by settingrighttomid.Otherwise, if
hoursexceedh, it meansmidis too slow, so move the search space to the right by settinglefttomid + 1.
When the iteration ends, return
leftas the minimum eating speed that allows Koko to eat all the bananas withinhhours.
Let’s look at the following illustration to get a better understanding of the solution: