Koko Eating Bananas

Approach Summary

Binary search on the answer (eating speed). Feasibility check: can Koko finish all bananas at speed k within h hours?

Full Solution & Approach

This is binary search on the answer. The eating speed k ranges from 1 (slowest) to max(piles) (eating the biggest pile in one hour). For a given speed k, the time to eat pile p is ceil(p / k), and Koko finishes if the sum over all piles is at most h. That feasibility check is monotonic: if speed k works, every larger speed also works. So binary search the smallest k that satisfies the check. The feasibility function runs in O(n), and the answer space is bounded by the largest pile, giving O(n log(max pile)). Recognize the pattern by the phrasing "minimum X such that condition holds" with a large numeric range — capacity-to-ship and split-array problems share the exact skeleton: binary search the answer, write a feasibility check, keep the leftmost feasible value.

Binary search over a range of size max(piles) with an O(n) check per step — O(n log(max(piles))). Only a few scalars — O(1) space.

Solution Code

Solution

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    def feasible(k: int) -> bool:
        return sum(math.ceil(p / k) for p in piles) <= h

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

function minEatingSpeed(piles, h) {
  const feasible = (k) =>
    piles.reduce((t, p) => t + Math.ceil(p / k), 0) <= h;
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(piles, mid, h)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private boolean feasible(int[] piles, int k, int h) {
    int hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;
    return hours <= h;
}

int minEatingSpeed(const vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(piles, mid, h)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

bool feasible(const vector<int>& piles, int k, int h) {
    long long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;
    return hours <= h;
}

Edge Cases to Watch

h equal to len(piles) — Koko must eat one pile per hour; speed equals the largest pile
A single pile — speed is ceil(pile / h)
h larger than needed — speed 1 may already suffice
Piles larger than h — impossible inputs are excluded by constraints

How to Recognize This Pattern

Minimum rate/speed that satisfies a constraint

Complexity Analysis

Time Complexity

O(n log m)

Space Complexity

O(1)