Koko Eating Bananas

Try It Yourself

Use the editor below to search possible eating speeds rather than array positions. For each candidate speed, calculate how many whole hours all piles require.

Submit your implementation when it passes the examples. The answer may be one, the largest pile, or a speed between them.

Koko Eating Bananas

mediumBinary Search on Answer · Arrays35 minLC 875

Problem

Koko has several piles of bananas and h hours. At an integer speed k, she spends one hour consuming up to k bananas from one pile.

Return the smallest speed that lets her finish every pile within h hours.

Example 1:

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

Output: 4

Example 2:

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

Output: 30

Constraints

1 ≤ piles.length ≤ h ≤ 100,000
1 ≤ piles[i] ≤ 1,000,000,000

0 attempts

Solution

Possible speeds form an ordered range from 1 through the largest pile. A candidate is feasible when the sum of each pile's rounded-up division by that speed is no more than h.

If a speed is feasible, keep it as a possible answer and search lower speeds. Otherwise, discard it and every slower speed.

function minEatingSpeed(piles, h) {
  let left = 1;
  let right = Math.max(...piles);

  while (left < right) {
    const speed = left + Math.floor((right - left) / 2);
    let hours = 0;

    for (const pile of piles) {
      hours += Math.ceil(pile / speed);
    }

    if (hours <= h) right = speed;
    else left = speed + 1;
  }

  return left;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n log m)`	Each of log m candidate speeds scans all n piles, where m is the largest pile.
Auxiliary space	`O(1)`	Only search boundaries and the current hour total are stored.