Koko Eating Bananas

Difficulty: Medium

Koko has several piles of bananas and h hours before the guards return. She picks one eating speed k (bananas per hour) and uses that same speed for every hour of the day.

Each hour, she chooses one pile and eats up to k bananas from it. If that pile has fewer than k bananas left, she finishes it off and simply doesn't eat any faster that hour — she doesn't move on to another pile until the next hour.

Find the smallest whole-number eating speed k that lets Koko finish every pile within h hours.

Examples

Input: piles = [3, 6, 7, 11], h = 8
Output: 4

At speed 4, the hours needed are ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8, which just fits. Any slower speed would take more than 8 hours.

Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30

With only 5 hours for 5 piles, Koko gets exactly one hour per pile, so she must be fast enough to clear the biggest pile, 30, in a single hour.

Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23

At speed 23 the hours needed add up to exactly 6; speed 22 would need 7 hours, which is too slow.

Constraints

1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9

Approach

The direct way is to try every possible speed starting from 1 and stop at the first one that finishes in time. That's correct, but the number of possible speeds can be as large as the biggest pile, which is slow.

The key observation is that "hours needed" only ever decreases as speed increases — eating faster never takes longer. That means every possible speed falls into one of two groups: "too slow" (needs more than h hours) or "fast enough" (needs at most h hours), with every "too slow" speed below every "fast enough" one. Whenever a yes/no question has this kind of clean boundary, you can binary search directly over the candidate answers — here, the possible speeds — instead of over an array, narrowing in on the smallest speed that's "fast enough."

Solutions

Brute Force — Try Every Speed

Starting from speed 1, check how many hours that speed would need, and stop at the first speed that fits within h hours.

function minEatingSpeed(piles, h) {
  const hoursNeeded = (speed) => {
    let hours = 0;
    for (const pile of piles) {
      hours += Math.ceil(pile / speed);
    }
    return hours;
  };

  let speed = 1;
  while (hoursNeeded(speed) > h) {
    speed++;
  }
  return speed;
}

Time: O(n * max(piles)) · Space: O(1)

Optimal — Binary Search on the Answer

Binary search over possible speeds, from 1 to the largest pile. At each candidate speed, check the hours needed; if it fits within h hours, try a slower speed, otherwise try a faster one.

function minEatingSpeed(piles, h) {
  const hoursNeeded = (speed) => {
    let hours = 0;
    for (const pile of piles) {
      hours += Math.ceil(pile / speed);
    }
    return hours;
  };

  let low = 1;
  let high = Math.max(...piles);

  while (low < high) {
    const mid = Math.floor((low + high) / 2);

    if (hoursNeeded(mid) <= h) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

Time: O(n * log(max(piles))) · Space: O(1)