Problem: Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the i<sup>th</sup> 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 will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

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
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

• 1 <= piles.length <= 10<sup>4</sup>
• piles.length <= h <= 10<sup>9</sup>
• 1 <= piles[i] <= 10<sup>9</sup>

# Minimum Eating Speed to Finish Bananas

This problem asks us to find the minimum eating speed (k) for Koko to finish all the bananas within a given time (h). We can use binary search to efficiently find this optimal eating speed.

## 1. Naive Solution (Brute Force)

A naive approach would be to iterate through all possible values of `k` from 1 to the maximum number of bananas in any pile and check if Koko can finish all the bananas within `h` hours for each `k`. This approach is inefficient because it has a time complexity of O(n * max(piles)), where n is the number of piles.

## 2. Optimal Solution (Binary Search)

We can use binary search to find the optimal value of `k`. The range for our binary search will be from 1 to the maximum number of bananas in any pile. For each `k` in our search space, we calculate the total time it takes for Koko to eat all the bananas. If the total time is less than or equal to `h`, we try a smaller `k`; otherwise, we try a larger `k`.

```python
def minEatingSpeed(piles, h):
    left, right = 1, max(piles)
    ans = right

    while left <= right:
        k = (left + right) // 2
        hours = 0
        for pile in piles:
            hours += (pile + k - 1) // k  # Equivalent to math.ceil(pile / k)

        if hours <= h:
            ans = k
            right = k - 1  # Try to find a smaller k
        else:
            left = k + 1  # Need a larger k

    return ans

# Example usage
piles = [3, 6, 7, 11]
h = 8
print(f"Minimum eating speed: {minEatingSpeed(piles, h)}")  # Output: 4

piles = [30, 11, 23, 4, 20]
h = 5
print(f"Minimum eating speed: {minEatingSpeed(piles, h)}")  # Output: 30

piles = [30, 11, 23, 4, 20]
h = 6
print(f"Minimum eating speed: {minEatingSpeed(piles, h)}")  # Output: 23

3. Big(O) Run-time Analysis

• The binary search takes O(log(max(piles))) iterations. max(piles) is the largest pile size, which determines the search space for k. In each iteration, we calculate the time taken to eat all bananas, which takes O(n) time, where n is the number of piles.
• Therefore, the overall time complexity is O(n * log(max(piles))).

4. Big(O) Space Usage Analysis

• The space complexity is O(1) because we are only using a few variables to store the left, right, and middle values during the binary search. We are not using any extra data structures that scale with the input size.

5. Edge Cases

• Empty Input: If the piles array is empty, the function should return 0 or handle the case gracefully by returning an appropriate default value or raising an exception.
• Single Pile: If there is only one pile, the minimum eating speed would be (pile + h - 1) // h.
• h equals the number of piles: In this case, Koko has exactly one hour per pile, so the minimum eating speed is the size of the largest pile.
• h is less than the number of piles: This is an invalid input according to the constraints (piles.length <= h), so the function doesn't need to handle it.
• Large Pile Sizes: The pile sizes can be up to 10⁹. The code should handle this without integer overflow issues. The calculations of hours within the loop is done correctly to avoid overflows.
• h is very large: If h is extremely large compared to the number of piles, the binary search will still correctly converge to the smallest possible eating speed (1).

These edge cases are handled correctly by the provided code.