Canonical Deep-Dive: Koko Eating Bananas

Problem: Koko Eating Bananas (https://leetcode.com/problems/koko-eating-bananas/) The lesson: binary search does not need a sorted array. It needs a monotonic yes-or-no question, and here you build one out of thin air.

This is a guided walk-through, not an answer key. It explains how to think about searching an answer space instead of an array: the search space, the feasible predicate, why that predicate is monotonic, and the exact complexity. It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: Koko has piles of bananas, where piles[i] is the number of bananas in the i-th pile. The guards come back in h hours. Each hour Koko picks one pile and eats up to k bananas from it; if the pile has fewer than k left, she eats it all and that hour is over (she does not move on to another pile within the same hour). Find the smallest integer eating speed k such that she finishes every pile within h hours. You are guaranteed h >= len(piles), so a finishing speed always exists.

Why the obvious idea is too slow (and what it hides)

The first instinct is to try speeds one at a time: start at k = 1, compute how many hours that takes, and increase k until it fits in h. That works, and it is worth holding in your head as the baseline, because the structure of that loop is the whole insight in disguise.

Time: O(max(piles) * n). For each candidate speed up to max(piles) you scan all n piles to total the hours. With piles up to a billion, that is far too slow.
Space: O(1).

But look at what that loop is really doing. It scans candidate speeds 1, 2, 3, ... in increasing order and stops at the first one that fits. It is a linear search for a threshold in a sorted list of candidate speeds. Anything that is a linear search for a threshold in a sorted space is a binary search waiting to happen. The speeds are already ordered (they are just the integers from 1 to max(piles)); we do not need to sort anything. We only need to confirm that “does speed k fit?” behaves monotonically, and then we can binary search for the boundary instead of walking to it.

The brute-force baseline you actually keep: the hours function

Before optimizing the search, nail down the one piece of arithmetic both versions need: given a speed k, how many hours does Koko take?

For a single pile of size p eaten at speed k, she needs ceil(p / k) hours: full hours of k bananas each, plus one more partial hour for the remainder. A pile of 7 at speed 3 takes ceil(7/3) = 3 hours (3 + 3 + 1). The total hours for a speed is the sum over all piles:

hours(k) = sum( ceil(piles[i] / k)  for each pile i )

Compute this with math.ceil(p / k), or with the integer-only form (p + k - 1) // k if you want to avoid floats entirely (know both; the integer form sidesteps any floating-point rounding worry). This function is O(n), one pass over the piles, and it is the per-candidate cost in both the brute force and the binary search.

The four-step framework: binary search on the answer

This is the recipe for the whole week. Walk it in order, every time the input is not a plain sorted array.

1. Identify the answer space. What single number are you choosing, and what are its bounds?

The answer is the eating speed k. The slowest sensible speed is 1 (she must eat at least one banana an hour to ever finish). The fastest speed worth considering is max(piles): eating faster than the largest pile cannot help, because each hour is capped at one pile anyway, so a speed of max(piles) already finishes every pile in exactly one hour each. So lo = 1 and hi = max(piles).

Say those bounds out loud and justify the upper one. A speed above max(piles) would finish in len(piles) hours just like max(piles) does; it buys nothing, so there is no reason to search past it.

2. Write feasible(k). A yes-or-no test on a candidate answer.

feasible(k) is True if Koko finishes within the deadline at speed k, that is, if hours(k) <= h, and False otherwise.

That is the entire predicate: total the hours at speed k using the function above, and compare to h. Nothing about this step searches; it just answers one question about one candidate.

3. Confirm monotonicity, and say why. This is the step people skip, and skipping it is the usual way these solutions come out wrong. The method is only valid if feasible flips exactly once as k increases.

As k grows, hours(k) never increases: eating faster takes the same number of hours or fewer for every pile, since ceil(p / k) is non-increasing in k. So once some speed k0 is fast enough (hours(k0) <= h), every speed faster than k0 is also fast enough. The predicate is False, False, ..., False, True, True, ..., True with a single flip. That single flip is exactly what binary search locates.

Do not take this on faith because the examples pass. Argue it: faster speed, fewer (or equal) hours, therefore “feasible” can only turn on once and never turn back off.

4. Binary search the boundary. You want the smallest k for which feasible(k) is True, because the problem asks for the minimum speed. Use the half-open template that converges lo and hi onto that boundary:

While lo < hi: take mid = (lo + hi) // 2. If feasible(mid), the answer is mid or smaller, so keep the left half including mid: hi = mid. Otherwise mid is too slow, so discard it and everything below: lo = mid + 1.
When lo == hi, that single index is the smallest feasible speed. Return it.

Notice the invariant: the range [lo, hi] always contains the smallest feasible speed, and each step halves it. The loop ends because the range strictly shrinks every iteration. Because a finishing speed is guaranteed to exist (the problem promises h >= len(piles)), hi = max(piles) is itself feasible, so the search never falls off the top.

The key insight, in one sentence

The list of candidate speeds is already sorted (it is just the integers from 1 to max(piles)), and “finishes in time” is a property that, once true, stays true as the speed rises, so finding the slowest acceptable speed is a binary search for the single point where an unsorted-looking problem’s hidden monotonic predicate flips from False to True. You never sort anything and you never build the list of speeds; you only ever evaluate feasible at a midpoint and throw away half the range.

Exact complexity

Time: O(n log(max(piles))). The binary search runs O(log(max(piles))) iterations, because each iteration halves a speed range that starts at width max(piles). Each iteration calls feasible, which is O(n) (one pass to total the hours over the n piles). Multiply them: O(n log(max(piles))). Note the log is of the largest pile, the size of the answer space, not of n; that is the tell of “binary search on the answer”.
Space: O(1). You hold a handful of integers (lo, hi, mid, a running hour total). The piles are the input and do not count; nothing extra grows with the input.

A worked check (do this by hand before you code)

Take piles = [3, 6, 7, 11], h = 8. The answer space is [1, 11]. Sanity-check the endpoints and the answer with the hours function:

Speed 3: ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3) = 1 + 2 + 3 + 4 = 10 hours. That is more than 8, so speed 3 is infeasible.
Speed 4: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8 hours. That is exactly 8, so speed 4 is feasible.

So the predicate is False at 3 and True at 4: the flip is between them, and the smallest feasible speed is 4. Confirm that your binary search converges to 4 on this input, and that it gives 30 for piles = [30, 11, 23, 4, 20], h = 5 and 23 for the same piles with h = 6. Working these by hand first is how you catch a boundary bug before the judge does.

Your work this week

Implement Koko Eating Bananas yourself, in your own work repo (for example koko-eating-bananas.py). Write the hours(k) helper first and test it in isolation on the worked example above; then wrap it in the binary search over [1, max(piles)]. Build it from the four steps; do not copy a solution.
Write the feasible predicate as its own named function or inline helper, not as a tangle inside the loop. The clarity of feasible is what makes the monotonicity argument obvious, and an interviewer will ask you to state that argument.
Run it against the worked examples by hand and in code, then submit to LeetCode’s judge. Test the edges yourself: a single pile (the answer is ceil(pile / 1) constrained by h), all piles equal, and h exactly equal to len(piles) (which forces the fastest speed, max(piles)).
Commit with a five-question debrief in the message. In answer 3, state the exact complexity above and, crucially, say what the log is the log of and why it is max(piles) and not n.

When you can explain, from memory and with no AI open, the four steps for this problem (answer space, feasible, why it is monotonic, search the boundary) and why a faster speed can never increase the hours, you own this problem. That explanation is exactly what an interviewer will ask for, and it is the template you will reuse on every “binary search on the answer” problem for the rest of your career.