Koko Eating Bananas — Binary Search on Answer

The Problem

Koko loves bananas. There are n piles of bananas, with piles[i] bananas in the i-th pile. The guards return in h hours. Koko picks an eating speed k bananas per hour. Each hour she picks a pile and eats up to k bananas from it; if the pile has fewer than k bananas, she finishes it that hour and waits for the next hour to start a new pile. Return the minimum k such that she finishes all the piles within h hours.

The phrasing is whimsical, but underneath it is a binary-search-on-answer problem: the speed range is bounded, and the feasibility predicate “can she finish within h hours at speed k” is monotonic in k.

Intuition

If Koko can finish at speed k, she can also finish at any higher speed. So the predicate “feasible at speed k” is monotonic: false up to some threshold k*, true from k* onward. Binary search the smallest feasible k over the range [1, max(piles)]. The feasibility check for a candidate k sums ceil(p / k) across piles and compares to h. Ceiling division in integer math is (p + k - 1) // k, which sidesteps any floating-point concern.

Explanation with Example

Take piles = [3, 6, 7, 11], h = 8. The search range is [1, 11].

lo=1  hi=11  mid=6  hours=ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)=1+1+2+2=6 <=8 -> hi=6
lo=1  hi=6   mid=3  hours=1+2+3+4=10 >8 -> lo=4
lo=4  hi=6   mid=5  hours=1+2+2+3=8 <=8 -> hi=5
lo=4  hi=5   mid=4  hours=1+2+2+3=8 <=8 -> hi=4
lo=4  hi=4   return 4

The minimum speed is 4.

Code

The loop invariant: the answer is always in [lo, hi]. When lo == hi they are the answer. On a feasible mid, set hi = mid (not mid - 1) because mid itself might be the answer.

def minEatingSpeed(piles, h):
    def hours_at(k):
        return sum((p + k - 1) // k for p in piles)

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

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 (hoursAt(piles, mid) <= h) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private long hoursAt(int[] piles, int k) {
        long total = 0;
        for (int p : piles) {
            total += (p + k - 1) / k;
        }
        return total;
    }
}

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minEatingSpeed(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 (hoursAt(piles, mid) <= (long long)h) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

private:
    long long hoursAt(const vector<int>& piles, int k) {
        long long total = 0;
        for (int p : piles) total += (p + k - 1) / k;
        return total;
    }
};

Edge Cases

If h == len(piles), Koko needs one hour per pile and can only have speed max(piles). If h is huge, speed 1 is sufficient. The bounds [1, max(piles)] cover both extremes.

If a pile has zero bananas (the problem guarantees positive, but defensively), (0 + k - 1) // k = 0, no time spent. If piles is empty, the question is degenerate; the problem guarantees at least one pile.

For very large pile values, the ceiling division can be computed via (p + k - 1) // k to avoid floating-point error in other languages.

Complexity Analysis

Time is O(n log M) where M = max(piles). Each binary-search iteration does an O(n) feasibility check; there are O(log M) iterations.

Space is O(1): just integer variables.

For typical constraints (n up to 10^4, piles up to 10^9), that’s about 10^4 * 30 = 3 * 10^5 operations — instantaneous.

How to Explain It in an Interview

Start with the monotonicity argument: at higher speeds Koko takes fewer or equal hours, so the feasibility predicate is monotonic non-increasing as a function of speed. That justifies binary search on the answer.

Then describe the bounds: speed must be at least 1 and at most max(piles). Above max(piles) she’s just idle the rest of each hour. Below 1 isn’t allowed.

Write the search, narrate the ceiling-division formula, and finish with O(n log M) and O(1).

Watch for the off-by-one: when the predicate is true, set hi = mid (not mid - 1) because mid might be the answer.

Related Problems

• Capacity to Ship Packages Within D Days — same pattern.
• Split Array Largest Sum — binary search on max subarray sum.
• Maximum Candies Allocated to K Children — binary search on candies per child.
• Minimized Maximum of Products Distributed to Any Store.