Problem 11.7 · Binary SearchMedium

Koko Eating Bananas

What it teaches: Binary search on the answer: test a speed with a quick feasibility check and halve the range of speeds.

Practise it on judges as “Koko Eating Bananas”.

The problem

Koko has piles of bananas and h hours. Each hour she picks one pile and eats up to k bananas from it. Return the minimum integer speed k that lets her finish within h hours.

Example 1

Input: piles = [3, 6, 7, 11], h = 8
Output: 4

Example 2

Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30

Constraints

1 ≤ piles.length ≤ h ≤ 10⁹
1 ≤ piles[i] ≤ 10⁹

Pattern clues in the wording

→ "Minimum speed such that" she finishes in time
→ Faster speeds never hurt: monotonic
→ Answer range up to 10⁹

These clues point to Binary Search on the Answer: When you can check "is answer x good enough?" and the check is monotonic, binary search over possible answers.

Stuck? Take one hint at a time

Solution.java · starter

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	piles = [3,6,7,11] h = 8	4
2	piles = [30,11,23,4,20] h = 5	30
3	piles = [30,11,23,4,20] h = 6	23

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Try every speed · O(n · max(piles))2. Optimal: binary search the speed · O(n log(max pile))

Try every speed

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

Check k = 1, 2, 3, ... until one works.

Approach 1

class Solution {
    public int minEatingSpeed(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;
        }
    }
}

Verdict: Up to 10⁹ speeds: far too slow.

Optimal: binary search the speed

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

lo = 1, hi = max(piles). feasible(k) = sum of ceil(p / k) ≤ h. Find the first feasible k with the first-true template.

Approach 2

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;
            long hours = 0;
            for (int p : piles) hours += (p + mid - 1) / mid;
            if (hours <= h) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

Verdict: About 30 feasibility checks.

Before you submit

Edge cases and common mistakes

Test these inputs

h equals the number of piles (speed = max pile)
One huge pile
h very large (speed 1)

Mistakes people make

Summing hours in an int (overflow with 10⁴ piles and speed 1).
Using floating-point division for the ceiling.

Interview

Follow-up questions

Why is hi = max(piles) enough?

Command Palette