Koko Eating Bananas

Problem

LeetCode 875 — Koko Eating Bananas

Koko can eat k bananas per hour, one pile at a time. Given pile sizes and h total hours, find the minimum eating speed k such that all piles are finished within h hours.

Example

piles = [3, 6, 7, 11], h = 8  →  4

At speed 4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 hours ≤ 8. ✓
At speed 3: 1+2+3+4 = 10 hours > 8. ✗

Approach

The answer lies somewhere in [1, max(piles)]. The feasibility predicate is monotone — if speed k works, so does any speed k+1. This makes the search space binary-searchable.

For each candidate speed mid:

• Sum up ceil(piles[i] / mid) across all piles.
• If total hours ≤ h → feasible; record as candidate answer and search left (smaller speeds).
• Else → not feasible; search right.

ceil(p / k) in integer math: if p % k == 0 → p/k, else p/k + 1.

Complexity

• Time: Θ(n log maxPile) — binary search runs exactly log(maxPile) iterations; each feasibility check always scans all n piles. No early exit possible, so best and worst case are the same.
• Space: O(1)

Solution

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;
        if (h < n) return -1;

        int max = piles[0];
        for (int i = 1; i < n; i++) {
            if (max < piles[i]) max = piles[i];
        }

        int l = 1;
        int r = max;
        int result = max;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (feasible(mid, piles, h)) {
                result = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return result;
    }

    private boolean feasible(int eatSpeed, int[] piles, int hour) {
        for (int i = 0; i < piles.length; i++) {
            if (piles[i] % eatSpeed == 0)
                hour = hour - piles[i] / eatSpeed;
            else
                hour = hour - piles[i] / eatSpeed - 1;
            if (hour < 0) return false;
        }
        return true;
    }
}

Bug to watch out for

Using while(l < r) misses the case when l == r at loop exit — that final value is never checked. For example piles=[3], h=3: binary search converges to l=r=1 without checking it, returning 2 instead of the correct 1. Fix: use while(l <= r).

Why It Teaches You Something

Binary search isn’t only for sorted arrays — any monotone predicate over an integer range is fair game. The same skeleton solves: