Binary Search on Answer — Koko Eating Bananas

↗ LeetCode: Koko Eating Bananas · Medium · pattern chapter →

Asked atGoogleAmazonMeta

Koko has n piles of bananas, piles[i] in each. She can eat at speed k bananas/hour. Each hour she picks one pile; if it has ≥ k bananas she eats k, otherwise she eats the whole pile (and rests the remainder of that hour). She must finish all piles in h hours. Return the minimum k.

Example 1 — piles=[3,6,7,11], h=8 → 4Example 2 — piles=[30,11,23,4,20], h=5 → 30Example 3 — piles=[30,11,23,4,20], h=6 → 23

Constraints — 1 ≤ n ≤ 10⁴; 1 ≤ piles[i] ≤ 10⁹; n ≤ h ≤ 10⁹.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force (try every speed)

Intuition. Try k = 1, 2, 3, … in order; return the first k that finishes on time.

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

Complexity — Time O(max(piles) · n) worst-case; Space O(1). At piles[i] = 10⁹ this is a trillion operations. TLE.

---

Approach 2 — Binary search on the answer

Insight from brute. The feasible(k) predicate is monotonic: if speed k finishes on time, then every k' > k also does. That's a sorted boolean array of [false, false, …, true, true, …]. Binary search for the first true.

Range. lo = 1, hi = max(piles). Any speed above max(piles) finishes in exactly n hours (one pile per hour), which fits since n ≤ h.

Trap. Get the feasibility direction right: feasible(k) = totalHours(k) ≤ h. Flipping this returns the fastest failing speed instead of the slowest passing one.

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;   // keep candidate
        else                          lo = mid + 1;
    }
    return lo;
}
private boolean feasible(int[] piles, int k, int h) {
    long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;
    return hours <= h;
}

Execution Trace

BS on answer — piles=[3,6,7,11], h=8

Step 1 / 5speed 6 → 6 hrs ≤ 8 → hi=mid=6

Complexity — Time O(n log max); Space O(1). Optimal.

---

Try it yourself

Complexity summary

Approach	Time	Space
Linear scan on k	O(n · max)	O(1)
Binary search on answer	O(n log max)	O(1)

When to use which

• "Minimum X such that … works" or "maximum X such that … works" → BS on answer.
• Sanity-check the feasibility direction: feasible(minSpeed) should be false, feasible(maxSpeed) should be true. If not, you have the polarity wrong.

✨AI Study CompanionBeta

Related problems (same ladder applies)

• Capacity To Ship Packages Within D Days — same skeleton with capacity as the answer
• Split Array Largest Sum — feasibility: can we split into ≤ m parts each with sum ≤ cap
• Minimize Max Distance to Gas Station — real-number BS on max gap
• Median of Two Sorted Arrays — BS on the partition point

Was this page helpful?