Skip to content
16-Week DSA Roadmap
LeetCode #875MediumProblem 2 of 8

Koko Eating Bananas

Find the slowest eating speed that still finishes every pile of bananas in h hours, by binary searching over the speeds.

  • Binary search on the answer
  • Feasibility check

Before this, know: Classic binary search (week 3), Rounding up a division (ceiling)

The problem in plain English

Koko the gorilla has some piles of bananas, piles, and h hours before the guards come back. She picks one eating speed k: how many bananas she eats per hour. Each hour she picks one pile and eats up to k bananas from it. If the pile has fewer than k, she finishes it and wastes the rest of that hour (she won’t start another pile in the same hour).

Return the smallest whole-number speed k that lets her finish every pile within h hours.

Example: piles = [3, 6, 7, 11], h = 8. The answer is 4:

piles
  1. 3
  2. 6
  3. 7
  4. 11
hours at speed 4
  1. 1
  2. 2
  3. 2
  4. 3
At 4 bananas per hour: pile 3 takes 1 hour, 6 takes 2, 7 takes 2, 11 takes 3. Total 8 hours, which fits in h = 8. Speed 3 would need 10 hours, too many.

The rules that matter:

  • h is at least the number of piles, so an answer always exists.
  • Piles can be huge: up to 1,000,000,000 bananas. Keep that number in mind.

Rounding up: the ceiling

How many hours does one pile take at speed k? Pile 7 at speed 4: after 1 hour she has eaten 4 and 3 are left. Those 3 still cost a whole second hour. So it’s 7 ÷ 4 = 1.75, rounded up to 2.

Rounding up is called the ceiling, written ⌈x⌉. In JavaScript it’s Math.ceil(x), in Python math.ceil(x). ⌈1.75⌉ = 2, ⌈2⌉ = 2, ⌈0.5⌉ = 1.

Before you code: think it through

The question isn’t “find a value in an array” any more. It’s “find the smallest number that works”. The key is how “works” behaves as the speed grows:

speed k (red: too slow, green: finishes in 8 hours)
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
For piles [3, 6, 7, 11] and h = 8: speeds 1, 2, 3 are too slow (red); 4 and everything faster works (green). The answer is where red turns green.

Eating faster never takes more hours. So the answers line up as no, no, no, yes, yes, yes: one switch from no to yes. Whenever answers line up like that, binary search can find the switch.

Pause and think

piles = [3, 6, 7, 11], h = 8. We test speed 6 and it takes 6 hours (fast enough). Which speeds can we cross off without testing them?

Approach 1: Brute force

Try speed 1. If she can’t finish in time, try 2, then 3, and so on. The first speed that works is the answer.

Brute force: try 1, 2, 3, ... bananas per hour

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

speed k (bananas per hour)
1234567891011
piles (bananas)
  1. 3
  2. 6
  3. 7
  4. 11
hours per pile
variables
h (hours we have)
8
k (speed)
—
total hours
—
answer
—
  • Too slow
  • Fast enough

Start with the slowest possible speed, k = 1, and go up one at a time.

Step 1 / 6

Which line is running?

