Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Koko has several piles of bananas and exactly h hours before the guards return. In one hour, she chooses one pile and eats up to k bananas from that pile. If the pile has fewer than k, she finishes it and the rest of that hour is wasted.

The real task is to find the smallest integer eating speed k that still lets her finish every pile within h hours.

That framing matters, because the problem is not asking for a schedule. Once a speed is fixed, the number of hours required is forced. Each pile contributes:

ceil(pile_size / k)

hours, because Koko can only work on one pile per hour.

So the problem becomes:

“What is the smallest k such that the total required hours is at most h?”

Why binary search fits perfectly

This problem has a monotonic yes-or-no structure.

If a speed k is fast enough, then any larger speed is also fast enough. Eating faster can only reduce the total hours, never increase them.

If a speed k is too slow, then any smaller speed is also too slow.

That means the answers form a clean boundary:

  • too slow
  • too slow
  • too slow
  • fast enough
  • fast enough
  • fast enough

Whenever a problem has that shape, binary search on the answer is usually the right move.

The search range is also natural:

  • the slowest meaningful speed is 1
  • the fastest speed we ever need to consider is max(piles)

If Koko can eat the largest pile in one hour, going any faster does not help, because she still cannot eat from multiple piles in the same hour.

How to compute the hours for a candidate speed

For a guessed speed k, the only job is to total the hours across all piles:

hours_needed = sum(ceil(pile / k) for pile in piles)

In Python, the clean integer-only version is:

(pile + k - 1) // k

That avoids floating point math and directly computes the ceiling of the division.

Once that helper exists, the rest is straightforward:

  1. Pick a middle speed.
  2. Compute how many hours that speed needs.
  3. If it fits within h, keep searching left for a smaller valid speed.
  4. If it does not fit, search right for a larger speed.

A small example

Suppose the piles are [3, 6, 7, 11] and h = 8.

Try k = 4:

  • pile 3 needs 1 hour
  • pile 6 needs 2 hours
  • pile 7 needs 2 hours
  • pile 11 needs 3 hours

That totals 8, so speed 4 works.

Try k = 3:

  • pile 3 needs 1 hour
  • pile 6 needs 2 hours
  • pile 7 needs 3 hours
  • pile 11 needs 4 hours

That totals 10, so speed 3 is too slow.

Now the boundary is obvious: 3 fails, 4 works, so the minimum valid speed is 4.

How to derive this in an interview

The cleanest path is to start with the direct question: “If I already knew the eating speed, could I check whether it works?”

Yes. That check is easy because each pile is independent once k is fixed.

Next, ask what happens as k increases. The total hours only goes down, so the feasibility check is monotonic. That is the key observation that turns a brute-force search over speeds into binary search.

This is the interview-friendly derivation:

  1. Write the helper that computes hours for one guessed speed.
  2. Notice the helper gives a monotonic predicate: can_finish(speed).
  3. Binary search for the first speed where that predicate becomes true.

That progression shows understanding instead of just pattern-matching “binary search on answer.”

Python solution

from typing import List


def hours_required_for_speed(piles: List[int], eating_speed: int) -> int:
    """
    Return how many whole hours Koko needs if she eats at `eating_speed`
    bananas per hour.

    Each pile takes ceil(pile_size / eating_speed) hours because Koko can
    work on at most one pile per hour.
    """
    total_hours = 0

    for pile_size in piles:
        # Integer-only ceiling division: ceil(pile_size / eating_speed)
        total_hours += (pile_size + eating_speed - 1) // eating_speed

    return total_hours


def minimum_eating_speed(piles: List[int], available_hours: int) -> int:
    """
    Binary search for the smallest eating speed that finishes all piles
    within `available_hours`.
    """
    if not piles:
        return 0

    # This lower bound is safe and often tighter than starting from 1.
    minimum_possible_speed = max(1, (sum(piles) + available_hours - 1) // available_hours)
    maximum_possible_speed = max(piles)

    left = minimum_possible_speed
    right = maximum_possible_speed

    while left < right:
        middle_speed = left + (right - left) // 2
        required_hours = hours_required_for_speed(
            piles=piles,
            eating_speed=middle_speed,
        )

        # If this speed works, keep the answer and look for a smaller one.
        if required_hours <= available_hours:
            right = middle_speed
        else:
            left = middle_speed + 1

    return left


class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        return minimum_eating_speed(piles=piles, available_hours=h)

Why this works

The helper hours_required_for_speed is correct because it sums the exact number of whole hours needed for each pile at a fixed speed. Since Koko can only eat from one pile per hour, each pile independently costs ceil(pile / k) hours.

The binary search is correct because feasibility is monotonic. If a speed k finishes on time, every speed larger than k also finishes on time. If k does not finish on time, every smaller speed also fails. So there is a first valid speed, and binary search finds exactly that boundary.

If there are n piles and the largest pile has size M, each feasibility check costs O(n), and the binary search performs O(log M) checks. The total time is O(n log M), and the extra space is O(1) aside from the input.

Interview follow-ups

Yes, but it is much worse. A direct simulation that tests every speed from 1 upward would work in principle, because for each speed it can compute the total hours and stop at the first valid one. The problem is that the answer might be close to max(piles), so that approach becomes O(nM) in the worst case, where M is the largest pile size. Binary search reduces the number of candidate speeds from a full linear scan to only O(log M) checks, which is the real optimization that matters here.

Why is max(piles) a valid upper bound?

Because once Koko can eat the entire largest pile in one hour, every other pile also takes at most one hour. That means the total time is at most the number of piles. In the LeetCode version of the problem, the input guarantees a feasible answer, so searching up to max(piles) is always enough. Speeds above that do not create any new behavior, because Koko still cannot work on two piles during the same hour.

Can the lower bound be better than 1?

Yes. A stronger lower bound is ceil(sum(piles) / h), because Koko must eat all bananas within h hours, so her average rate cannot be lower than total bananas divided by total available hours. That bound does not solve the problem by itself, because the one-pile-per-hour rule can still force the answer higher, but it is a safe place to start the binary search. It slightly shrinks the search range without changing the overall O(n log M) complexity.

What changes if Koko is allowed to switch piles within the same hour?

Then the one-pile-per-hour restriction disappears, which changes the math completely. At speed k, Koko can eat exactly k bananas per hour no matter how those bananas are split across piles, so the total hours needed becomes ceil(sum(piles) / k). In that version, the structure is even simpler because only the total number of bananas matters, not the distribution across piles. The same binary-search-on-answer pattern still works, but the feasibility check becomes much cheaper conceptually because it no longer sums a ceiling term for every individual pile.

What if the interviewer wants the exact proof that the predicate is monotonic?

The proof is short. For any pile size p, the function ceil(p / k) never increases when k increases. Therefore the total function sum(ceil(pile / k) for pile in piles) also never increases as k gets larger. Since the required hours move in only one direction, the predicate “can finish within h hours” changes from false to true at most once. That one-way transition is exactly the condition binary search needs.

Practical takeaway

The important move is to stop thinking about bananas and start thinking about answer space.

Once the candidate speed becomes the variable, the problem turns into a monotonic feasibility check. From there, the optimal solution is just binary search wrapped around a simple hour-counting helper.