Koko Eating Bananas

Koko the monkey is alone with n piles of bananas — the i-th pile holds piles[i] bananas. The zookeepers have stepped out and will be back in h hours.

Koko picks a fixed eating speed of k bananas per hour. Each hour she chooses one pile and eats k bananas from it. If fewer than k bananas remain in that pile, she finishes the pile and eats nothing more that hour — she never touches a second pile within the same hour.

Koko likes eating slowly, but every banana must be gone before the keepers return.

Return the minimum integer speed k that lets Koko finish all the bananas within h hours.

Hints

· Stuck? Reveal one nudge at a time.

You are not searching the array — you are searching for a speed. What is the smallest speed that could ever work, and the largest speed that is ever needed?

For a fixed speed k, one pass computes the hours Koko needs: each pile costs ceil(piles[i] / k) hours. Can you decide feasibility in O(n)?

If speed k finishes in time, every faster speed does too — a monotone NO…NO YES…YES split. Binary search the smallest YES in [1, max(piles)].

Common doubts

At speed max(piles) every pile takes exactly one hour, and the constraints guarantee h >= piles.length — so that speed always finishes in time. Eating faster cannot help: Koko still spends a full hour per pile.

Hours come in whole units. A pile of 7 at speed 3 takes 3 hours (3 + 3 + 1), not 2. In integer math, round up with (p + k - 1) // k.

No. Each hour she commits to a single pile; if she empties it early, the rest of the hour is wasted. That rule is what makes each pile's cost independent and the total a simple sum.

It never searches the array — it searches the range of speeds 1..max(piles), which is implicitly sorted. Feasibility is monotone over that range, and that is all binary search needs.

Interview follow-ups

· What an interviewer asks next.

No speed works — even infinitely fast, Koko spends one hour per pile. Pointing out that the guarantee h >= piles.length is what makes an answer exist is a strong senior signal.

Yes — ceil(total_bananas / h) is a valid lower bound, since h hours at speed k eat at most k*h bananas. It shrinks the window, though the log factor already makes the search essentially free.

Any problem with a monotone feasibility check over a numeric answer: shipping packages within D days, splitting an array to minimize the largest sum, allocating pages to students, placing aggressive cows. The template is identical — binary search the answer, verify greedily in O(n).

Fun facts

This problem is the poster child of a pattern called binary search on the answer: instead of locating an index in an array, you locate a value in the answer space, using a monotone yes/no test as your compass.
Roughly 30 feasibility checks suffice for any bound up to 10^9 — doubling the input range costs exactly one extra check, which is why the pattern scales so gracefully.

Asked at

AmazonGoogleMetaBloombergUber

Frequently Sometimes Occasionally

Example 1

Input: piles = [3,6,7,11], h = 8
Output: 4
At speed 4 the piles take 1 + 2 + 2 + 3 = 8 hours — exactly on time. Speed 3 needs 10 hours, too slow.

Example 2

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Five piles, five hours — one hour per pile, so k must swallow the biggest pile whole: 30.

Example 3

Input: piles = [30,11,23,4,20], h = 6
Output: 23
One spare hour lets Koko split only the largest pile across two hours: at speed 23 the costs are 2 + 1 + 1 + 1 + 1 = 6 hours.

Constraints

- 1 <= piles.length <= 10^4 - piles.length <= h <= 10^9 - 1 <= piles[i] <= 10^9

A deadline, a dial to set, and a yes/no question — Koko Eating Bananas is the cleanest introduction to binary search on the answer, a pattern that turns find the smallest value that works problems into a 30-step search. Master it here and a whole family of problems falls open.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search on a monotone predicate. Searching for the boundary in a run of NOs followed by a run of YESes — not for a value in a sorted array.

Ceiling division with integers. Computing ceil(a / b) without floats as (a + b - 1) / b — the cost of one pile at a fixed speed.

Reading constraints for complexity. Values up to 10^9 with n up to 10^4 rule out trying every speed and point at an O(n log max) shape.

Understand the problem

In plain English: pick an integer speed k. Each hour Koko eats from one pile only — k bananas, or the whole pile if fewer remain, wasting the rest of that hour. Pile i therefore costs exactly ceil(piles[i] / k) hours, independent of every other pile. Find the minimum k such that the total hours are at most h.

Worked example — piles = [3,6,7,11], h = 8

speed k = 4:
  pile 3  → 1 hour        (eats 3, hour over)
  pile 6  → 2 hours       (4, then 2)
  pile 7  → 2 hours       (4, then 3)
  pile 11 → 3 hours       (4, 4, then 3)
  total 1+2+2+3 = 8 ≤ 8   ✓ finishes in time

speed k = 3: 1+2+3+4 = 10 > 8   ✗ too slow
answer: 4

Clarifying questions

Two or three sharp questions before coding show you probe the rules instead of assuming them.

Questions to ask first

· Signals seniority before you write a line of code.

Rules of eating

“If Koko finishes a pile mid-hour, can she start the next pile in the same hour?”

No — the leftover time is wasted. This is exactly why each pile independently costs ceil of piles[i] / k hours, which makes the feasibility check a simple sum.

“Is the speed k required to be an integer?”

Yes. That makes the answer space the discrete range 1 to max(piles), which binary search can walk in about 30 steps.

Input validity

“Is h always at least the number of piles?”

Yes — the constraints guarantee it. Each hour covers at most one pile, so with fewer hours than piles no speed, however large, could ever finish.

“Can a pile be empty?”

No, every pile holds at least one banana, so the minimum useful speed is 1 and division by zero never threatens the ceiling formula.

Constraints and scale

“How big can the pile sizes and h get?”

Both reach 10^9. Any approach that tries speeds one by one is dead on arrival; the number of candidate speeds must shrink exponentially.

The ideal opening — say it like this

Before I code, let me pin down the rules.

Each hour Koko commits to a single pile and any leftover time that hour is wasted — so pile i costs the ceiling of piles[i] divided by k hours, correct?

And since h is at least the number of piles, speed max(piles) always finishes in time — so an answer always exists between 1 and max(piles).

Key observations

1Aha

Checking one speed is a single O(n) pass

Fix a speed k. Pile i costs ceil(piles[i] / k) hours, so hours(k) = Σ ceil(piles[i] / k). Speed k is feasible when hours(k) <= h. The whole problem collapses to: find the smallest feasible k.

2Aha

Feasibility is monotone — faster never hurts

If Koko finishes in time at speed k, she certainly finishes at k + 1. So the answer space splits into a block of NOs followed by a block of YESes:

k:        1   2   3   4   5   6  ...  11
feasible: ✗   ✗   ✗   ✓   ✓   ✓  ...   ✓
                      ↑
              first YES = answer

3Aha

Binary search the boundary, not the array

The first YES in a NO…NO YES…YES sequence is exactly what binary search finds. Search [1, max(piles)] — the top end is always feasible because h >= piles.length means one hour per pile suffices. That is log2(10^9) ≈ 30 checks of O(n) each: about 3 × 10^5 operations instead of 10^13.

Brute force vs optimal

	Brute force	Optimal
Time	O(n · max(piles))	O(n log max(piles))
Space	O(1)	O(1)

Full code for both approaches lives in the Approaches selector below.

Summary

Key takeaway

When a problem asks for the minimum (or maximum) value passing a monotone can-we-do-it test, do not search the data — binary search the answer space and pair it with a linear feasibility check.

lo = 1, hi = max(piles)
while lo < hi:
    mid = (lo + hi) / 2
    if sum(ceil(p / mid) for p in piles) <= h:
        hi = mid        # mid works — try slower
    else:
        lo = mid + 1    # too slow — speed up
return lo