Find the minimum eating speed for Koko to finish all bananas within h hours.
Binary search on the answer space (eating speed 1 through max pile size) rather than on the input array. For each candidate speed, greedily compute hours needed in O(n). The feasibility check is monotone — if speed k works, any speed above k also works — so binary search finds the minimum valid speed in O(n log m) time.
How to think about it
Recognise the pattern
This is binary search on the answer — one of the most powerful and under-used patterns. Instead of searching the input for a value, you search the range of possible answers for the smallest one that satisfies a condition.
The signal that triggers this pattern:
- You are asked for a minimum (or maximum) value that makes something feasible.
- Given a candidate answer, you can check feasibility greedily in O(n).
- The feasibility function is monotone: if
kworks, so does every value abovek(for minimisation).
Build the approach step by step
Problem setup: Koko has piles of bananas. She eats at most k bananas per hour from one pile. She has h hours. Find the minimum integer k such that she finishes.
Brute force: try every speed from 1 upward until feasible. O(max(piles) · n) — potentially huge.
Binary search on the answer:
- Search space:
[1, max(piles)]. At speed = max(piles), she finishes every pile in 1 hour. - Feasibility check:
sum(ceil(pile / k) for pile in piles) <= h. This is O(n). - The feasibility function is monotone — higher speed → fewer or equal hours → still feasible.
- Apply the lower-bound binary search template to find the smallest feasible
k.
piles=[3,6,7,11], h=8
speed space: [1..11]
mid=6: hours = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8 -> feasible, try lower
mid=3: hours = 1+2+3+4 = 10 > 8 -> too slow, go higher
mid=4: hours = 1+2+2+3 = 8 <= 8 -> feasible, try lower
mid=3: already tested -> converges to 4Complexity
| Value | Why | |
|---|---|---|
| Time | O(n log m) | log m iterations (m = max pile), O(n) feasibility check each |
| Space | O(1) | Only scalars |
Here m = max(piles), so log m is at most ~30 for pile sizes up to 10⁹.