LeetCode 875 · Binary Search · concept: modified-binary-search
Problem
Koko eats bananas from piles at speed k per hour (one pile at a time; a partial pile still uses a full hour). Given h hours, return the minimum integer speed k that finishes all piles in time.
piles = [3,6,7,11], h = 8 -> 4
The insight — binary search on the answer
k isn’t found in the array — it’s a value in the range [1, max(piles)]. The key property is monotonicity: if speed k works, every speed > k also works; if k is too slow, everything slower is too. That yes/no boundary is binary-searchable. Search for the smallest k whose total hours ≤ h.
import math
def minEatingSpeed(piles, h):
def hours_at(k):
return sum(math.ceil(p / k) for p in piles) # ceil: partial pile = full hour
l, r = 1, max(piles)
while l < r:
k = l + (r - l) // 2
if hours_at(k) <= h:
r = k # k works -> maybe a slower speed also works; keep k
else:
l = k + 1 # too slow -> need faster
return l # smallest feasible speedTime O(n · log(max pile)), space O(1). Each feasibility check is O(n); the search does O(log(max)) checks.
”Binary search on the answer” — the pattern
When you can’t binary-search the input but can (1) define a candidate answer range and (2) write an O(n) feasibility test that’s monotonic in the candidate, binary-search the answer space. The array isn’t sorted — the answers are (feasible above a threshold, infeasible below). This is one of the highest-leverage patterns in the set; it also solves Capacity to Ship Packages, Split Array Largest Sum, and Swim in Rising Water.
Key insight
“Minimize/maximize a value subject to a monotonic feasibility check” → binary search the answer. The two ingredients are a bounded range and a monotone predicate; the search then finds the boundary between “works” and “doesn’t.”
Related
- concept: modified-binary-search
- prev: Search a 2D Matrix · next: Find Minimum in Rotated Sorted Array
Software engineering
Infrastructure & security
Computer science
Hardware & engineering