LeetCode 875 ·
Medium
Koko Eating Bananas
Find the smallest eating speed that finishes all banana piles within h hours.
Try it
Step through the core mechanic. The simulator below runs the binary search shape this problem is built on.
Interactive · Binary search on the answer (LC 875) find smallest eating speed k that finishes piles in ≤ h hours
answer space — k ∈ [1, max(piles)]
init: lo=1, hi=max(piles)=11
predicate
can(k) = (Σ⌈piles[i] / k⌉ ≤ h) Why this works.
The predicate can(k) is monotone: a higher eating speed never
hurts feasibility, so once can(k) is true, every larger k is
also true. The answer space looks like
[false, false, ..., false, true, true, ..., true] — and
binary search on a sorted boolean array is what we just learned.The approach
Speed feasibility is monotone: if speed k works, so does k+1. Binary search k over [1, maxPile]; for each, sum ceil(pile/k) hours and keep the smallest feasible speed.
| Aspect | Value |
|---|---|
| Pattern | Binary search |
| Recognise it by | Minimise a rate subject to a monotone feasibility test — binary search on the answer. |
| Time complexity | O(n log maxPile) |
| Space complexity | O(1) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.