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. You’re guaranteed h >= n, so a solution always 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 — per-candidate checking must be paired with something 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


class Solution:
    def minEatingSpeed(self, 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 — dead on arrival. Space O(1).

Approach 2 — Binary search on the answer

The insight: feasibility is monotone in k. Eating faster never hurts: 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. That’s 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 the classical binary search on the answer technique: search candidate answers, not data.

class Solution:
    def minEatingSpeed(self, 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 insight: the feasibility check is where correctness usually leaks, so make 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 a habit that breaks once numerators exceed 2^53. You can also stop a probe early once the running total exceeds h.

class Solution:
    def minEatingSpeed(self, 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, prove feasibility is monotone along it, write a cheap feasible(k) check, and binary search for the first True. The data structure is irrelevant — the sorted thing is the answer space itself. This template dispatches a whole family of problems (ship packages within D days, split array largest sum, minimum days to make bouquets).