875. Koko Eating Bananas
Asked at Amazon, Atlassian, Netflix, NVIDIA
Difficulty
Medium
Time
O(n * log(max(piles)))
Space
O(1)
Pattern
Array
Companies
4
Problem
Koko has n piles of bananas. The i-th pile holds piles[i] bananas. The guards are away and will return in h hours.
Koko picks an eating speed k, measured in bananas per hour. In each hour she chooses one pile and eats up to k bananas from it. If the pile has fewer than k bananas left, she finishes that pile and eats nothing more during that hour. So eating one pile takes ceil(pile / k) hours.
Return the smallest integer k that lets Koko finish every pile within h hours. She wants to eat as slowly as possible, but she must be done before the guards come back.
Key rule: if a speed k works, every larger speed also works. That monotonic property is what makes binary search possible.
Pick a speed, count the hours
Constraints
- ●
1 <= piles.length <= 10^4 - ●
piles.length <= h <= 10^9 - ●
1 <= piles[i] <= 10^9
Examples
piles = [3,6,7,11], h = 84piles = [30,11,23,4,20], h = 530piles = [30,11,23,4,20], h = 623Asked At
4 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Netflix | Medium | View all Netflix questions → |
| NVIDIA | Medium | View all NVIDIA 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).
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).
Binary search on the speed
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
O(n * log(max(piles))) timeimport 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 runs in O(n * log(max(piles))) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Koko Eating Bananas?
Koko Eating Bananas is asked at Amazon, Atlassian, Netflix, NVIDIA. 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.