Koko has n piles of bananas, where piles[i] is the number of bananas in the ith pile. She has h hours to eat all the bananas. Each hour, she picks one pile and eats up to k bananas from it. If the pile has fewer than k bananas, she finishes it and waits until the next hour. Return the minimum integer k (eating speed) such that she can eat all bananas within h hours. It is guaranteed that h >= n.
Example
piles = [3, 6, 7, 11], h = 8
Output: 4
At speed 4, Koko takes 1 hour for pile 3, 2 hours for pile 6, 2 hours for pile 7, and 3 hours for pile 11 – totaling 8 hours, which exactly fits. Speed 3 would require 10 hours, which exceeds the limit.
Binary search on the answer — the eating speed k. The range is 1 to the size of the largest pile. For each candidate speed, calculate the total hours needed (ceiling of each pile divided by k). If total hours is within h, try a slower speed; otherwise go faster.
Why this works
Instead of searching through data, you are searching through possible answers (eating speeds 1 to max pile size). For each candidate speed, you can calculate exactly how many hours it takes. Since “can finish in time” flips from false to true at some speed, binary search finds that threshold efficiently.
Step by step
- Define the search space — the minimum speed is 1, the maximum is the largest pile (eating it in one hour).
- Pick a candidate speed (mid) — calculate total hours by summing
ceil(pile / mid)for each pile. - Check feasibility — if total hours <= h, this speed works, but maybe a slower speed also works, so try left half.
- Otherwise go faster — if total hours > h, this speed is too slow, search the right half.
- Converge — when left == right, you have the minimum speed that finishes in time.
Time: O(n·log m)
Space: O(1)
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
for (int pile : piles) {
right = Math.max(right, pile); // upper bound: eat the biggest pile in one hour
}
while (left < right) {
int mid = left + (right - left) / 2;
long hours = 0;
for (int pile : piles) {
hours += (pile + mid - 1) / mid; // ceiling division = hours for this speed
}
if (hours <= h) { // fast enough — try going slower
right = mid;
} else { // too slow — need to eat faster
left = mid + 1;
}
}
return left;
}
}
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1, right = *max_element(piles.begin(), piles.end()); // search space bounds
while (left < right) {
int mid = left + (right - left) / 2;
long long hours = 0;
for (int pile : piles) {
hours += (pile + mid - 1) / mid; // ceiling division = hours for this speed
}
if (hours <= h) { // fast enough — try going slower
right = mid;
} else { // too slow — need to eat faster
left = mid + 1;
}
}
return left;
}
};
def minEatingSpeed(piles: list[int], h: int) -> int:
left, right = 1, max(piles) # search space: slowest to fastest possible speed
while left < right:
mid = (left + right) // 2
hours = sum((pile + mid - 1) // mid for pile in piles) # ceiling division = hours for this speed
if hours <= h: # fast enough — try going slower
right = mid
else: # too slow — need to eat faster
left = mid + 1
return left