# Koko Eating Bananas

> How to solve Koko Eating Bananas: binary search over eating speed to find the slowest pace that still finishes every pile in time.

- Difficulty: Medium
- Category: Binary Search
- Topics: Array, Binary Search
- Published 2026-08-21

## Problem

Koko has several piles of bananas and a fixed number of hours before the guards return. Each hour she picks one pile and eats up to some fixed speed's worth of bananas from it; a pile with fewer bananas left than her speed finishes early, and the leftover hour is wasted. Find the smallest whole-number eating speed that clears every pile in time.

**Example.** With piles `[3, 6, 7, 11]` and `8` hours, the smallest working speed is `4`: the piles take `1`, `2`, `2`, and `3` hours, totaling `8`.

## Key idea

Testing every possible speed would work, but the range of plausible speeds can be large. The relationship between speed and total hours is monotonic: a faster speed never increases the hours needed, and a slower speed never decreases them. A monotonic condition like this means the smallest satisfying speed can be found with binary search over the speed itself, not the array.

Set a low bound of one banana per hour and a high bound equal to the largest pile, since eating faster offers no benefit. For a candidate speed at the midpoint, simulate the hours needed across all piles, rounding each pile up to a whole hour. If the total fits the limit, record the speed and try slower; otherwise increase it.

## Solution

```typescript
function minEatingSpeed(piles: number[], h: number): number {
  let low = 1;
  // eating faster than the largest pile never helps, so it is a safe upper bound
  let high = Math.max(...piles);
  let slowestWorking = high;

  while (low <= high) {
    const speed = low + Math.floor((high - low) / 2);
    // round each pile up, since a leftover hour on one pile cannot carry to another
    const hoursNeeded = piles.reduce((total, pile) => total + Math.ceil(pile / speed), 0);

    if (hoursNeeded <= h) {
      // this speed works, remember it and try an even slower one
      slowestWorking = speed;
      high = speed - 1;
    } else {
      low = speed + 1;
    }
  }

  return slowestWorking;
}
```

## Complexity

- **Time:** O(n log m). Each of the O(log m) candidate speeds requires an O(n) pass over the piles, where m is the largest pile size.
- **Space:** O(1). Only the search bounds and a running hour total are needed.

## Watch out for

- Each pile's hours must be rounded up, not truncated, since a leftover hour on one pile cannot carry into another.
- The upper bound must guarantee success; the largest pile size always works, since one pile per hour finishes in at most n hours.

## Pattern

This is "binary search on the answer": instead of searching an array for a value, you search a range of candidate answers using a feasibility check that flips monotonically at one threshold. The same shape applies to minimizing the largest split sum or the slowest allowable shipment capacity.

---

Canonical URL: https://www.marauderbot.com/questions/koko-eating-bananas
