## Problem Description

Koko loves to eat bananas. There are **N** piles of bananas, the **i**-th pile has **piles[i]** bananas. The guards have gone and will come back in **H** hours.

Koko can decide her bananas-per-hour eating speed of **K**. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour. Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

## Example

1 | Input: piles = [3,6,7,11], H = 8 |

1 | Input: piles = [30,11,23,4,20], H = 5 |

1 | Input: piles = [30,11,23,4,20], H = 6 |

## Ideas

The way to tackle this question is to find out a way to get the minimum possible K. The value for K is clearly limited from 1 to the greatest number in the piles array (if setting K to maximum number in the array then any number greater than K will only result in longer time to finish)

Of course we could iterate from 1 to the greatest number to find out K, then why don’t we use binary search? The way it works is that if we found some K that **doesn’t** allow Koko to have all the bananas in limited time H, then any number smaller than K will not work either. Same thing goes to the case that we found some K that **does** allow Koko to enjoy all bananas within time H, we can then safely try smaller numbers as they might also fulfill the term.

Now that we have a nice way to find K, the only thing left here is to check if K is good (Koko get to eat all bananas within H hours) or not (Koko get caught by the guard). We can simply go through the array to calculate the time needed according the the description.

## Code

1 | class Solution { |

## Complexity and Optimizaiton

Suppose n is the length of the piles array, the method **finish** takes O(n) as it iterates over the array once. In **minEatingSpeed** **finish** is called inside the binary search loop. Therefore, the time complexity is O(nlog(K)) and space complexity is O(1).

There are still something we could improve in the **finish** method. Assuming n is smaller than K, then we could first sort the piles array in **minEatingSpeed**, then use binary seach as well in **finish** to find out the minimum p larger than K, in this way there is no need to iterate the elements before p.