⚡Flashcard Drill➔
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

  1. This is a binary search on the answer: the predicate "can finish within h hours with speed k" is monotone in k.
  2. For a given k, the hours needed are sum(ceil(p / k)).
  3. The feasible range is [1, max(piles)]; binary search for the smallest feasible k.
  4. Use r = mid (not mid - 1) when the predicate holds, because mid itself 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 - 1 when feasible: that could skip the optimal value. Use hi = mid.
  • Computing hours with p // mid: integer division truncates; the ceiling (p + mid - 1) // mid is 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 is max(piles), since eating faster than the largest pile wastes the hour's capacity.
  • Forgetting that h >= piles.length: this guarantees k = 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems