mediumBinary Search

Koko Eating Bananas

Each hour, eat up to k bananas from one pile. Any unused capacity that hour is lost. Find the smallest positive k that finishes all piles within h hours.

LeetCode ↗

Work through the cases

3 examples

Input notation

Positive pile sizes on line 1; h on line 2, at least the number of piles.

Expected result

The minimum eating speed.

Case 1

Input

4 8 12
6

Expected output

Case 2

Input

9
2

Expected output

Case 3

Input

3 6
2

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

A larger speed k finishes sooner; we want the smallest k that finishes within h hours. h and pile sizes reach 10^9, so we binary-search the monotone predicate “can finish in h hours”. Search [1,\max piles]; the check sums \lceil x/k\rceil over piles. The first feasible speed is the answer.

We notice that if Koko can eat all the bananas at a speed of k within h hours, then she can also eat all the bananas at a speed of k' > k within h hours. This shows monotonicity, so we can use binary search to find the smallest k that satisfies the condition.

We define the left boundary of the binary search as l = 1, and the right boundary as r = \max(piles). For each binary search, we take the middle value mid = \frac{l + r}{2}, and then calculate the time s required to eat bananas at a speed of mid. If s ≤ h, it means that the speed of mid can meet the condition, and we update the right boundary r to mid; otherwise, we update the left boundary l to mid + 1. Finally, when l = r, we find the smallest k that satisfies the condition.

The time complexity is O(n × log M), where n and M are the length and maximum value of the array piles respectively. The space complexity is O(1).

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = (int) 1e9;
        while (l < r) {
            int mid = (l + r) >> 1;
            int s = 0;
            for (int x : piles) {
                s += (x + mid - 1) / mid;
            }
            if (s <= h) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.