Koko Eating Bananas
Asked at Amazon, Atlassian, Netflix
Problem
Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them and does not eat any more that hour. Find the minimum integer k such that she can eat all the bananas within h hours.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Netflix | Medium | View all Netflix questions → |
How to Think About It
Brute force: try every speed from 1 to max(piles). For each speed, calculate the total hours needed by summing ceil(pile / k) for each pile. Return the first speed where total hours <= h. This is O(max(piles) * n) which is too slow for large inputs.
Key insight: the answer space is monotonic. If speed k works, then any speed > k also works. If speed k does not work, any speed < k also does not work. This is a classic binary search on answer scenario.
Binary search bounds: lo = 1 (minimum possible speed), hi = max(piles) (eat the largest pile in one hour). For each mid speed, calculate hours needed. If hours <= h, the answer is mid or lower (search left). If hours > h, we need a higher speed (search right).
Visual walkthrough for piles = [3, 6, 7, 11], h = 8:
Binary search: lo=1, hi=11
mid=6: hours = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8. Try lower.
mid=3: hours = 1+2+3+4 = 10 > 8. Need higher.
mid=4: hours = 1+2+2+3 = 8 <= 8. Try lower.
mid=3: already checked. Answer is 4.
Time complexity: O(n * log(max(piles))) where n is the number of piles. Each binary search step takes O(n) to compute total hours, and we do O(log(max(piles))) steps. Space: O(1).
Edge cases: single pile, pile size of 1, h equals n (must eat exactly 1 per pile per hour), h very large (answer is 1).
Optimal Approach
Binary search on the answer (eating speed k). Set lo = 1, hi = max(piles). While lo < hi: compute mid = (lo + hi) // 2. Calculate total hours: for each pile, add ceil(pile / mid). If total hours <= h, set hi = mid (try slower). Else set lo = mid + 1 (need faster). Return lo.
Walkthrough: piles = [3, 6, 7, 11], h = 8.
lo=1, hi=11, mid=6. Hours =1+1+2+2 = 6 <= 8.hi=6.lo=1, hi=6, mid=3. Hours =1+2+3+4 = 10 > 8.lo=4.lo=4, hi=6, mid=5. Hours =1+1+2+3 = 7 <= 8.hi=5.lo=4, hi=5, mid=4. Hours =1+2+2+3 = 8 <= 8.hi=4.lo=4, hi=4. Return 4.
Time: O(n * log(max(piles))). Space: O(1).
What Trips People Up in Real Interviews
Using (p + mid - 1) / mid for ceiling division but forgetting it for the Python math.ceil version. In C++/Java, (p + mid - 1) / mid avoids floating point. In Python, math.ceil(p / mid) works but is slower than integer math.
Setting hi to sum(piles) instead of max(piles). The maximum speed Koko could ever need is eating the largest pile in one hour. Using sum(piles) wastes binary search iterations.
Off-by-one in the binary search: returning lo - 1 or using < instead of <= when checking hours. The loop invariant is lo <= answer <= hi. When lo == hi, that is the answer.
Not using long for the hours sum in C++/Java. If you have many piles of large bananas, the sum can overflow int. Always use long for the running total.
Trying a greedy approach (sort piles, eat from largest first) instead of binary search. Greedy doesn't work here because the optimal speed depends on all piles simultaneously, not just the largest one.
Solution Code
import math
def minEatingSpeed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h:
hi = mid
else:
lo = mid + 1
return loFrequently Asked Questions
What is the Koko Eating Bananas problem?
Koko loves to eat bananas. There are n piles of bananas, the i-th pile has `piles[i]` bananas. The guards have gone and will come back in h hours. Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them and does not eat any more that hour. Find the minimum integer k such that she can eat all the bananas within h hours.
How do you solve Koko Eating Bananas?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Koko Eating Bananas?
Koko Eating Bananas is asked at Amazon, Atlassian, Netflix. It is a medium difficulty problem.
What are common mistakes on Koko Eating Bananas?
- Using `(p + mid - 1) / mid` for ceiling division but forgetting it for the Python `math.ceil` version. In C++/Java, `(p + mid - 1) / mid` avoids floating point. In Python, `math.ceil(p / mid)` works but is slower than integer math.
- Setting `hi` to `sum(piles)` instead of `max(piles)`. The maximum speed Koko could ever need is eating the largest pile in one hour. Using `sum(piles)` wastes binary search iterations.
- Off-by-one in the binary search: returning `lo - 1` or using `<` instead of `<=` when checking hours. The loop invariant is `lo <= answer <= hi`. When `lo == hi`, that is the answer.
- Not using `long` for the hours sum in C++/Java. If you have many piles of large bananas, the sum can overflow `int`. Always use `long` for the running total.
- Trying a greedy approach (sort piles, eat from largest first) instead of binary search. Greedy doesn't work here because the optimal speed depends on all piles simultaneously, not just the largest one.