Koko Eating Bananas
Last Updated: April 1, 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.
A couple of things to notice. First, increasing k can only decrease the total hours (or keep it the same). This means there's a clear threshold: every speed at or above some minimum value works, and everything below it doesn't. That monotonic property is the key. Second, Koko never moves on to a second pile in the same hour. Even if she finishes a pile early, the remaining time in that hour is wasted. So the total time is the sum of ceil(p / k) for each pile.
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
The simplest idea: 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), which is the maximum possible time. At speed max(piles), every pile takes at most 1 hour, so the total is n, which is the minimum possible time. Since h >= n, speed max(piles) always works, so we're guaranteed to find an answer.
For each candidate speed k, computing the total hours is straightforward: for each pile, the hours needed is ceil(piles[i] / k). A clean way to compute this without floating point is (piles[i] + k - 1) / k, which is the standard integer ceiling division trick.
Algorithm
- Find
maxPile, the maximum value inpiles. - For each speed
kfrom 1 tomaxPile: - Compute
totalHours= sum ofceil(piles[i] / k)for all piles. - If
totalHours <= h, returnk. - Return
maxPile(this line is technically unreachable sincemaxPilealways works).
Example Walkthrough
Code
- Time Complexity: O(n * max(piles)). For each of the max(piles) candidate speeds, we iterate through all n piles. With max(piles) up to 10^9, this is far too slow.
- Space Complexity: O(1). Only uses a few variables. No extra data structures.
The brute force tries every speed sequentially, but the feasibility function is monotonic. What if we could eliminate half the search range at each step instead?
Approach 2: Binary Search on Answer
Intuition
Here's the key insight that unlocks this problem: the feasibility of a speed is monotonic. If Koko can finish at speed k, she can definitely finish at any speed greater than k. If she can't finish at speed k, she can't finish at any speed less than k either. This is the classic setup for "binary search on the answer."
Instead of trying every speed one by one, we binary search over the range [1, max(piles)]. At each step, we pick the middle speed, check if it's feasible, and eliminate half the range. The feasibility check is simple: compute the total hours needed at that speed and compare 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 pattern used in problems like Search Insert Position, but instead of searching within an array, we're searching over an abstract answer space.
The total hours function is monotonically non-increasing as speed increases. At speed 1, total hours is maximized (sum of all pile sizes). At speed max(piles), total hours is minimized (one hour per pile, so total = n). Since h >= n, there's always a valid answer in [1, max(piles)].
Binary search exploits this monotonicity. At each step, if the middle speed is feasible, the answer is at mid or lower. If it's not feasible, the answer must be higher than mid. This halves the search range each time, giving us the answer in O(log(max(piles))) iterations.
Algorithm
- Set
left = 1andright = max(piles). - While
left < right: - Compute
mid = left + (right - left) / 2. - Calculate
totalHours= sum ofceil(piles[i] / mid)for all piles. - If
totalHours <= h, this speed works, but there might be a slower speed that also works. Setright = mid. - Otherwise, this speed is too slow. Set
left = mid + 1. - Return
left.
Example Walkthrough
Code
- Time Complexity: O(n * log(max(piles))). Binary search runs O(log(max(piles))) iterations (at most ~30 for max(piles) = 10^9). Each iteration computes the total hours in O(n).
- Space Complexity: O(1). Only uses a few integer variables. No extra data structures needed.