Koko Eating Bananas

You'll use binary search on the answer: search over possible speeds instead of positions in a list. You need the binary search from Search Insert Position and integer division. Related chapter: binary search.

1. The problem

Koko eats bananas from piles at a whole-number speed. Each hour, she eats up to that many bananas from one pile. If the pile runs out early, she waits out the rest of the hour. Find the smallest speed that finishes every pile within h hours. Every pile has at least one banana, and h is at least the number of piles. This is LeetCode 875.

"Waits out the rest of the hour" is the phrase that matters. A pile of 6 at speed 4 takes 2 hours, not 1.5.

2. A correct baseline

def baseline(piles, h):
    for speed in range(1, max(piles) + 1):
        if sum((p + speed - 1) // speed for p in piles) <= h:
            return speed

assert baseline([3,6,7,11],8) == 4
assert baseline([4,4],2) == 4
assert baseline([1],9) == 1

This tries every speed from 1 up to the biggest pile, M. Each try sums over all n piles, so it takes O(nM) time. With 10,000 piles of up to a billion bananas, that's far too slow to finish. It uses O(1) extra space.

The bottleneck. It tests speeds one at a time. But if one speed works, every faster speed works too, so most of those tests tell us nothing new.

3. The observation

First, the hours for one pile. A pile of 7 at speed 3 takes 3 hours: 3, 3, then 1. That's 7 / 3 rounded up. In Python, (pile + speed - 1) // speed rounds up without floats.

Now ask "does speed s finish in time?" for every speed. For [3,6,7,11] with h=8, speeds 1 to 3 say no and speeds 4 and up say yes. A faster speed never takes more hours, so the answers are always some Noes followed by some Yeses. That's the same shape as Search Insert Position, so binary search finds the first Yes.

Where to search? Speed 1 is the lowest possible. Speed M, the biggest pile, always works: each pile takes one hour, and h is at least the number of piles.

4. The solution and a trace

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        """Positive piles, h >= len(piles); return minimum feasible speed."""
        left, right = 1, max(piles)
        while left < right:
            speed = (left + right) // 2
            hours = sum((p + speed - 1) // speed for p in piles)
            if hours <= h:
                right = speed  # This speed works; keep it as a candidate.
            else:
                left = speed + 1
        return left

solve=Solution().minEatingSpeed
assert solve([3,6,7,11],8) == 4
assert solve([4,4],2) == 4
assert solve([1],9) == 1

Trace [3,6,7,11] with h=8:

5. Why it works

What stays true. The smallest speed that works is always between left and right.

Why each update keeps it there. If a speed is too slow, every slower speed is too, so left = speed + 1 skips only speeds that fail. If a speed works, the answer is that speed or slower, so right = speed keeps it.

The loop ends with the answer. Each step shrinks the range, so left and right meet. They meet at the smallest speed that works.

6. Cost, edge cases, and failure

Cost. Binary search tries about log M speeds, and each try sums over n piles. That's O(n log M) time. For piles up to a billion, it's about 30 tries instead of a billion. O(1) extra space.

Edge cases. Round up for each pile separately. Empty piles and h smaller than the number of piles can't happen: no speed finishes a pile in less than one hour.

Where it fails. Adding the piles together before rounding up gives the wrong count:

assert baseline([1,1],1) is None  # Infeasible, deliberately outside the contract.
assert (sum([1,1])+2-1)//2 == 1  # Wrong model suggests one hour suffices.

import random
rng=random.Random(875)
for _ in range(300):
    piles=[rng.randint(1,20) for _ in range(rng.randint(1,8))]
    h=rng.randint(len(piles),40)
    assert solve(piles,h)==baseline(piles,h)