Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Koko Eating Bananas

Find the slowest eating speed that clears every pile of bananas within h hours by binary searching the range of speeds, in O(n log m) time.

Updated Medium read: 8 min read

Approaches at a glance

ApproachTimeSpace
Try every speedO(n × m)O(1)
Binary search on the speedO(n log m)O(1)

The problem

Koko has several piles of bananas; piles[i] is the number of bananas in pile i. She has h hours to eat them all.

She chooses one eating speed, a whole number of bananas per hour, and keeps to it. Each hour she picks a single pile and eats up to that many bananas from it. If the pile has fewer bananas left than her speed, she finishes the pile and then waits: she does not start another pile until the next hour.

Return the smallest speed at which every banana is eaten within h hours. There are never more piles than hours, so an answer always exists.

piles = [4, 9, 12, 7], h = 6    →  7
piles = [4, 9, 12, 7], h = 4    →  12   (one hour per pile: the speed must cover the largest pile)
piles = [4, 9, 12, 7], h = 10   →  4
piles = [30],          h = 7    →  5

How long one speed takes

Before looking for the best speed, work out how to judge a single one. A pile of 9 bananas at speed 4 takes three hours: 4, then 4, then the last 1. In general a pile takes pile / speed hours, rounded up, because a part-used hour is still an hour gone. The total is the sum over all piles.

piles = [4, 9, 12, 7], speed = 4
 
pile 4   →  1 hour
pile 9   →  3 hours
pile 12  →  3 hours
pile 7   →  2 hours
total    →  9 hours

Both approaches below use this calculation, so it gets a function of its own.

JavaScript

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

Python

def hours_needed(piles, speed):
    hours = 0
    for pile in piles:
        hours += (pile + speed - 1) // speed   # pile / speed, rounded up
    return hours

The Python version rounds up with whole numbers only. Adding speed - 1 before the floor division pushes any remainder over into the next whole hour, and avoids floating-point division altogether.

Approach 1: try every speed

Start at speed 1 and go up by one until the hours fit.

JavaScript

function minEatingSpeedBruteForce(piles, h) {
  let speed = 1;
  while (hoursNeeded(piles, speed) > h) {
    speed++;
  }
  return speed;
}

Python

def min_eating_speed_brute_force(piles, h):
    speed = 1
    while hours_needed(piles, speed) > h:
        speed += 1
    return speed

The loop must stop: at a speed equal to the largest pile, each pile takes exactly one hour, and there are at least as many hours as piles.

With n piles and a largest pile of m bananas, up to m speeds are tried and each costs one pass over the piles.

Time O(n × m). Space O(1).

A pile may hold a thousand million bananas. With ten thousand piles as well, that is far too slow.

Approach 2: binary search on the speed

Write the result of the test "does this speed finish within 6 hours?" under each speed for piles = [4, 9, 12, 7]:

speed:   1   2   3   4   5   6   7   8   9   10  11  12
hours:   32  17  12  9   8   7   6   6   5   5   5   4
in 6?    no  no  no  no  no  no  yes yes yes yes yes yes
                                 ↑
                    the smallest speed that passes

Eating faster never takes longer, so the hours only ever fall or stay level as the speed rises. Once a speed passes, every higher one passes too. The row of answers switches from "no" to "yes" exactly once, and binary search can find the switch without testing every speed. This is the "smallest value that passes" form of the binary search on the answer pattern.

Three decisions:

  • Range. The lowest speed is 1. The highest worth trying is the largest pile: anything faster still takes one hour per pile, so it gains nothing.
  • Test. hoursNeeded(piles, speed) <= h.
  • Direction. Failures come first. When the middle passes it may be the answer, so keep it (hi = mid). When it fails, drop it (lo = mid + 1).

JavaScript

function minEatingSpeed(piles, h) {
  let lo = 1;
  let hi = Math.max(...piles);
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (hoursNeeded(piles, mid) <= h) {
      hi = mid;        // fast enough: the answer is mid or slower
    } else {
      lo = mid + 1;    // too slow: the answer is faster
    }
  }
  return lo;
}

Python

def min_eating_speed(piles, h):
    lo = 1
    hi = max(piles)
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
 
        if hours_needed(piles, mid) <= h:
            hi = mid        # fast enough: the answer is mid or slower
        else:
            lo = mid + 1    # too slow: the answer is faster
    return lo

It is the same loop as the lower-bound search in Search Insert Position. There, the question asked of the middle was "is this element at least the target?". Here it is "is this speed fast enough?". Nothing else has changed.

Walkthrough

piles = [4, 9, 12, 7], h = 6. The range of speeds starts as 1 to 12.

lo hi mid Hours at speed mid Within 6? Action
1 12 6 1 + 2 + 2 + 2 = 7 No lo = 7
7 12 9 1 + 1 + 2 + 1 = 5 Yes hi = 9
7 9 8 1 + 2 + 2 + 1 = 6 Yes hi = 8
7 8 7 1 + 2 + 2 + 1 = 6 Yes hi = 7
7 7 lo equals hi: return 7

Four speeds were tested instead of seven. Speed 8 also finishes in six hours, which is why a passing speed cannot simply be returned: a slower one may pass too, and the search keeps going left until none does.

The range holds m speeds, so it is halved about log m times, and each test is one pass over n piles.

Time O(n log m). Space O(1).

Comparing the approaches

Approach Time Space Tests when the largest pile is 1,000,000,000
Try every speed O(n × m) O(1) Up to 1,000,000,000
Binary search on the speed O(n log m) O(1) About 30

The test is the same in both. All of the gain comes from choosing which speeds to test.

Why sorting the piles does not help

It is tempting to sort piles first because the word "binary search" is in the air. The piles are never searched. The search runs over speeds, which are consecutive whole numbers and so already in order. The piles are only added up, and a sum does not care about order.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python. minEatingSpeed calls hoursNeeded, so copy that function as well.

JavaScript

console.log(hoursNeeded([4, 9, 12, 7], 4)); // 9
console.log(minEatingSpeed([4, 9, 12, 7], 6)); // 7
console.log(minEatingSpeed([4, 9, 12, 7], 4)); // 12
console.log(minEatingSpeed([4, 9, 12, 7], 10)); // 4
console.log(minEatingSpeed([30], 7)); // 5

Python

print(hours_needed([4, 9, 12, 7], 4))  # 9
print(min_eating_speed([4, 9, 12, 7], 6))  # 7
print(min_eating_speed([4, 9, 12, 7], 4))  # 12
print(min_eating_speed([4, 9, 12, 7], 10))  # 4
print(min_eating_speed([30], 7))  # 5

The comment after each line is the result you should see.

Common mistakes

  • Starting the range at 0. Speed 0 divides by zero, and in JavaScript that quietly gives Infinity hours instead of an error. The slowest real speed is 1.
  • Rounding the hours down. Math.floor(pile / speed) says a pile of 9 at speed 4 takes two hours. The last banana needs a third.
  • Dividing the total by the speed. sum(piles) / speed assumes Koko can move to a new pile in the middle of an hour. She cannot, so each pile is rounded up separately.
  • Returning the first speed that passes. A slower speed might pass as well. Keep the passing speed in the range and carry on.
  • Using hi = mid - 1 with lo < hi. That throws away a speed that might be the answer. In this template the passing branch is hi = mid.
  • Setting the top of the range to the sum of the piles. It still works, but the largest pile is a tighter limit and just as easy to justify.
  • Overflow in other languages. With many large piles at a low speed, the hours can exceed a 32-bit integer. Use a 64-bit type in Java or C++.

Original problem: LeetCode 875: Koko Eating Bananas