#875
Koko Eating Bananas
Medium Binary search on the answer
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Koko eats from one pile per hour at speed k bananas/hour (a smaller pile still takes the full hour). Find the minimum k that lets her finish all piles within h hours.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the slowest eating speed that still finishes all piles in h hours.
Why this works: faster always works if slower works, so binary search the speed and count hours = sum of ceil(pile / speed).
Example: piles [3, 6, 7, 11], h = 8
speed 4: 1+2+2+3 = 8 ✓speed 3: 1+2+3+4 = 10 ✗answer 4
✦Hints open one at a time
If speed k works, any faster speed works too. That's monotonic — binary search on k.
Hours needed at speed k = sum of ceil(pile / k).
k ranges from 1 to the largest pile.
↗Approach
Binary search k in [1, max]. If hours(k) <= h, try smaller (hi = k); otherwise lo = k + 1. ceil(p / k) = (p + k − 1) / k.
</>Solution (Java)
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int lo = 1, hi = 0;
for (int p : piles) hi = Math.max(hi, p);
while (lo < hi) {
int k = (lo + hi) >>> 1;
if (hours(piles, k) <= h) hi = k; // fast enough, try slower
else lo = k + 1;
}
return lo;
}
private long hours(int[] piles, int k) {
long total = 0;
for (int p : piles) total += (p + k - 1) / k; // ceil(p / k)
return total;
}
}!Common mistake
Summing hours in int — with many piles and k = 1 it can overflow. Use long.
Complexity
- Time: O(n log M), M = largest pile.
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon