Problem · LC 875

Koko Eating Bananas

Medium
◧ Template C · search on the answer

How to recognize it

No sorted array in sight — instead: "find the minimum speed / smallest capacity / least X such that a condition is satisfiable." When the answer itself lives in a numeric range and feasibility is monotonic, you binary search the ANSWER, not the input. This is THE pattern interviewers love because it looks nothing like binary search at first.

The core idea

Define feasible(k) = "can Koko finish all piles in ≤ h hours eating k bananas/hour?". Bigger k is always ≥ as feasible, so feasibility flips false→true exactly once as k grows. Binary search the smallest k where feasible(k) is true, over the range [1, max(pile)].

Why It's Tricky

This is the mental leap: there's no array to search. Instead, you search a RANGE OF ANSWERS (speeds 1 to max(pile)). You're not looking up a value — you're testing whether a candidate answer is feasible. This feels totally different from Template A, but it's Template B's logic applied to a different domain.

The Key Insight

The key is MONOTONICITY: if Koko can finish at speed 5, she can finish at speed 6 (faster is always better). This monotonicity means binary search works: slow speeds fail, then at some speed k*, she succeeds, and all faster speeds also work. Find k*.

Step-by-Step Walkthrough

Example: piles=[1,1,1,1,1,1,1,1,1,9], h=10

Speed 1: 1+1+1+1+1+1+1+1+1+9 = 19 hours > 10 ✗
Speed 9: 1+1+1+1+1+1+1+1+1+1 = 10 hours = 10 ✓ (ceil(9/9)=1 hour for the pile of 9)

Binary search [1, 9]:
mid=5 → 1+1+1+1+1+1+1+1+1+2 = 11 > 10 ✗ (ceil(9/5)=2)
mid=7 → 1+1+1+1+1+1+1+1+1+2 = 11 > 10 ✗
mid=8 → 1+1+1+1+1+1+1+1+1+2 = 11 > 10 ✗
mid=9 → 1+1+1+1+1+1+1+1+1+1 = 10 ✓

Answer: 9 is the minimum speed.

time O(n · log(max pile))
space O(1)
koko_eating_bananas
import math

def minEatingSpeed(piles, h):
    def feasible(k):                       # monotonic in k
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:                         # leftmost-true (Template B)
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                       # maybe smaller works
        else:
            lo = mid + 1                   # need to eat faster
    return lo

Interview gotchas

  • Prove monotonicity out loud — that is what justifies binary search. "Faster eating never hurts" is the whole argument.
  • Hours for a pile is ceil(pile / k), not pile / k. A pile is finished in a whole number of hours.
  • Use the leftmost-true template (lo < hi, hi = mid) so you converge on the first feasible k.
  • Bounds: lo = 1 (can't eat 0), hi = max(piles) (eating faster than the biggest pile is pointless).

💡 What to Say in the Interview

  • Say: "There's no array to search, so I'll search the answer range [1, max(pile)]."
  • State the feasibility function: "Can Koko finish all piles in ≤ h hours at speed k?"
  • Prove monotonicity: "If she finishes at speed k, she finishes at any speed > k — faster eating helps."
  • Explain the formula: "Hours for a pile of P at speed K is ceil(P/K), not P/K, because she eats in whole hours."
  • Use Template B: "Since feasibility is monotonic, I'll binary search to find the leftmost (minimum) feasible speed."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.