Solution
Approach 1: Binary Search
Intuition
If Koko can finish eating all the bananas (within H
hours) with an eating speed of K
, she can finish with a larger speed too.
If we let possible(K)
be true
if and only if Koko can finish with an eating speed of K
, then there is some X
such that possible(K) = True
if and only if K >= X
.
For example, with piles = [3, 6, 7, 11]
and H = 8
, there is some X = 4
so that possible(1) = possible(2) = possible(3) = False
, and possible(4) = possible(5) = ... = True
.
Algorithm
We can binary search on the values of possible(K)
to find the first X
such that possible(X)
is True
: that will be our answer. Our loop invariant will be that possible(hi)
is always True
, and lo
is always less than or equal to the answer. For more information on binary search, please visit [LeetCode Explore  Binary Search].
To find the value of possible(K)
, (ie. whether Koko
with an eating speed of K
can eat all bananas in H
hours), we simulate it. For each pile of size p > 0
, we can deduce that Koko finishes it in Math.ceil(p / K) = ((p1) // K) + 1
hours, and we add these times across all piles and compare it to H
.
Complexity Analysis

Time Complexity: , where is the number of piles, and is the maximum size of a pile.

Space Complexity: .
Analysis written by: @awice.