Koko Eating Bananas

This is the most valuable idea in the binary search section. The input is an unsorted list, and no index in it holds the answer. But the answers themselves — the possible speeds — are ordered, and "is this speed fast enough?" flips from no to yes exactly once as the speed grows. So you binary search the speeds.

Once you see it here, you will see it in dozens of problems: smallest capacity, least time, largest minimum gap. Interviewers use these problems because the pattern is invisible to people who think binary search means "sorted array".

The problem

There are n piles of bananas; pile i holds piles[i] bananas. An eater chooses a whole-number speed k. Each hour she picks one pile and eats k bananas from it; if the pile has fewer than k, she finishes it and does nothing else that hour. Given h hours, return the smallest speed k that finishes every pile within h hours.

• piles = [3, 6, 7, 11], h = 8 → 4. At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours. At speed 3 they take 1 + 2 + 3 + 4 = 10 hours, which is too many.
• piles = [25, 10, 15], h = 4 → 15. At 15 the piles take 2 + 1 + 1 = 4 hours; at 14, pile 15 needs 2 hours, so the total is 5.

Constraints: 1 ≤ n ≤ 10⁴, n ≤ h ≤ 10⁹, 1 ≤ piles[i] ≤ 10⁹.

Clarifying questions

• Is h at least the number of piles? Yes. Each pile takes at least one hour, so with fewer hours there is no answer.
• Must the speed be a whole number? Yes.
• Can leftover time in an hour go to another pile? No. That is what makes each pile cost ceil(pile / k) hours.
• Can piles be empty? No, each has at least one banana.

Approach 1: the simple way

Try speeds 1, 2, 3, … and return the first that finishes in time.

