Koko Eating Bananas (LeetCode 875)

The problem

There are piles of bananas, and piles[i] is the size of pile i. Koko picks an eating speed k (bananas per hour). Each hour she chooses one pile and eats k bananas from it; if the pile has fewer than k, she finishes it and waits out the rest of the hour. Return the minimum integer k that lets her eat every banana within h hours. It is guaranteed that h >= len(piles).

Input:  piles = [3, 6, 7, 11], h = 8
Output: 4

At speed 4 the piles take 1, 2, 2 and 3 hours: 8 in total. At speed 3 they take 1, 2, 3 and 4: 10 hours, too slow.

How to think about it

Start with brute force. Try k = 1, 2, 3, … and return the first speed whose total time is at most h. Computing the time for one speed is O(n). Trying up to max(piles) speeds (up to 10⁹) makes this O(n · max), far too slow.

Look at how the answer to “is speed k fast enough?” behaves. If speed k works, any faster speed also works, because each pile takes the same or fewer hours. So across all speeds the answers look like no, no, no, yes, yes, yes. That is a monotonic yes/no sequence, and you want the first yes.

The key insight: binary-search the answer itself, not an array. The answer lies in [1, max(piles)]: speed max(piles) finishes every pile in one hour, which takes len(piles) <= h hours. For a candidate mid, compute the hours needed, sum(ceil(p / mid)). If it fits in h, mid works and the answer is mid or smaller (hi = mid); otherwise go faster (lo = mid + 1). That gives about 30 checks instead of a billion.

Which pattern is this? Search on the answer. The tell is a phrase like “minimum speed / capacity / size such that something is possible”, where checking one candidate is easy and feasibility is monotonic. It’s the same first-true template as First Bad Version, with the feasibility check playing the role of isBad.

Approach

1. Set lo = 1 and hi = max(piles).
2. While lo < hi:
   • mid = (lo + hi) // 2.
   • Hours at speed mid = sum(ceil(p / mid) for p in piles).
   • If hours <= h, set hi = mid; else set lo = mid + 1.
3. Return lo.

Solution

import math

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)                 # max(piles) always works
    while lo < hi:
        mid = (lo + hi) // 2
        if sum(math.ceil(p / mid) for p in piles) <= h: hi = mid   # fast enough: try slower
        else: lo = mid + 1                                         # too slow
    return lo
# min_eating_speed([3,6,7,11], 8) -> 4

Dry run

On piles = [3, 6, 7, 11], h = 8:

Now lo == hi == 4, so the answer is 4.

Complexity

• Time: O(n log M), where M = max(piles). The binary search takes O(log M) steps and each feasibility check sums over all n piles.
• Space: O(1). The generator inside sum doesn’t build a list.

Edge cases and pitfalls

• h == len(piles): she must finish one pile per hour, so the answer is max(piles).
• Huge h: the answer can be 1. Start lo at 1, never 0, or you’ll divide by zero.
• Ceiling division: p // mid undercounts. Use math.ceil(p / mid) or the integer-only (p + mid - 1) // mid, which avoids float rounding for very large values.
• Searching up to sum(piles) still works but wastes steps. max(piles) is a tight upper bound.

Related problems

• Capacity To Ship Packages Within D Days (LeetCode 1011): search on the answer with a greedy day-packing check.
• Split Array Largest Sum (LeetCode 410): the same idea for “minimise the largest piece”.
• First Bad Version (LeetCode 278): the first-true template in its simplest form.