4.11.3 — Koko Eating Bananas

LeetCode 875 · Medium

The problem

There are n piles of bananas. Koko eats at k bananas per hour. Each hour she picks one pile and eats up to k from it — if the pile has fewer than k left, she finishes it and stops for that hour, so a pile never carries over into someone else's hour.

Find the smallest k that lets her finish every pile within h hours.

piles = [3,6,7,11], h = 8   →  4
piles = [30,11,23,4,20], h = 5  →  30

h is at least the number of piles, so an answer always exists.

The pattern

There is no sorted array here, and nothing to search through. This is the problem that shows binary search does not need one.

Ask a different question. For a given speed k, can she finish in time? That is easy to answer: work out how many hours each pile takes and add them up.

\text{hours for a pile} = \left\lceil \frac{\text{pile}}{k} \right\rceil

Now notice the shape of the answers as k increases:

k:        1    2    3    4    5    6   ...
in time?  no   no   no   yes  yes  yes ...
                         ↑
                    the answer

Once a speed is fast enough, every faster speed is also fast enough. The answers go no, no, no, yes, yes, yes and never flip back. That is a monotonic predicate, and it is exactly the structure binary search needs.

So binary search the speed, not the array. This move has a name — binary search on the answer — and it turns a whole family of "find the minimum X that works" problems into ten lines.

The three things to check before using it:

1. The answer is a number in a known range.
2. "Does value X work?" is easy to check.
3. If X works, everything above X works too — or below, depending on direction.

The range

The slowest sensible speed is 1. The fastest useful speed is max(piles), because eating faster than the biggest pile cannot help — each hour is capped at one pile anyway.

So the search space is 1 … max(piles).

The solution

Python

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def hours_needed(k: int) -> int:
            return sum((p + k - 1) // k for p in piles)      # ceiling division

        low, high = 1, max(piles)

        while low < high:                    # fence model: converge on a boundary
            mid = low + (high - low) // 2
            if hours_needed(mid) <= h:
                high = mid                   # mid works — it might be the answer
            else:
                low = mid + 1                # mid is too slow — discard it

        return low

TypeScript

function minEatingSpeed(piles: number[], h: number): number {
  const hoursNeeded = (k: number) =>
    piles.reduce((sum, p) => sum + Math.ceil(p / k), 0);

  let low = 1, high = Math.max(...piles);

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (hoursNeeded(mid) <= h) high = mid;
    else low = mid + 1;
  }

  return low;
}

This is shape B from 4.11.1 — the boundary search. Three things follow from that and all three matter:

while low < high, not <=. The loop ends when the range collapses to one value, and that value is the answer.

high = mid, not mid - 1. When mid works, it might be the smallest thing that works, so it must stay in the range. Discarding it would lose the answer.

No equality check anywhere. There is nothing to find. The loop converges on the boundary between "too slow" and "fast enough", and low is the first value on the working side.

Ceiling division without floating point

(p + k - 1) // k is integer ceiling division. It is worth understanding rather than memorising.

To round p / k up, add just enough to push any non-zero remainder over the next whole number. k - 1 is exactly enough: if p divides evenly, adding k - 1 is not enough to reach the next multiple, so nothing changes. If there is any remainder, it is enough.

Check it: 7 / 3 should be 3. (7 + 2) // 3 = 9 // 3 = 3 ✓. And 6 / 3 should be 2. (6 + 2) // 3 = 8 // 3 = 2 ✓.

Why not math.ceil(p / k)? Because that converts to a float first. For values near 2^{53} the float cannot represent the number exactly, and the answer comes out wrong. Integer arithmetic has no such limit. On this problem the values are small enough that either works, but the integer version is the one to have in your fingers.

Complexity

O(n \log(\max(\text{piles}))) — the binary search takes \log(\max) steps and each step scans all n piles.

O(1) space.

The log factor is over the values, not the array length. That is characteristic of binary search on the answer, and it is worth saying explicitly, because it is what makes the technique cheap even when the answer range is enormous.

Where this goes next

Every one of these is the same ten lines with a different works(x) function:

• Capacity To Ship Packages Within D Days — the check is "can these packages fit in D shipments with capacity x". The range runs from max(weights) to sum(weights).
• Split Array Largest Sum — identical to the shipping problem, worded as an array split.
• Minimum Number of Days to Make m Bouquets — the check walks the array counting adjacent bloomed flowers.
• Find the Smallest Divisor Given a Threshold — the check is this exact ceiling-division sum.
• Minimize Max Distance to Gas Station — the answer is a real number, so you binary search on floats and stop when the range is smaller than the required precision.

The recognition cue, worth memorising: the problem says minimise the maximum, or maximise the minimum, or find the smallest X such that. That phrasing almost always means binary search on the answer.

What the interviewer will push on

"Why can you binary search when there is no sorted array?" Because the yes/no answers over the range are monotonic. State the three conditions.

"What is your search range and why?" 1 to max(piles). Faster than the biggest pile gains nothing, because each hour is capped at one pile.

"Why high = mid and not mid - 1?" A working value might be the answer, so it stays in the range.

"Why integer ceiling division?" Floats lose precision at large magnitudes, and (p + k - 1) // k is exact.

"What is the complexity?" O(n \log(\max)) — and point out the log is over values, not array length.

One thing to volunteer: name the technique and state the monotonic property in one sentence. "If speed k finishes in time, every speed above k does too, so the answers are monotonic and I can binary search the speed."

Next: 4.11.4 Find Minimum in Rotated Sorted Array — back to an array, but one whose sorted order has been broken in exactly one place.