Koko Eating Bananas

Problem

Koko has n piles of bananas; pile i holds piles[i] bananas. The guards return in h hours. Koko picks a fixed eating speed k (bananas per hour). Each hour she chooses one pile and eats k bananas from it — if the pile has fewer than k left, she finishes the pile and eats nothing more that hour (she never switches piles mid-hour).

Return the minimum integer speed k that lets her finish every pile within h hours. The constraint h >= n guarantees a solution exists.

Examples

• Input: piles = [3, 6, 7, 11], h = 8 → Output: 4 (At k=4 the piles take ⌈3/4⌉+⌈6/4⌉+⌈7/4⌉+⌈11/4⌉ = 1+2+2+3 = 8 hours — exactly in time; k=3 would need 10.)
• Input: piles = [30, 11, 23, 4, 20], h = 5 → Output: 30 (Five piles, five hours: one pile per hour, so k must cover the biggest pile.)
• Input: piles = [30, 11, 23, 4, 20], h = 6 → Output: 23 (One spare hour lets her split the 30-pile into two sittings; every other pile still fits in one hour at k=23.)

Constraints

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9
• Pile sizes up to 10^9 mean candidate speeds range into the billions, so checking every speed one by one is too slow; the search over speeds must be logarithmic.

Think about it first

TL;DR

Binary search on the answer (minimum feasible speed) with an O(n) feasibility check — O(n log m) time where m = max(piles), O(1) space.

Approach 1 — Brute force (try every speed)

Check k = 1, 2, 3, … and return the first speed whose total eating time fits within h. A pile of p bananas at speed k takes ceil(p / k) hours, since a final partial hour still consumes a whole hour.

import math


def minEatingSpeed(piles: list[int], h: int) -> int:
    k = 1
    while True:
        hours = sum(math.ceil(p / k) for p in piles)
        if hours <= h:
            return k
        k += 1

Time O(n * m) where m = max(piles): up to 10^4 * 10^9 = 10^13 operations when the answer is large, which is far too slow. Space O(1).

Approach 2 — Binary search on the answer

Feasibility is monotone in k. If speed k finishes in time, every speed above k does too. So the k-axis splits into an infeasible prefix and a feasible suffix, and the answer is the boundary: the first feasible k.

flowchart LR
    A["k=1<br/>10 hrs<br/>infeasible"] --> B["k=2<br/>infeasible"] --> C["k=3<br/>10 hrs<br/>infeasible"] --> D["k=4<br/>8 hrs<br/>feasible (answer)"] --> E["k=5<br/>8 hrs<br/>feasible"] --> F["k=11<br/>4 hrs<br/>feasible"]

This calls for a boundary-finding binary search over the answer space [1, max(piles)] (at max(piles) every pile takes one hour, and h >= n makes that feasible), with each probe answered by an O(n) simulation. This is binary search on the answer: search candidate answers, not the input data.

def minEatingSpeed(piles: list[int], h: int) -> int:
    def hours_at(k: int) -> int:
        return sum((p + k - 1) // k for p in piles)   # ceil(p / k)

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_at(mid) <= h:
            hi = mid          # feasible — try a slower speed
        else:
            lo = mid + 1      # too slow — must speed up
    return lo

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

1. lo=1, hi=11 → mid=6: hours = 1+1+2+2 = 6 ≤ 8 → feasible, hi=6.
2. lo=1, hi=6 → mid=3: hours = 1+2+3+4 = 10 > 8 → lo=4.
3. lo=4, hi=6 → mid=5: hours = 1+2+2+3 = 8 ≤ 8 → hi=5.
4. lo=4, hi=5 → mid=4: hours = 1+2+2+3 = 8 ≤ 8 → hi=4.
5. lo == hi == 4 → return 4.

Time O(n log m) — about 30 probes of an O(n) check at m = 10^9. Space O(1).

Approach 3 — Binary search with integer-ceiling notes (same search, sharper check)

The feasibility check is where most bugs appear, so keep the arithmetic exact. (p + k - 1) // k and -(-p // k) both compute ceil(p / k) in pure integers; math.ceil(p / k) routes through a float, which is safe at these bounds but breaks once numerators exceed 2^53. You can also stop a probe early once the running total exceeds h.

def minEatingSpeed(piles: list[int], h: int) -> int:
    def feasible(k: int) -> bool:
        total = 0
        for p in piles:
            total += -(-p // k)      # exact integer ceil
            if total > h:            # early exit: already too slow
                return False
        return True

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Walkthrough on piles = [30, 11, 23, 4, 20], h = 5: at mid=15 the hours run 2+1+2+1+2 = 8 > 5 (infeasible → lo rises); the search climbs until k=30, where hours = 1+1+1+1+1 = 5 ≤ 5, and no smaller k is feasible since k=29 makes the 30-pile cost 2 hours (total 6). Returns 30.

Same asymptotics as Approach 2 — O(n log m) time, O(1) space — with a constant-factor win from early exit and float-free math.

Common pitfalls

• Computing hours as p // k (floor) instead of ceil — a 7-banana pile at k=4 takes 2 hours, not 1; leftover bananas still cost a full hour.
• Searching [1, sum(piles)] or beyond: speeds above max(piles) change nothing (each pile already takes one hour), so hi = max(piles) is the tight, correct cap.
• Using hi = mid - 1 on the feasible branch — the minimum feasible speed may be mid; this search needs the first-True convention (hi = mid, loop while lo < hi).
• Believing greedy pile-ordering matters: the total is a sum of per-pile ceilings, independent of the order Koko eats them — don’t simulate schedules.

Pattern takeaway

“Minimize k such that the task fits a budget” is the signature of binary search on the answer: pick the answer axis, confirm feasibility is monotone along it, write a cheap feasible(k) check, and binary search for the first True. The input is not sorted; the answer space is. The same template solves a family of problems: ship packages within D days, split array largest sum, minimum days to make bouquets.