Koko Eating Bananas
Koko chooses one positive integer eating speed k in bananas per hour. During an hour she works on one pile; if that pile runs out early, the rest of the hour is lost. Find the smallest speed that finishes every pile within h hours. The constraints allow up to 10,000 piles, pile sizes up to one billion, and as many as one billion hours.
Count each pile’s whole hours
Fix a speed and count the hours it needs. A pile of 7 at speed 3 takes 3 hours: two full hours eat 3 each, then a third hour finishes the last banana. It costs ceil(7 / 3), not 2, because Koko cannot start another pile during the leftover part of that third hour.
So a pile of size p costs ceil(p / k) hours, and the piles do not share partial hours. At speed 4 on [3, 6, 7, 11], the costs are 1 + 2 + 2 + 3 = 8. Speed 3 costs 1 + 2 + 3 + 4 = 10, which misses the deadline h = 8.
One way to solve the problem is to test speed 1, then 2, then 3, stopping at the first speed that fits. That is correct, but the largest pile can contain one billion bananas. Each test may inspect all n piles. With M as the largest pile size, this baseline takes O(nM) time and O(1) extra space, which is too slow for the full limits.
Find the first working speed
If speed 4 works, speed 5 also works; making each hour faster cannot add hours. If speed 3 fails, every smaller speed fails too. Candidate speeds form a row of failures followed by successes. We need the first success.
The answer lies between 1 and the largest pile. Speed 1 is the slowest legal choice. At the largest pile's size, every pile takes one hour, so that speed works because the constraints guarantee h >= piles.length.
Shrink the answer interval
Keep the smallest working speed inside the inclusive interval [left, right]. Every speed below left is known to fail, and right is known to work. At the start, left = 1 and right = M satisfy both claims.
Test the midpoint, rounding down. If it works, set right = middle: the answer is no greater than this working speed, and we still need to check slower speeds. If it fails, every speed through middle fails too, so set left = middle + 1. Each update keeps the answer in the interval.
For [3, 6, 7, 11] and h = 8, the search tests speeds 6, 3, 5 and 4. Their hour totals are 6, 10, 8 and 8, narrowing [1, 11] to [4, 4].
While left < right, the rounded-down midpoint is below right. A working test decreases right; a failing test increases left. The interval shrinks each time, so the bounds eventually meet. The shared speed works because right still works, and every smaller speed fails because it is below left. This is binary search over candidate speeds.
Round up with integer division
To compute a pile's hours using integer division, divide its size by the speed. An exact division needs that many hours; a nonzero remainder needs one more. Use 1 + (pile - 1) // speed for positive piles: subtracting one lowers the integer quotient only for exact multiples, then adding one gives the ceiling. Pile 6 at speed 3 gives 1 + 5 // 3 = 2, and pile 7 gives 1 + 6 // 3 = 3.
The feasibility check returns false as soon as its running hour total exceeds h. Every remaining pile adds positive hours, so finishing the scan cannot make that speed work.
Implementation
from typing import List
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def can_finish(speed: int) -> bool:
hours_needed = 0
for pile in piles:
hours_needed += 1 + (pile - 1) // speed
if hours_needed > h:
return False
return True
left = 1
right = max(piles)
while left < right:
middle = left + (right - left) // 2
if can_finish(middle):
right = middle
else:
left = middle + 1
return leftComplexity
One feasibility check scans n piles. Binary search uses checks, where M is the largest pile; finding M takes another scan. Total time is and extra space is , including the M = 1 case.