visual walkthrough
Koko Eating Bananas
MediumBinary Search on Answer
The textbook search-on-answer problem.
The idea
Eating faster never takes more hours, so the speeds split into "too slow" then "fast enough".
Binary search that range for the first speed that's fast enough. Each check just adds up ⌈pile / speed⌉.
Complexity
| approach | time | space |
|---|---|---|
| Try every speed | O(max · n) | O(1) |
| Binary search on the speed | O(n log max) | O(1) |