Skip to main content
DSA patterns

Koko Eating Bananas

mediumBinary search Must-doUberSnowflakeElastic

Problem statement

There are several piles of bananas, and Koko has h hours before the guards return. She picks one constant eating speed k (bananas per hour) and keeps it for the whole time. Each hour she picks one pile and eats k bananas from it — or, if the pile has fewer than k left, she finishes that pile and stops for the hour (she doesn't move on to another pile in the same hour).

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

Examples

Example 1

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

Output: 4

Explanation: at speed 4, the piles take 1 + 2 + 2 + 3 = 8 hours (each pile's hours are its size divided by 4, rounded up). That exactly fits the 8-hour budget, and no slower speed does.

Example 2

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

Output: 30

Explanation: with only 5 hours and 5 piles, Koko has exactly one hour per pile, so she has to clear the biggest pile — 30 bananas — in a single hour.

Example 3

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

Output: 23

Explanation: with one extra hour to spare, a speed of 23 works: the piles take 2 + 1 + 1 + 1 + 1 = 6 hours.

Hints

Hint 1: Try thinking about it backwards: instead of asking "how fast does Koko need to eat", ask "for a given speed, how many hours would it take?" — that's a much easier question to answer.

Approach

Optimal: Binary search on the speed

Intuition

The brute-force approach checks every speed one at a time, but it doesn't need to: as speed goes up, the hours needed only ever goes down (never up). That's a monotonic relationship — exactly the shape binary search is built for. Instead of searching a sorted list of values, this binary searches a sorted list of possible answers: every speed from 1 to the biggest pile, ordered from slowest to fastest. At each guess, check whether that speed finishes in time; if it does, it's a candidate, but try an even slower one; if it doesn't, this speed and everything slower is out, so try faster.

Steps

  1. Set left = 1 (the slowest speed worth trying) and right = max(piles) (the fastest speed worth trying — nothing faster helps, since it never takes less than one hour to clear a pile).
  2. While left <= right: let speed = (left + right) // 2.
  3. Compute the total hours at this speed, the same way as the brute-force approach.
  4. If the hours fit within h, this speed works — remember it, then try to find something slower: right = speed - 1.
  5. Otherwise this speed is too slow — search faster speeds: left = speed + 1.
  6. Once the loop ends, the smallest working speed found is the answer.

Dry run

piles = [3, 6, 7, 11], h = 8. Speed range starts at [1, 11].

step left right speed hours fits? action
1 1 11 6 1+1+2+2 = 6 yes remember 6, try slower → right = 5
2 1 5 3 1+2+3+4 = 10 no too slow → left = 4
3 4 5 4 1+2+2+3 = 8 yes remember 4, try slower → right = 3
end 4 3 — — — left > right → return 4

Edge cases: a single pile with h = 1 forces speed up to that pile's full size, since there's only one hour to clear it — the binary search still finds that correctly because right starts at exactly that pile's size.

Complexity

Time O(n log m) - Binary search over the speed range `[1, m]` takes about log₂(m) steps, and each step costs O(n) to add up the hours across all piles.

Space O(1) - Two or three index-like variables, regardless of how many piles there are or how big they are.

import math


class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left, right = 1, max(piles)
        res = right
        while left <= right:
            speed = (left + right) // 2
            hours = sum(math.ceil(pile / speed) for pile in piles)
            if hours <= h:
                res = speed
                right = speed - 1
            else:
                left = speed + 1
        return res


if __name__ == "__main__":
    print(Solution().minEatingSpeed([3, 6, 7, 11], 8))  # 4
    print(Solution().minEatingSpeed([30, 11, 23, 4, 20], 5))  # 30
    print(Solution().minEatingSpeed([30, 11, 23, 4, 20], 6))  # 23
RecapThe whole problem in a few lines, for the night before
  • Spot it: "minimum/maximum value that satisfies a condition, and the condition gets easier as the value increases" — binary search on the answer, not on an array
  • Idea: binary search over the range of possible speeds; at each guess, simulate whether that speed finishes in time
  • Cost: O(n log m) time, O(1) space, where n is the number of piles and m is the largest pile
  • Trap: using integer division instead of rounding up when computing hours per pile — a partial hour still costs a full hour

Interview follow-ups

  • The piles can now be refilled while Koko eats — new bananas can arrive mid-run. How would that change things?

    The monotonic relationship that makes binary search work — faster speed always means fewer or equal hours — no longer holds cleanly if the total workload can grow while she's still eating, since a speed that used to be "fast enough" might not stay that way. You'd need to know the arrival pattern (a fixed total by a deadline, or an ongoing rate) to decide whether this is still a single binary search or needs to become an ongoing rate-vs-arrival-rate comparison, closer to a queueing problem than a one-shot search.

  • h can now be enormous — up to 10^9 as the constraints allow — while there are relatively few piles. Does the approach still hold up?

    Yes, without any change: the binary search's cost depends on the size of the speed range (bounded by the largest pile, at most 10^9) and the number of piles, not on h itself — h only appears as a comparison value inside each check, so an enormous h just makes it more likely that a slow speed already succeeds, which the search finds just as quickly.

Frequently asked questions

Binary search only needs one thing: a range of candidate answers where "does this answer work?" flips from no to yes (or yes to no) exactly once as you move through the range. Here the candidates are speeds from 1 to the biggest pile, and "finishes within h hours" goes from false to true as speed increases and never flips back — that single flip is what makes binary search valid, whether or not there's an actual array involved.

A speed of 0 bananas per hour would mean Koko eats nothing, ever, and no finite number of hours could clear a nonempty pile — worse, it would make the hours-per-pile division blow up. The smallest speed that could possibly work is 1, so that's the natural lower bound.

Because Koko doesn't get credit for a partial hour. If a pile has 7 bananas and she eats 4 per hour, she needs 2 hours: 4 in the first, 3 in the second, and that second hour is spent even though she didn't eat a full 4. Rounding down would undercount the hours and could make an invalid speed look valid.

This is a rate-sizing problem: given a fixed amount of work (bananas) and a fixed deadline (hours), find the minimum throughput (bananas per hour) that clears it in time. The same shape shows up when sizing a worker pool's processing rate to drain a queue before an SLA, or picking the minimum bandwidth that finishes a batch of transfers within a maintenance window.