# Koko Eating Bananas

- **Canonical ID**: `koko-eating-bananas`
- **Canonical URL**: https://dsacheatsheet.com/problems/koko-eating-bananas
- **Difficulty**: medium
- **Patterns**: Binary Search
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/koko-eating-bananas/

## 1. Core Invariant / The Trick

Monotonic predicate on speed `k` over `[1 .. max(piles)]`: calculate `sum(ceil(p / k))` (`(p + k - 1) // k` integer ceiling). Find the smallest `k` where total hours <= `h`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N log M)`
- **Space Complexity**: `O(1)`
- **Proof**: Binary search spans range `1..max(piles)` (size M); each check iterates N piles.

## 3. Minimal Idiomatic Code

### Python
```python
def minEatingSpeed(piles: list[int], h: int) -> int:
    l, r = 1, max(piles)
    while l < r:
        m = (l + r) // 2
        hours = sum((p + m - 1) // m for p in piles)
        if hours <= h: r = m
        else: l = m + 1
    return l
```

### TypeScript
```typescript
export function minEatingSpeed(piles: number[], h: number): number {
  let l = 1, r = Math.max(...piles);
  while (l < r) {
    const m = Math.floor((l + r) / 2);
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / m);
    if (hours <= h) r = m; else l = m + 1;
  }
  return l;
}
```

### C++
```cpp
int minEatingSpeed(vector<int>& piles, int h) {
    int l = 1, r = *max_element(piles.begin(), piles.end());
    while (l < r) {
        int m = l + (r - l) / 2; long hrs = 0;
        for (int p : piles) hrs += (p + m - 1) / m;
        hrs <= h ? r = m : l = m + 1;
    }
    return l;
}
```

### Java
```java
int minEatingSpeed(int[] piles, int h) {
    int l = 1, r = Arrays.stream(piles).max().getAsInt();
    while (l < r) {
        int m = l + (r - l) / 2; long hrs = 0;
        for (int p : piles) hrs += (p + m - 1) / m;
        if (hrs <= h) r = m; else l = m + 1;
    }
    return l;
}
```

### Go
```go
func minEatingSpeed(piles []int, h int) int {
    l, r := 1, 0
    for _, p := range piles { if p > r { r = p } }
    for l < r {
        m := (l + r) / 2; hrs := 0
        for _, p := range piles { hrs += (p + m - 1) / m }
        if hrs <= h { r = m } else { l = m + 1 }
    }
    return l
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Integer division truncation vs ceiling division `(p + k - 1) // k`.

### Follow-ups
- Capacity To Ship Packages Within D Days uses identical binary search on answer capacity.