Binary Search · LC #875
Koko Eating Bananas
Find the minimum eating speed `k` (bananas/hour) that lets Koko finish all piles within `h` hours, using binary search on the answer space [1, max(piles)].
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
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 bananas-per-hour eating speed of `k`. Each hour, she chooses one pile and eats `k` bananas from it. If the pile has less than `k` bananas, she eats all of them instead and will not eat any more bananas during this hour. Return the minimum integer `k` such that she can eat all the bananas within `h` hours.
Sample I/O
Input: piles=[3,6,7,11], h=8 Output: 4 Input: piles=[30,11,23,4,20], h=5 Output: 30
Time: O(n log m) · Space: O(1)
Intuition
How to Think About It
Intuition
Total hours consumed is a monotonically decreasing function of eating speed `k`. Below some threshold speed it takes too long; above it finishes in time. Binary search finds the minimum feasible `k` on this monotone domain.
Core Concept
Search space: `[1, max(piles)]`. For a candidate speed `m`, compute `hours = sum(ceil(pile/m))`. If `hours <= h`, speed is feasible - try smaller (`r = m`). If `hours > h`, speed is too slow - try larger (`l = m+1`). Use `l < r` loop; at exit `l == r` is the minimum feasible speed.
When to use
Any "find minimum X such that condition(X) is satisfied" where the condition is monotone (false below threshold, true above). Canonical "binary search on answer" template.
When NOT to use
When the feasibility check itself is not O(n) or better, the total complexity may exceed brute force; or when the answer domain is not discrete/integer.
Key Insights
What to Know Cold
- The answer is always in [1, max(piles)] - at max speed each pile takes exactly 1 hour.
- Use ceiling division `ceil(pile/k) = (pile + k - 1) / k` in integer arithmetic to avoid float.
- Loop condition is `l < r` (not `l <= r`) because we converge on the minimum feasible - `r = m` (not `mid-1`) preserves it.
- This is the prototype of the "binary search on answer" pattern used in Ship Packages (LC 1011), Minimize Max Distance (LC 1552), Split Array Largest Sum (LC 410), and more.
- Total hours must use `long` accumulation in Java/C++ if pile sizes are large.
3 examples
Worked Examples
Find minimum speed with h > n
piles=[3,6,7,11], h=8.
l=1,r=11. mid=6→hours=ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)=1+1+2+2=6≤8→r=6. mid=3→hours=1+2+3+4=10>8→l=4. mid=5→hours=1+2+2+3=8≤8→r=5. mid=4→hours=1+2+2+3=8≤8→r=4. l==r=4→return 4.
function minEatingSpeed(piles: number[], h: number): number {
let l=1, r=Math.max(...piles);
while(l<r){
const m=l+Math.floor((r-l)/2);
const hours=piles.reduce((s,p)=>s+Math.ceil(p/m),0);
if(hours<=h) r=m; else l=m+1;
}
return l;
}Output: 4
Demonstrates the binary-search-on-answer pattern with a feasibility check.
Exactly n hours allowed (h == piles.length)
piles=[30,11,23,4,20], h=5.
With only 5 hours for 5 piles, must finish each pile in 1 hour → k = max(piles) = 30.
Output: 30
Upper bound edge case: h equals number of piles forces k = max(piles).
All piles equal
piles=[4,4,4,4], h=8.
With h=2*n, k=2 suffices (each pile of 4 takes ceil(4/2)=2 hours; total=8).
Output: 2
Uniform piles simplify feasibility check; validates ceiling division.