MediumNeetCode150ArrayBinary Search
Koko Eating Bananas
Find minimum integer k such that Koko can eat all bananas within h hours.
Examples
Input
piles = [3,6,7,11], h = 8
Output
4
k=4: eat 3 in 1h, 6 in 2h, 7 in 2h, 11 in 3h = 8h.
Constraints
- •
1 <= piles.length <= 10^4 - •
1 <= piles[i] <= 10^9 - •
piles.length <= h
Approaches
Try k from 1 to max(piles).
CodeT: O(max(piles) * n) | S: O(1)
Binary search on k.
CodeT: O(n * log(max(piles))) | S: O(1)
def minEatingSpeed(piles, h):
import math
l,r=1,max(piles)
while l<r:
m=(l+r)//2
hours=sum(math.ceil(p/m) for p in piles)
if hours<=h: r=m
else: l=m+1
return lSame approach.
Diagram
Binary search: if hours <= h, try smaller k
CodeT: O(n * log(max(piles))) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Linear Search | O(max(piles) * n) | O(1) | Try k from 1 to max(piles). |
| Binary Search | O(n * log(max(piles))) | O(1) | Binary search on k. |
| Binary Search - Optimized | O(n * log(max(piles))) | O(1) | Same approach. |
Linear Search
T: O(max(piles) * n)S: O(1)
Try k from 1 to max(piles).
Binary Search
T: O(n * log(max(piles)))S: O(1)
Binary search on k.
Binary Search - Optimized
T: O(n * log(max(piles)))S: O(1)
Same approach.
Common Mistakes
Not using binary search
Wrong feasibility check
Off-by-one in search bounds