# Koko Eating Bananas
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/koko-eating-bananas)
Canonical: https://scaleengineer.com/dsa/problems/koko-eating-bananas
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Atlassian](https://scaleengineer.com/companies/atlassian), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Infosys](https://scaleengineer.com/companies/infosys), [PayPal](https://scaleengineer.com/companies/paypal), [VMware](https://scaleengineer.com/companies/vmware), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [eBay](https://scaleengineer.com/companies/ebay), [Netflix](https://scaleengineer.com/companies/netflix), [Turing](https://scaleengineer.com/companies/turing), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [HashedIn](https://scaleengineer.com/companies/hashedin), [oyo](https://scaleengineer.com/companies/oyo), [Splunk](https://scaleengineer.com/companies/splunk), [Nykaa](https://scaleengineer.com/companies/nykaa), [Ripple](https://scaleengineer.com/companies/ripple), [Okta](https://scaleengineer.com/companies/okta)
---
## Problem
Koko loves to eat bananas. There are `n` piles of bananas, the `ith` 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 <= 104`
* `piles.length <= h <= 109`
* `1 <= piles[i] <= 109`

# Approaches
## Brute Force with Linear Search
This approach involves checking every possible eating speed `k` starting from 1. For each speed, we calculate the total time required to eat all the bananas. The first speed `k` that allows Koko to finish within `h` hours is the minimum possible speed and is returned as the answer. This method is straightforward but inefficient.
**Time:** O(M * N), where N is the number of piles and M is the maximum possible eating speed (the value of the largest pile). In the worst case, we might have to check all speeds from 1 to M. For each speed, we iterate through N piles. This is too slow for the given constraints. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct solution if it runs to completion.
**Cons:** Extremely inefficient due to the large search space for `k`.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints, as the maximum pile size can be up to 10^9.
### Explanation
The brute-force solution systematically tests each possible value for the eating speed `k`, beginning with the slowest possible speed, `k=1`. For a given `k`, we can determine the total time required by summing up the hours needed for each pile. The hours to finish a pile of `p` bananas with speed `k` is `ceil(p / k)`. In integer arithmetic, this is `(p + k - 1) / k`. We calculate this for all piles and sum them up. If the total time is within the allowed `h` hours, we have found our answer, as we are checking `k` in increasing order. The search for `k` can stop once we reach the size of the largest pile, as any speed greater than that won't reduce the time for that pile (it will still take 1 hour).

```java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        // The maximum possible speed to check is the largest pile size.
        int maxPile = 0;
        for (int pile : piles) {
            maxPile = Math.max(maxPile, pile);
        }

        // Start checking speeds from k = 1.
        for (int k = 1; k <= maxPile; k++) {
            long totalHours = 0;
            // Calculate total hours for the current speed k.
            for (int pile : piles) {
                totalHours += (pile + k - 1) / k;
            }
            // If Koko can finish within h hours, this is the minimum k.
            if (totalHours <= h) {
                return k;
            }
        }
        return -1; // Should not be reached given the problem constraints.
    }
}
```
### Algorithm
- Iterate through possible eating speeds `k` starting from 1 up to a reasonable upper bound (like the maximum pile size).
- For each speed `k`, calculate the total hours `totalHours` required to eat all bananas.
- To calculate `totalHours`, iterate through each pile `p` in `piles`.
- The time for one pile is `ceil((double)p / k)`, which can be calculated using integer arithmetic as `(p + k - 1) / k`.
- Sum up the hours for all piles.
- If `totalHours` is less than or equal to the given `h`, then `k` is the minimum speed. Return `k` immediately.

## Binary Search on the Answer
A much more efficient approach utilizes binary search on the possible range of eating speeds `k`. The key observation is that the time taken to eat all bananas is a monotonically decreasing function of the speed `k`. That is, if Koko can finish with speed `k`, she can also finish with any speed greater than `k`. This property allows us to efficiently discard half of the search space in each step, leading to a logarithmic time complexity for the search.
**Time:** O(N * log M), where N is the number of piles and M is the maximum value in `piles`. The binary search on the range of speeds takes `log M` iterations. In each iteration, we iterate through all N piles to calculate the total time, which takes O(N) time. · **Space:** O(1), as we only use a few variables to manage the binary search state, not counting the input array.
**Pros:** Highly efficient and passes all test cases within the time limit.; Optimal solution for this type of problem (searching for a minimum/maximum value that satisfies a monotonic condition).
**Cons:** Slightly more complex to conceptualize than a linear search.; Requires careful handling of potential integer overflow when calculating the total hours, which must be stored in a `long`.
### Explanation
The problem asks for the minimum `k` that satisfies a condition. The condition (finishing within `h` hours) has a monotonic property with respect to `k`: if a speed `k` works, any speed `k' > k` also works. This structure is a perfect fit for binary search on the answer.

The search space for `k` ranges from a minimum of 1 to a maximum of the largest pile size. Any speed higher than the largest pile is redundant. We can set `low = 1` and `high = max(piles)`. 

We then apply binary search:
1. Pick a `mid` speed from the current range `[low, high]`.
2. Calculate the total hours needed to eat all bananas at this `mid` speed. It's crucial to use a `long` for the total hours to avoid overflow, as the sum can exceed the capacity of a 32-bit integer.
3. If the total hours is less than or equal to `h`, `mid` is a valid speed. We store it as a potential answer and try to find an even smaller speed by narrowing our search to the left half (`high = mid - 1`).
4. If the total hours exceeds `h`, the speed `mid` is too slow. We must increase the speed, so we search in the right half (`low = mid + 1`).

This process continues until the search space is exhausted (`low > high`), and the best answer found will be the minimum possible speed `k`.

```java
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int low = 1;
        int high = 0;
        for (int pile : piles) {
            high = Math.max(high, pile);
        }

        int minSpeed = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canFinish(piles, h, mid)) {
                minSpeed = mid;
                high = mid - 1; // Try for a smaller speed
            } else {
                low = mid + 1; // Speed is too slow, need to increase it
            }
        }
        return minSpeed;
    }

    private boolean canFinish(int[] piles, int h, int k) {
        long totalHours = 0;
        for (int pile : piles) {
            // Calculate hours for the current pile and add to total.
            // (pile + k - 1) / k is equivalent to Math.ceil((double)pile / k)
            totalHours += (long)(pile + k - 1) / k;
        }
        return totalHours <= h;
    }
}
```
### Algorithm
- Determine the search range for the speed `k`. The lower bound `low` is 1. The upper bound `high` is the maximum number of bananas in any single pile.
- Perform a binary search within the range `[low, high]`.
- In each step, calculate the middle speed `mid = low + (high - low) / 2`.
- Check if it's possible to finish all bananas with speed `mid` within `h` hours.
- To do this, calculate the total hours required for speed `mid`. Initialize `totalHours = 0` (as a `long` to prevent overflow). Iterate through each pile `p` and add `(p + mid - 1) / mid` to `totalHours`.
- If the calculated `totalHours` is less than or equal to `h`, it means `mid` is a possible answer. We store it and try to find a smaller valid speed by searching in the left half: `high = mid - 1`.
- If `totalHours` is greater than `h`, `mid` is too slow. We need to increase the speed by searching in the right half: `low = mid + 1`.
- The loop continues until `low > high`. The last valid speed recorded is the minimum one.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinEatingSpeed(int[] piles, int h) {
        int left = 1, right = piles.Max();
        while (left < right) {
            int mid = (left + right) >> 1;
            int s = 0;
            foreach(int pile in piles) {
                s += (pile + mid - 1) / mid;
            }
            if (s <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
```

### Java

```java
class Solution { public int minEatingSpeed ( int [] piles , int h ) { int left = 1 , right = ( int ) 1 e9 ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; int s = 0 ; for ( int x : piles ) { s += ( x + mid - 1 ) / mid ; } if ( s <= h ) { right = mid ; } else { left = mid + 1 ; } } return left ; } }
```

### CPP

```cpp
class Solution { public: int minEatingSpeed ( vector < int >& piles , int h ) { int left = 1 , right = 1e9 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; int s = 0 ; for ( int & x : piles ) s += ( x + mid - 1 ) / mid ; if ( s <= h ) right = mid ; else left = mid + 1 ; } return left ; } };
```

### Python

```python
class Solution : def minEatingSpeed ( self , piles : List [ int ], h : int ) -> int : left , right = 1 , int ( 1e9 ) while left < right : mid = ( left + right ) >> 1 s = sum (( x + mid - 1 ) // mid for x in piles ) if s <= h : right = mid else : left = mid + 1 return left
```