Koko Eating Bananas
Koko loves bananas. There are piles of bananas, the ith pile has pilesi bananas, and h hours until the guards come back. Koko picks a speed of k bananas per hour. Each hour she chooses one pile and eats k bananas from it; if the pile has fewer than k bananas left, she eats them all and does not touch another pile that hour. Koko wants to finish all the piles before the guards return. Return the minimum integer k such that she can eat all the bananas within h hours. This is binary search on the answer : search over candidate speeds from 1 to max(piles), checking at each guess whether that speed finishes in time.
Constraints
- 1 ≤ piles.length ≤ 104
- piles.length ≤ h ≤ 109
- 1 ≤ pilesi ≤ 109
Example
piles = [3, 6, 7, 11], h = 84Explanation At speed 4, Koko needs ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8 hours, exactly the budget.
In plain terms
- Binary search on the answer
- Instead of searching an array, you search over the range of possible answers, halving that range using a feasibility check instead of an array comparison.
Binary search over eating speeds for the smallest feasible one
low=1, high=7, mid=4. Speed 4 needs 5 hours, which is within 6 — feasible, so try slower.
What happens in this step
low=1, high=7 mid = 1 + floor((7-1)/2) = 4 Hours at speed 4: ceil(3/4) + ceil(6/4) + ceil(7/4) = 1 + 2 + 2 = 5 5 <= 6, so speed 4 finishes in time. A slower speed might still work, so keep 4 as a candidate and pull high down to it: high becomes 4. Every speed above 4 is discarded.
Steps to visualize
- The walkthrough uses a smaller example: piles = [3, 6, 7] with h = 6 hours.
- The row is every speed Koko could pick, from 1 up to the biggest pile (7).
- A cell shows the hours that speed needs, and stays blank until the search actually checks it.
- The box marks the speeds still in play; start it across the whole row.
- Check the speed in the middle. If it finishes within h hours it is feasible, so pull high down to it and try slower.
- If it does not finish in time, that speed is too slow — move low past it.
- When low and high meet, that speed is the smallest one that works.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
low=1, high=7, mid=4. Speed 4 needs 5 hours, which is within 6 — feasible, so try slower.
What happens in this step
low=1, high=7 mid = 1 + floor((7-1)/2) = 4 Hours at speed 4: ceil(3/4) + ceil(6/4) + ceil(7/4) = 1 + 2 + 2 = 5 5 <= 6, so speed 4 finishes in time. A slower speed might still work, so keep 4 as a candidate and pull high down to it: high becomes 4. Every speed above 4 is discarded.
Solution
function minEatingSpeed(piles, h) {
let low = 1;
let high = Math.max(...piles);
function hoursNeeded(speed) {
let hours = 0;
for (const pile of piles) {
hours += Math.ceil(pile / speed);
}
return hours;
}
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (hoursNeeded(mid) <= h) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}- Time
- O(n log m)
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
piles = [3, 6, 7, 11], h = 8 | 4 | example from the docstring |
piles = [30, 11, 23, 4, 20], h = 5 | 30 | very tight hour budget forces the fastest possible speed |
piles = [30, 11, 23, 4, 20], h = 6 | 23 | one extra hour of budget lowers the required speed |
piles = [5], h = 3 | 2 | a single pile with a small hour budget |
piles = [1, 1, 1, 1], h = 4 | 1 | exactly one hour per pile, minimum possible speed suffices |
piles = [3, 6, 7, 11], h = 4 | 11 | h equals the number of piles, forcing the fastest speed possible |
piles = [1000000000], h = 2 | 500000000 | large values exercising the logarithmic search over speeds |