Solution


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) = ((p-1) // 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.