AlgoMaster Logo

Koko Eating Bananas

medium5 min readUpdated June 23, 2026

Understanding the Problem

We need to find the minimum eating speed k that lets Koko finish all bananas within h hours. At speed k, each pile of size p takes ceil(p / k) hours to eat. The total hours across all piles must be at most h.

Two properties shape the solution. Increasing k can only decrease the total hours, or keep it the same, never increase it. That gives a clear threshold: every speed at or above some minimum value works, and everything below it does not. Koko also never moves on to a second pile within the same hour. If she finishes a pile early, the rest of that hour is wasted, so the total time is the sum of ceil(p / k) over all piles.

The question boils down to: what is the smallest k such that the sum of ceil(piles[i] / k) across all piles is at most h?

Key Constraints:

  • 1 <= piles.length <= 10^4 → Up to 10,000 piles. For each candidate speed, computing the total hours is O(n), which is fine.
  • piles.length <= h <= 10^9 → h is always at least the number of piles (Koko needs at least one hour per pile). h can be very large, which means very low speeds could work.
  • 1 <= piles[i] <= 10^9 → Pile sizes can be huge. The maximum possible speed we'd ever need is max(piles), since at that speed every pile takes exactly 1 hour.

Approach 1: Brute Force (Linear Search)

Intuition

Try every possible speed starting from 1, and for each speed, calculate how many hours Koko needs. Return the first speed where the total hours is at most h.

The speed range is [1, max(piles)]. At speed 1, every banana takes one hour, so the total is sum(piles), the maximum possible time. At speed max(piles), every pile takes at most 1 hour, so the total is n, the minimum possible time. Since h >= n, speed max(piles) always works, so an answer always exists in this range.

For each candidate speed k, the hours needed for a pile is ceil(piles[i] / k). To compute this without floating point, use (piles[i] + k - 1) / k, the integer form of ceiling division.

Algorithm

  1. Find maxPile, the maximum value in piles.
  2. For each speed k from 1 to maxPile:
    • Compute totalHours = sum of ceil(piles[i] / k) for all piles.
    • If totalHours <= h, return k.
  3. Return maxPile (this line is technically unreachable since maxPile always works).

Example Walkthrough

1Start: try k=1. hours = ceil(3/1)+ceil(6/1)+ceil(7/1)+ceil(11/1) = 27. 27 > 8, too slow.
0
3
1
6
2
7
3
11
1/5

Code

The brute force tries every speed sequentially. Because feasibility is monotonic, the next approach uses binary search to eliminate half the remaining range at each step.

Approach 2: Binary Search on Answer

Intuition

The feasibility of a speed is monotonic. If Koko can finish at speed k, she can finish at any speed greater than k. If she cannot finish at speed k, she cannot finish at any speed less than k. This is the setup for binary search on the answer.

Instead of trying every speed one by one, binary search over the range [1, max(piles)]. At each step, pick the middle speed, check if it is feasible, and eliminate half the range. The feasibility check computes the total hours at that speed and compares it with h.

The search finds the lower bound: the smallest speed where the total hours is at most h. This is the same lower-bound binary search used to find an insertion point in a sorted array, except the search space here is the abstract range of possible speeds rather than array indices.

Algorithm

  1. Set left = 1 and right = max(piles).
  2. While left < right:
    • Compute mid = left + (right - left) / 2.
    • Calculate totalHours = sum of ceil(piles[i] / mid) for all piles.
    • If totalHours <= h, this speed works, but there might be a slower speed that also works. Set right = mid.
    • Otherwise, this speed is too slow. Set left = mid + 1.
  3. Return left.

Example Walkthrough

1Initialize: search range [1, 11], left=1, right=11
0
3
1
6
2
7
3
11
1/6

Code