Koko Eating Bananas

MediumBinary Search · Answer Space🧩 Binary Search LeetCode #875 ↗Updated Oct 30, 2026

Problem

There are piles[i] bananas in each pile and h hours available. Each hour Koko picks one pile and eats up to k bananas from it (if fewer remain, she finishes that pile and idles the rest of the hour). Return the smallest integer speed k that lets her finish every pile within h hours.

Input[3,6,7,11], h=8Output4

Input[30,11,23,4,20], h=5Output30

Input[30,11,23,4,20], h=6Output23

1 ≤ n ≤ 10⁴ · n ≤ h ≤ 10⁹ · 1 ≤ piles[i] ≤ 10⁹

Try it yourself

Java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Hours needed, Σ ⌈pile / k⌉, only decreases as k grows, so “can finish at speed k” is false…false, true…true. Binary search the speed for the first true.

PatternBinary Search

Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.

Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.

Open the Binary Search guide →

Approaches

Brute ForceTry Every Speed

Time O(n · max)Space O(1)

Speed max(piles) always works (one hour per pile, and h ≥ n). So try k = 1, 2, 3, … and return the first speed whose total hours fit in h. Each check costs O(n).

Java

public int minEatingSpeed(int[] piles, int h) {
    int maxPile = 0;
    for (int p : piles) maxPile = Math.max(maxPile, p);
    for (int k = 1; k < maxPile; k++) {
        if (canFinish(piles, h, k)) return k;
    }
    return maxPile;
}
private boolean canFinish(int[] piles, int h, int k) {
    long hours = 0; // can exceed int range
    for (int p : piles) {
        hours += (p - 1) / k + 1; // ceil(p / k)
        if (hours > h) return false;
    }
    return true;
}

Correct, but up to 10⁹ speeds × 10⁴ piles — hopeless.

OptimalBinary Search on Speed

Time O(n log max)Space O(1)

Search k in [1, max(piles)]. If mid is feasible, record it and look for something smaller (right = mid - 1); otherwise Koko is too slow (left = mid + 1). Monotonicity guarantees we never discard the answer.

Java

public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = 0;
    for (int p : piles) right = Math.max(right, p);
    int result = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, h, mid)) {
            result = mid;      // feasible: try slower
            right = mid - 1;
        } else {
            left = mid + 1;    // too slow: speed up
        }
    }
    return result;
}
private boolean canFinish(int[] piles, int h, int k) {
    long hours = 0;
    for (int p : piles) {
        hours += (p - 1) / k + 1; // ceil(p / k) without overflow
        if (hours > h) return false;
    }
    return true;
}

Dry runpiles=[3,6,7,11], h=8, k∈[1,11]

cells hours per pile at speed k changed

k=6
1

1

2

2

6 ≤ 8 ✔ ans=6, r=5
k=3
1

2

3

4

10 > 8 ✘ l=4
k=4
1

2

2

3

8 ≤ 8 ✔ ans=4, r=3
end
1

2

2

3

l=4 > r=3 → return 4

~30 feasibility checks instead of up to 10⁹.

Pro tip

Tighten the low end to ⌈sum / h⌉ — any slower speed can't possibly eat everything in time.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Speed	`O(n · max)`	`O(1)`
Optimal	Binary Search on Speed	`O(n log max)`	`O(1)`

Common pitfalls

Summing hours in an int — at k=1 the total can reach 10¹³.
(p + k - 1) / k in int overflows near 2·10⁹; use (p-1)/k + 1.
Starting the search at 0 — division by zero; the minimum speed is 1.

Interview tips

Say it out loud: “minimise k such that f(k) is true, f monotone” ⇒ binary search.
Justify the bounds: 1 is the slowest speed, max(piles) always suffices.
Mention the early exit in canFinish once hours exceed h.

Pattern

Binary search on the answer → “minimum/maximum value such that a check passes” with a monotone check.

My notes saved in this browser