Koko Eating Bananas
A monkey named Koko enjoys eating bananas. She is presented with n piles of bananas, where the i-th pile contains piles[i] bananas. Koko can eat at a constant speed of k bananas per hour. In each hour, she can pick one pile and eat up to k bananas from it. If the pile has fewer than k bananas, she eats the entire pile and waits for the next hour to pick another.
She wants to finish eating all the bananas within h hours before the guards arrive.
Your task is to determine the minimum integer value of k that allows her to finish all the bananas within the given time.
Example 1
Input: piles = [30, 11, 23, 4, 20], h = 6 Output: 23
To determine how long it would take Koko to eat all the bananas at this speed, we calculate the time for each pile as the ceiling of pile_size / k since she can’t eat a partial pile in less than an hour.
For pile 30, it would take ⌈30 / 23⌉ = 2 hours.
For pile 11, it's ⌈11 / 23⌉ = 1 hour.
For pile 23, it's ⌈23 / 23⌉ = 1 hour.
For pile 4, it's ⌈4 / 23⌉ = 1 hour.
For pile 20, it's ⌈20 / 23⌉ = 1 hour.
Summing these up: 2 + 1 + 1 + 1 + 1 = 6 hours in total.
Example 2
Input: piles = [3, 6, 7, 11], h = 4 Output: 11
She has exactly 4 hours for 4 piles. So each pile must be finished in one hour, meaning speed must be at least the size of the largest pile → max(piles) = 11.
We can use binary search in this problem because the solution space — the possible eating speeds (k) — is monotonic. That means if Koko can finish eating at speed k, she can also finish at any higher speed. Instead of linearly testing all values from 1 to max(piles), binary search helps us efficiently narrow down to the smallest valid speed in O(log(max(piles)) * n) time, making it highly scalable even for large inputs.
Algorithm
-
Search Range: Minimum speed
low = 1(slowest possible). Maximum speedhigh = max(piles)(fastest needed — she finishes each pile in 1 hour). -
Midpoint and Feasibility: For each
mid = (low + high) / 2, compute the total hours it would take Koko to finish all piles at that speed. For a pile of size p, at speed k, it takesceil(p / k)hours, which can be computed as(p + k - 1) / k. -
Narrow the Search: If total hours at speed mid is within or less than h, try a smaller speed (search left). Else, try a higher speed (search right).
-
Goal: Find the smallest
ksuch that Koko finishes all bananas withinhhours.
from typing import List
import math
def min_eating_speed(piles: List[int], h: int) -> int:
left = 1
right = max(piles)
while left < right:
middle = (left + right) // 2
hour_spent = 0
for pile in piles:
hour_spent += math.ceil(pile / middle)
if hour_spent <= h:
right = middle
else:
left = middle + 1
return rightTime Complexity: O(n * log m). Where n is the number of piles and m is the maximum number of bananas in a pile. We perform binary search over m (from 1 to max pile), and in each iteration, we scan all n piles.
Space Complexity: O(1). Constant space is used as no extra data structures are created apart from a few variables.