1def hours_needed(piles: list[int], speed: int) -> int:2    """Hours to finish every pile at this speed."""3    return sum((pile + speed - 1) // speed for pile in piles)   # ceiling division456def min_speed_linear(piles: list[int], hours: int) -> int:7    """Try every speed from 1 upward: O(n * max(piles))."""8    speed = 19    while hours_needed(piles, speed) > hours:10        speed += 111    return speed

(pile + speed - 1) // speed is the ceiling of pile / speed in integers. Adding speed - 1 pushes any remainder up to the next whole hour, while exact multiples stay the same. Check: 7 bananas at speed 4 gives (7 + 3) // 4 = 2 hours; 8 at speed 4 gives 11 // 4 = 2. Correct both times.

Time: O(n × answer), up to O(n × max(piles)). Space: O(1).

With 10⁴ piles and an answer near 10⁹, that is 10¹³ operations — hours of computing. The waste is obvious: after learning that speed 500 is too slow, it still tries 501, 502, … one at a time.

The key insight

The speeds form an ordered range, and the test "does speed k finish within h hours?" is monotonic: a faster speed never needs more hours, because every term ceil(pile / k) can only shrink or stay the same as k grows. So along the speeds, the answers read no, no, …, no, yes, yes, …, and you want the first yes. That is first_true from the core lesson, run on speeds instead of indices.

Before coding any "binary search on the answer" problem, name three things:

1. The range — the smallest and largest answers that could possibly be right. Here, speed 1 up to max(piles): no speed above the biggest pile helps, because every pile already takes exactly one hour at that speed.
2. The test — a function that checks one candidate. Here, hours_needed(piles, k) <= h, one pass over the piles.
3. Why the test is monotonic — one sentence. Here: more speed never costs more hours. If you cannot say this sentence, the technique does not apply.

The range [1, max(piles)] holds at most 10⁹ speeds. Halving it takes about 30 tests. Thirty passes over 10⁴ piles is 3 × 10⁵ operations, which runs instantly.

Approach 2: binary search the speed

1def min_eating_speed(piles: list[int], hours: int) -> int:2    """Slowest whole-number speed that finishes all piles within hours."""3    left, right = 1, max(piles)              # the answer is always in [1, max(piles)]4    while left < right:5        mid = left + (right - left) // 26        if hours_needed(piles, mid) <= hours:7            right = mid                      # mid is fast enough; maybe slower works too8        else:9            left = mid + 1                   # mid is too slow; so is everything below it10    return left

Here right starts at max(piles) instead of one past the range, because max(piles) always works (it needs n hours, and h ≥ n). So the answer is guaranteed to be inside [left, right], and the loop only has to narrow it.

Dry run on piles = [3, 6, 7, 11], h = 8:

Here the linear version also needs four tests, because the answer is small. The gap explodes with bigger piles: [10⁹] with h = 2 takes 30 tests to find 500,000,000, while the linear version would need 500 million.

Time: O(n log M), where M = max(piles): about log₂ M tests, each a pass over n piles. Space: O(1).

Same template, new test: Capacity to Ship Packages

A second problem shows that only the test changes. Packages with weights weights[i] must ship in the given order. Each day the ship loads packages in order until the next one would go over its capacity; that one waits for the next day. Find the smallest capacity that ships everything within days days.

The three ingredients:

• Range: from max(weights) — a smaller ship cannot lift the heaviest package at all — to sum(weights), which ships everything in one day.
• Test: fill days greedily and count them; the capacity works if the count is at most days.
• Monotonic: a bigger ship never needs more days.

1def days_needed(weights: list[int], capacity: int) -> int:2    """Days to ship weights in order when each day carries at most capacity."""3    days, load = 1, 04    for weight in weights:5        if load + weight > capacity:6            days += 1                        # this package starts a new day7            load = 08        load += weight9    return days101112def ship_within_days(weights: list[int], days: int) -> int:13    """Smallest capacity that ships every package, in order, within days."""14    left, right = max(weights), sum(weights)  # must lift the heaviest; one day at most15    while left < right:16        mid = left + (right - left) // 217        if days_needed(weights, mid) <= days:18            right = mid19        else:20            left = mid + 121    return left

On weights = [4, 8, 3, 5, 6, 2] with 3 days, the search tests capacities 18, 13, 10, 12 and 11, and returns 12: [4, 8], [3, 5], [6, 2]. Capacity 11 needs four days: [4], [8, 3], [5, 6], [2].

The lower bound max(weights) is about correctness, not speed. days_needed never checks whether one package is heavier than the ship; it just starts a new day and loads it anyway. Start the range at 1 and ask for 6 days on the same weights, and the search returns 4 — a ship that cannot lift the 8. (The original version of this course said the helper "never terminates sensibly" below the maximum. It does terminate; it quietly returns a count that is wrong, which is worse.)

Time: O(n log S), where S = sum(weights). Space: O(1). Both solutions were checked against their linear versions on 300 random inputs each.

The family is easy to recognise once you know the phrasing: "minimise the maximum…" (largest part of a split, slowest speed, heaviest day) or "maximise the minimum…" (smallest gap between placed items). Split Array Largest Sum is this exact code under another name. Minimum Days to Make Bouquets and Magnetic Force Between Two Balls are the same idea with a different test.

Edge cases

• h equals the number of piles: every pile must go in one hour, so the answer is max(piles). The search reaches the top of the range.
• Huge h: the answer is 1; the search walks right down to it.
• One pile: [10⁹] with h = 2 returns 500,000,000.
• Integer size: hours can reach n × max(piles) = 10¹³ at speed 1. Python does not care; in Java or C++, sum into a 64-bit integer.

Follow-ups

• "Split the array into k parts to minimise the largest part's sum." Same as shipping: range [max, sum], test "can I split into at most k parts with no part above x?".
• "Place m items in positions to maximise the smallest gap." Now you want the last gap that still works, so use last_true with mid rounded up, as in the core lesson.
• "Tighten the range." No speed below ceil(sum(piles) / h) can work, so left can start there. It saves a few steps; it does not change the complexity.