function minEatingSpeed(piles, h) {Running now:   let k = 1;  while (true) {    let hours = 0;    for (const pile of piles) {      hours += Math.ceil(pile / k);    }    if (hours <= h) return k; // the first speed that is fast enough    k++; // too slow: try one banana per hour faster  }}

Brute force: try every speed

function minEatingSpeed(piles, h) {  let k = 1;  while (true) {    let hours = 0;    for (const pile of piles) {      hours += Math.ceil(pile / k);    }    if (hours <= h) return k; // the first speed that is fast enough    k++; // too slow: try one banana per hour faster  }}
import mathdef min_eating_speed(piles, h):    k = 1    while True:        hours = 0        for pile in piles:            hours += math.ceil(pile / k)        if hours <= h:            return k  # the first speed that is fast enough        k += 1  # too slow: try one banana per hour faster

Why is it slow?

Each try walks over all n piles. For [3, 6, 7, 11] the answer is 4, so that’s 4 tries × 4 piles = 16 small steps. Fine.

But with a pile of 1,000,000,000 bananas and very little time, the answer can be close to a billion. That’s up to a billion tries, each walking all the piles (up to 10,000): about 10¹³ steps. The time is O(n × m), where m is the biggest pile. Far too slow.

The pattern: binary search on the answer

In week 3 you binary searched an array for a value. Here there’s no array to search. Instead we search the range of possible answers, 1 to the biggest pile, and at each guess we ask a yes/no question: “is this speed fast enough?” That yes/no function is called a feasibility check (“feasible” means “it works”).

Pattern

Binary search on the answer

Template

Use it when: you need the minimum (or maximum) value that satisfies a condition, and if a value works then every bigger (or smaller) one works too.

Signal words

  • “minimum speed”
  • “smallest capacity”
  • “at least”
  • “within h hours”
  • “minimize the maximum”

Approach 2: Binary search on the speed

  1. The answer is between lo = 1 (slowest that makes sense) and hi = max(piles). At the biggest pile’s speed every pile takes 1 hour, so hi always works.
  2. While lo < hi: try mid = (lo + hi) // 2.
  3. Add up the hours at speed mid: ⌈pile / mid⌉ for every pile.
  4. If the total is ≤ h, mid works. The answer is mid or slower: hi = mid (keep mid, it might be the answer).
  5. Otherwise mid is too slow, and so is everything slower: lo = mid + 1.
  6. When lo === hi, only one speed is left, and it’s the answer.

Watch the number line at the top: the shaded band is the speeds still possible. Red dots are speeds we found too slow, green dots are speeds that work. The first round shows each pile’s ceiling one at a time; later rounds do it in one step.

Binary search on the eating speed

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

speed k (bananas per hour)
1234567891011lo=1
piles (bananas)
  1. 3
  2. 6
  3. 7
  4. 11
hours per pile
variables
h (hours we have)
8
mid (speed)
—
total hours
—
lo
1
hi
—
answer
—
  • Speeds still possible (lo..hi)
  • Too slow
  • Fast enough
  • Pile being worked out

The answer is a speed k (bananas per hour). Speed 0 makes no sense, so the slowest speed worth trying is lo = 1.

Step 1 / 22

Which line is running?

function minEatingSpeed(piles, h) {Running now:   let lo = 1; // slowest speed that makes sense  let hi = Math.max(...piles); // this speed always works  while (lo < hi) {    const mid = Math.floor((lo + hi) / 2);    let hours = 0;    for (const pile of piles) {      hours += Math.ceil(pile / mid); // a partly eaten pile still costs a full hour    }    if (hours <= h) {      hi = mid; // fast enough: the answer is mid or slower    } else {      lo = mid + 1; // too slow: the answer is faster than mid    }  }  return lo; // lo === hi: the slowest speed that works}

Try the “h = number of piles” edge case: with only 4 hours for 4 piles, Koko must finish one whole pile every hour, so the answer is the biggest pile, 11.

The code, line by line

Binary search on the speed

function minEatingSpeed(piles, h) {  let lo = 1; // slowest speed that makes sense  let hi = Math.max(...piles); // this speed always works  while (lo < hi) {    const mid = Math.floor((lo + hi) / 2);    let hours = 0;    for (const pile of piles) {      hours += Math.ceil(pile / mid); // a partly eaten pile still costs a full hour    }    if (hours <= h) {      hi = mid; // fast enough: the answer is mid or slower    } else {      lo = mid + 1; // too slow: the answer is faster than mid    }  }  return lo; // lo === hi: the slowest speed that works}
import mathdef min_eating_speed(piles, h):    lo = 1  # slowest speed that makes sense    hi = max(piles)  # this speed always works    while lo < hi:        mid = (lo + hi) // 2        hours = 0        for pile in piles:            hours += math.ceil(pile / mid)  # a partly eaten pile still costs a full hour        if hours <= h:            hi = mid  # fast enough: the answer is mid or slower        else:            lo = mid + 1  # too slow: the answer is faster than mid    return lo  # lo == hi: the slowest speed that works

Python needs import math at the top (for math.ceil), so its line numbers run two ahead of JavaScript’s. On LeetCode the Python function sits inside class Solution as def minEatingSpeed(self, piles, h).

  • JS 2 / Py 4: the slowest speed worth trying. Speed 0 would never finish.
  • JS 3 / Py 5: the fastest speed we ever need. Math.max(...piles) spreads the array into Math.max; Python’s max(piles) does the same.
  • JS 4 / Py 6: lo < hi, not lo <= hi. We stop when one candidate is left, because we already know the range always contains a working speed.
  • JS 5 / Py 7: the speed to test, rounded down.
  • JS 6–9 / Py 8–10: the feasibility check. For each pile, the hours are the pile divided by the speed, rounded up, because a partly eaten pile still uses a full hour.
  • JS 10–11 / Py 11–12: fast enough. Set hi = mid, not mid − 1: mid itself might be the smallest working speed, so we must keep it in the range.
  • JS 13 / Py 14: too slow. mid can’t be the answer, so lo = mid + 1.
  • JS 16 / Py 15: lo and hi are equal, and that speed is the answer.

Dry run

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

lohimidhours per piletotal≤ 8?next
11161, 1, 2, 26yeshi = 6
1631, 2, 3, 410nolo = 4
4651, 2, 2, 38yeshi = 5
4541, 2, 2, 38yeshi = 4
44———lo = hireturn 4
piles = [3, 6, 7, 11], h = 8

Look at the rows where mid = 5 and mid = 4: both speeds need exactly 8 hours. Binary search doesn’t stop at the first speed that works (5); it keeps squeezing hi down to find the slowest one.

after testing 6: 1..6
1234567891011lo=1hi=6
after testing 3: 4..6
1234567891011lo=4hi=6
after testing 5 and 4: answer 4
1234567891011lo=4answer=4
The same search on the number line: the band of possible speeds after each test. 11 speeds, 4 tests.

Complexity

Brute force

Time

O(n × m)

Up to m speeds (m = the biggest pile), and each one walks all n piles. With m = 1,000,000,000 that's hopeless.

Space

O(1)

Just k and a running total.

Binary search on the speed

Time

O(n × log m)

Each test halves the range of speeds, so about log₂(m) tests: for m = 1,000,000,000 that's only about 30. Each test walks the n piles.

Space

O(1)

lo, hi, mid and a running total.

From a billion tries down to about thirty. That’s what “binary search on the answer” buys you.

Common mistakes and edge cases

What to say out loud:

  1. “I’m looking for the minimum speed. If a speed works, any faster one works too, so the yes/no answers are sorted.”
  2. “That means I can binary search on the speed, between 1 and the biggest pile.”
  3. “The check for one speed is a pass over the piles with a ceiling division.”
  4. “That’s O(n log m) instead of O(n × m).”
  5. Mention the ceiling and the hi = mid detail before you’re asked.

Likely follow-ups:

  • “Why is max(piles) enough for hi?” Because at that speed every pile takes one hour, and h ≥ len(piles).
  • “Could you make the check faster?” Not really; each speed needs to look at every pile once.

Related problems (same pattern):

  • Capacity To Ship Packages Within D Days (LeetCode 1011) and Split Array Largest Sum (LeetCode 410): search the answer, check feasibility greedily.
  • Sqrt(x) (LeetCode 69): the biggest x whose square is ≤ n.
  • More on this pattern in the week 4 overview.