MediumBinary SearchArrayGreedy

Koko Eating Bananas

1 approach, code in every language

You are given a list of banana piles, where the value at each position tells you how many bananas sit in that pile. You also have a deadline of h hours before the piles are taken away. Each hour you pick a single pile and eat up to a fixed speed of k bananas from it; if the pile has fewer than k bananas left you finish it and idle for the rest of that hour, but you never switch to a second pile within the same hour.

Your goal is to find the smallest whole-number speed k that still lets you clear every pile within h hours. Larger speeds always make the job easier, so the answer is the exact point where 'just fast enough' begins.

Example 1

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

Output: 4

At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours, exactly meeting the deadline. Speed 3 would need 1 + 2 + 3 + 4 = 10 hours, which is too slow.

Example 2

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

Output: 30

There are 5 piles and only 5 hours, so each pile must be cleared in a single hour. The speed therefore has to be at least the size of the largest pile, which is 30.

Constraints

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

Binary Search on Eating Speed

Search the space of possible speeds between 1 and the largest pile, using a feasibility check that sums the hours required at a candidate speed.

Loading animation…

Intuition

The number of hours needed is a monotonic function of the speed: as k grows the total hours can only stay the same or shrink. That monotonic shape is exactly what binary search needs. Instead of testing every speed, we probe the middle speed, decide whether it finishes in time, and discard half of the remaining range each step. The smallest speed that keeps the total hours within the deadline is the answer.

Algorithm walkthrough

1Set the search window to lo = 1 and hi = the maximum pile size, since no faster speed is ever required.
2Pick mid as the middle speed and compute the total hours as the sum of ceil(pile / mid) across all piles.
3If the total hours are within h, this speed works, so shrink the window by moving hi down to mid.
4If the total hours exceed h, mid is too slow, so move lo up to mid + 1.
5When lo meets hi the window has collapsed onto the smallest feasible speed; return it.

Implementation

from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            hours = sum((p + mid - 1) // mid for p in piles)
            if hours <= h:
                hi = mid
            else:
                lo = mid + 1
        return lo

Time

O(n log m), where n is the number of piles and m is the largest pile

Space

O(1)

Each binary search step scans all piles once; the number of steps is logarithmic in the maximum pile size.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Overnight Print Rate is our own problem on the technique behind Koko Eating Bananas: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free