Koko Eating Bananas

PracticeNeetCode ↗LeetCode ↗

Koko has n piles of bananas and h hours before the guards return. Each hour she picks one pile and eats up to k bananas from it — if a pile has fewer than k, she finishes that pile and stops early for the hour. Find the minimum integer eating speed k such that she finishes every pile within h hours.

Example

Key Pointers

• "Find the minimum value that satisfies a condition" is a classic binary search on the answer, not on the input array itself.
• The feasible speeds are monotonic: if speed k works, any faster speed also works — that monotonicity is what makes binary search valid.
• Hours needed for a given speed is the sum of ceil(pile / speed) across all piles.

Step-by-Step Analysis

1. Set left = 1, right = max(piles) — the smallest and largest speeds worth ever trying.
2. While left is below right: compute a candidate speed mid, then total hours needed at that speed.
3. If those hours fit within h, mid is fast enough — try a slower speed by pulling right down to mid.
4. Otherwise mid is too slow — push left up past it.
5. When left meets right, that value is the minimum working speed.

Complexity

Time: O(n · log(max(piles))) — Space: O(1)

Code

import math

def minEatingSpeed(piles: list[int], h: int) -> int:
    left, right = 1, max(piles)

    while left < right:
        mid = left + (right - left) // 2
        hours = sum(math.ceil(pile / mid) for pile in piles)
        if hours <= h:
            right = mid
        else:
            left = mid + 1

    return left

Code Explanation

How the solution above works, piece by piece.

1. The answer lies between 1 and max(piles) (at that speed every pile takes exactly one hour).
2. For a candidate speed mid, ceil(pile / mid) is the hours for one pile; sum them for the total.
3. If the total fits in h, mid works but a slower speed might too: right = mid (keep mid).
4. Otherwise it's too slow: left = mid + 1.
5. When left == right that's the slowest speed that works. O(n log max) time: each of the log(max) probes sums n piles.

Visual Walkthrough

Running it on piles = [3, 6, 7, 11], h = 8:

Video Explanation

NeetCode — Binary Search, LeetCode 875