# LeetCode 875: Koko Eating Bananas

## Problem Restatement

Koko has several piles of bananas.

The array `piles` tells us how many bananas are in each pile.

Koko chooses an eating speed:

```python
k
```

This means she can eat up to `k` bananas from one pile in one hour.

Rules:

1. Each hour, she chooses one pile.
2. If the pile has at least `k` bananas, she eats exactly `k`.
3. If the pile has fewer than `k` bananas, she eats the whole pile.
4. She does not eat from another pile during that same hour.

Given `h` hours, return the minimum integer speed `k` such that Koko can eat all bananas within `h` hours.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `piles`, a list of banana pile sizes |
| Input | `h`, the number of hours available |
| Output | Minimum integer eating speed `k` |
| Constraint | `piles.length <= h` |

Function shape:

```python
class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        ...
```

## Examples

Example 1:

```python
piles = [3, 6, 7, 11]
h = 8
```

If `k = 4`, the hours needed are:

| Pile | Hours |
|---:|---:|
| `3` | `1` |
| `6` | `2` |
| `7` | `2` |
| `11` | `3` |

Total:

```python
1 + 2 + 2 + 3 = 8
```

So speed `4` works.

If `k = 3`, the hours are:

```python
1 + 2 + 3 + 4 = 10
```

That is too slow.

So the answer is:

```python
4
```

Example 2:

```python
piles = [30, 11, 23, 4, 20]
h = 5
```

There are five piles and five hours.

Koko must finish each pile in one hour.

So she needs speed equal to the largest pile:

```python
30
```

Example 3:

```python
piles = [30, 11, 23, 4, 20]
h = 6
```

The minimum speed that works is:

```python
23
```

## First Thought: Try Every Speed

A direct solution is to try every possible speed from `1` to `max(piles)`.

For each speed, compute how many hours Koko needs.

Return the first speed that finishes within `h` hours.

This is correct, but it can be too slow because `piles[i]` can be very large.

## Key Insight

The answer has a monotonic property.

If Koko can finish at speed `k`, then she can also finish at any speed larger than `k`.

If she cannot finish at speed `k`, then any smaller speed also fails.

So the speeds look like this:

```text
fail, fail, fail, pass, pass, pass
```

We need the first passing speed.

That is a binary search problem.

For a pile with `bananas` bananas, the hours needed at speed `k` is:

```python
ceil(bananas / k)
```

In integer arithmetic:

```python
(bananas + k - 1) // k
```

## Algorithm

Search over possible speeds.

The smallest possible speed is:

```python
1
```

The largest useful speed is:

```python
max(piles)
```

For each middle speed:

1. Compute the total hours needed.
2. If total hours is less than or equal to `h`, this speed works.
3. Try a smaller speed by moving `right`.
4. Otherwise, the speed is too slow.
5. Try a larger speed by moving `left`.

When the search ends, `left` is the minimum valid speed.

## Correctness

For any fixed speed `k`, the function `hours(k)` computes the exact number of hours needed because each pile requires `ceil(pile / k)` hours.

If `hours(k) <= h`, then speed `k` is valid. Any larger speed can only reduce or keep the same number of hours, so all larger speeds are also valid.

If `hours(k) > h`, then speed `k` is invalid. Any smaller speed can only increase or keep the same number of hours, so all smaller speeds are also invalid.

Therefore, the valid speeds form a suffix of the search range.

Binary search preserves the smallest valid speed inside the search range. When the middle speed works, the algorithm keeps it as a possible answer by moving `right = mid`. When it fails, the algorithm removes it and all smaller speeds by moving `left = mid + 1`.

When `left == right`, only one speed remains. Since the smallest valid speed was never removed, that speed is the answer.

## Complexity

Let:

```python
n = len(piles)
m = max(piles)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log m)` | Each binary search step scans all piles |
| Space | `O(1)` | Only counters and search bounds are stored |

## Implementation

```python
class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left = 1
        right = max(piles)

        while left < right:
            mid = (left + right) // 2

            hours = 0
            for pile in piles:
                hours += (pile + mid - 1) // mid

            if hours <= h:
                right = mid
            else:
                left = mid + 1

        return left
```

## Code Explanation

The search range is:

```python
left = 1
right = max(piles)
```

Speed `1` is the slowest possible speed.

Speed `max(piles)` can finish every pile in at most one hour.

The loop continues while more than one candidate speed remains:

```python
while left < right:
```

We test the middle speed:

```python
mid = (left + right) // 2
```

Then compute the total hours:

```python
hours = 0
for pile in piles:
    hours += (pile + mid - 1) // mid
```

The expression:

```python
(pile + mid - 1) // mid
```

is integer ceiling division.

If the speed works:

```python
if hours <= h:
    right = mid
```

we try to find a smaller valid speed.

Otherwise:

```python
else:
    left = mid + 1
```

the speed is too slow, so we search higher speeds.

Finally:

```python
return left
```

returns the smallest speed that works.

## Testing

```python
def test_min_eating_speed():
    s = Solution()

    assert s.minEatingSpeed([3, 6, 7, 11], 8) == 4

    assert s.minEatingSpeed([30, 11, 23, 4, 20], 5) == 30

    assert s.minEatingSpeed([30, 11, 23, 4, 20], 6) == 23

    assert s.minEatingSpeed([1], 1) == 1

    assert s.minEatingSpeed([312884470], 312884469) == 2

    print("all tests passed")

test_min_eating_speed()
```

Test meaning:

| Test | Why |
|---|---|
| `[3, 6, 7, 11]`, `h = 8` | Standard binary search case |
| `h` equals number of piles | Must use largest pile speed |
| Slightly more time than piles | Allows smaller speed |
| Single pile | Minimum input |
| Large pile and large `h` | Checks ceiling division |