Koko Eating Bananas

MediumBinary SearchArrayBinary Search

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

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.

Related questions