Binary Search · 065Medium
Koko Eating Bananas
Koko eats bananas from piles at k bananas per hour: each hour she picks one pile and eats up to k from it, moving on if the pile is smaller. Return the smallest integer k that lets her finish all piles within h hours.
Constraints
- 1 <= piles.length <= 10^4
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9
Examples
minEatingSpeed([3, 6, 7, 11], 8) -> 4 minEatingSpeed([30, 11, 23, 4, 20], 5) -> 30 minEatingSpeed([30, 11, 23, 4, 20], 6) -> 23 minEatingSpeed([4], 1) -> 4 // one pile, one hour minEatingSpeed([3, 6, 7, 11], 4) -> 11 // h == pile count, so k = max(piles) minEatingSpeed([3, 6, 7, 11], 27) -> 1 // 27 hours is exactly enough at k = 1
Edge cases
- h equal to the pile count forces k to be the largest pile.
- Hours for one pile are ceil(pile / k) — she never mixes piles in an hour.
- k is at least 1 and at most max(piles).
Show the target complexity (spoiler)
- Naive
- O(max(piles) * n) time — try every speed from 1 upward. With piles up to 10^9 this
- Target
- O(n log(max piles)) time — binary search the ANSWER over k in [1, max(piles)], testing feasibility at each step.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/05-binary-search/065-koko-eating-bananas.js ./practice c 065