Koko Eating Bananas

Problem in plain words

There are several piles of bananas and a deadline of h hours. Each hour, Koko picks one pile and eats up to k bananas from it. If the pile has fewer than k left she finishes it and waits for the next hour; she never moves to another pile within the same hour. Find the smallest whole number k that lets her finish every pile within h hours.

For instance, with piles [3, 8] and h = 4, speed 3 needs 1 + 3 = 4 hours and works, while speed 2 needs 2 + 4 = 6 hours and fails, so the answer is 3.

Intuition

For a fixed speed k, a pile of size p takes ceil(p / k) hours, and the total is just the sum over all piles. That total can only go down (or stay the same) as k grows. So the speeds split into a 'too slow' region followed by a 'fast enough' region, and we want the first speed in the second region.

Any monotonic yes/no question over a range of integers is a job for binary search. The range is 1 to max(piles): speed 1 is the slowest possible, and anything above the biggest pile is wasted because each pile already takes exactly one hour at that speed.

Approach

1. Set lo = 1 and hi = max(piles). Speed hi always works because h >= piles.length is guaranteed.
2. While lo < hi, take mid = lo + (hi - lo) / 2 and compute the hours needed at that speed: the sum of (p + mid - 1) / mid over all piles.
3. If the hours fit (hours <= h), mid is a candidate, so keep it: hi = mid.
4. Otherwise mid is too slow: lo = mid + 1.
5. When the pointers meet, lo is the minimum valid speed.

Dry run

Input: piles = [4, 9, 6], h = 5. Search range is 1 to 9.

Java solution

class Solution {
    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 (hoursNeeded(piles, mid) <= h) {
                hi = mid;        // fast enough, try slower
            } else {
                lo = mid + 1;    // too slow
            }
        }
        return lo;
    }

    private long hoursNeeded(int[] piles, int speed) {
        long hours = 0;
        for (int p : piles) {
            hours += (p + (long) speed - 1) / speed;   // ceil(p / speed)
        }
        return hours;
    }
}

Python solution

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            hours = sum((p + mid - 1) // mid for p in piles)
            if hours <= h:
                hi = mid        # fast enough, try slower
            else:
                lo = mid + 1    # too slow
        return lo

Complexity

Edge cases and common mistakes

• Integer overflow: with up to 10^4 piles of up to 10^9 bananas, the total hours at speed 1 can exceed the int range. Accumulate in a long in Java.
• Ceiling division: p / k rounds down. Use (p + k - 1) / k or Math.ceil on doubles (the integer form is safer and faster).
• Starting `lo` at 0: speed 0 causes division by zero. The lowest meaningful speed is 1.
• `h == piles.length`: each pile gets exactly one hour, so the answer is max(piles). The search handles this naturally.
• Returning the first speed that fits: a linear scan from 1 upward is correct but O(n * m), which is far too slow for large piles.