NeetCode #276LC-875MediumBinary SearchNC 150NC 250
← Back to All Problems#276 · #875 · Koko Eating Bananas(爱吃香蕉的珂珂)
📌 Problem Statement & Constraints
Koko has
piles of bananas and h hours. Each hour she chooses a pile and eats k bananas from it; if the pile has fewer than k left, she finishes it and stops for that hour. Return the minimum integer k such that she can eat all the bananas within h hours. Constraints: 1 <= piles.length <= 10^4, piles.length <= h <= 10^9, 1 <= piles[i] <= 10^9.💡 Core Algorithmic Approaches
- This is a binary search on the answer: the predicate "can finish within
hhours with speedk" is monotone ink. - For a given
k, the hours needed aresum(ceil(p / k)). - The feasible range is
[1, max(piles)]; binary search for the smallest feasiblek. - Use
r = mid(notmid - 1) when the predicate holds, becausemiditself may be the answer.
💻 Benchmark Python3 Implementation
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
# hours needed at speed mid; ceil division via integer arithmetic
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid # mid works -> try smaller
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log(max(piles))): each predicate evaluation is O(n) and the search does O(log V) of them.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Using
hi = mid - 1when feasible: that could skip the optimal value. Usehi = mid. - Computing hours with
p // mid: integer division truncates; the ceiling(p + mid - 1) // midis required. - Using floating-point ceiling:
math.ceil(p / mid)loses precision for large values; the integer form is exact. - Setting
hi = max(piles)wrongly: the maximum useful speed ismax(piles), since eating faster than the largest pile wastes the hour's capacity. - Forgetting that
h >= piles.length: this guaranteesk = max(piles)is always feasible, so the search never fails.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.