Find the minimum eating speed for Koko to finish all bananas within h hours.
Binary search on the answer space (eating speed 1 through max pile size) rather than on the input array. For each candidate speed, greedily compute hours needed in O(n). The feasibility check is monotone — if speed k works, any speed above k also works — so binary search finds the minimum valid speed in O(n log m) time.
How to think about it
This question looks like a banana word problem, but the interviewer is watching for one specific leap: binary searching the answer space rather than the input. The array of pile sizes is not sorted and you are not looking for a value inside it — you are looking for the smallest eating speed that works. The tell is the phrasing “minimum value such that something is feasible,” and the unlock is that feasibility here is monotone.
Make the monotonicity explicit, because it is what licenses the search. If Koko can clear every pile in h hours at speed k, she can certainly do it at any speed above k — faster never hurts. So the speeds split cleanly into “too slow” then “fast enough,” and you binary search the boundary over the range [1, max(piles)]. The feasibility check is a greedy O(n) sum: at speed k, a pile of size p takes ceil(p / k) hours, so she finishes when sum(ceil(p / k)) <= h. Standard lower-bound template — pull hi down when mid is feasible, push lo up when it is not — and lo lands on the minimum.
A worked example
import math
def min_eating_speed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # mid works; try smaller
else:
lo = mid + 1 # mid too slow; need faster
return lo
print(min_eating_speed([3, 6, 7, 11], 8)) # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5)) # h == n piles -> need max speed
print(min_eating_speed([1, 1, 1, 1], 4)) # plenty of time -> speed 1
# Trace the shrinking [lo, hi] window
def min_eating_speed_verbose(piles, h):
def hours(k):
return sum(math.ceil(p / k) for p in piles)
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
need = hours(mid)
ok = need <= h
verdict = "feasible, hi=mid" if ok else "too slow, lo=mid+1"
print(f" lo={lo}, hi={hi}, mid={mid}: hours={need} {'<=' if ok else '>'} {h} -> {verdict}")
if ok:
hi = mid
else:
lo = mid + 1
print(f" converged: {lo}")
return lo
print("Trace for piles=[3,6,7,11], h=8:")
min_eating_speed_verbose([3, 6, 7, 11], 8)4
30
1
Trace for piles=[3,6,7,11], h=8:
lo=1, hi=11, mid=6: hours=6 <= 8 -> feasible, hi=mid
lo=1, hi=6, mid=3: hours=10 > 8 -> too slow, lo=mid+1
lo=4, hi=6, mid=5: hours=8 <= 8 -> feasible, hi=mid
lo=4, hi=5, mid=4: hours=8 <= 8 -> feasible, hi=mid
converged: 4The trace is the algorithm thinking out loud. Speed 6 is feasible but probably wasteful, so hi drops to 6. Speed 3 needs 10 hours — too slow — so lo jumps past it to 4. Speeds 5 and 4 both just fit at exactly 8 hours, so the window keeps shrinking from the top until lo and hi meet at 4. Notice the answer sits right at the 8 <= 8 boundary: that is the smallest speed where feasibility flips on, which is precisely what we were searching for.