Koko Eating Bananas

Problem in Plain English

Given banana piles and a deadline of h hours, find the slowest hourly eating speed that still finishes every pile in time. Feasibility only improves as speed rises, so the minimum feasible speed is found by binary search.

Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Return the minimum integer k such that she can eat all the bananas within h hours.

Constraints

1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9

Examples

Example 1

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

At 4 bananas per hour the piles take 1, 2, 2 and 3 hours, totalling exactly 8 hours. Speed 3 needs 1 + 2 + 3 + 4 = 10 hours, so 4 is the minimum, not just a feasible choice.

Example 2

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

With only 5 hours for 5 piles each pile must finish in one hour, so the speed must cover the largest pile.

Example 3

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

At 23 bananas per hour the piles take 2, 1, 1, 1 and 1 hours, totalling exactly 6 hours. Speed 22 needs 2 + 1 + 2 + 1 + 1 = 7 hours, so 23 is the first feasible speed.

Example 4

Input: piles = [1], h = 1
Output: 1

One banana and one hour give the smallest search interval [1, 1]; speed 1 finishes exactly on the deadline.

Example 5

Input: piles = [4,4], h = 3
Output: 4

Speed 3 still takes two hours per pile, totalling 4. Speed 4 takes one hour per pile. Unused capacity in one hour cannot move to the next pile.

Intuition

A pile needs whole hours: at speed 4, a pile of 7 takes two hours, even though the second hour is partly unused. That spare capacity cannot be spent on another pile. Therefore total hours are the sum of each pile's ceiling division, not the ceiling of the total bananas. Example 1 needs 1 + 2 + 2 + 3 = 8 hours at speed 4; speed 3 needs 10. Increasing speed can only reduce or preserve each pile's hours, creating an infeasible-then-feasible boundary to search.

Approaches

Try Every Speed

Solution Details

Reveal Try Every Speed: intuition, complexity, and code

Intuition

Speeds are tried from slowest to fastest, and the hours for a speed come from rounding each pile up to whole hours. The first speed whose total fits the deadline is the minimum, because every slower speed was already shown to fail.

Step-by-Step Logic

Scan the piles to find maxPile, a guaranteed feasible upper bound since h >= piles.length. Example 1 updates the running maximum 0 -> 3 -> 6 -> 7 -> 11.
Try every integer speed k from 1 to maxPile in increasing order. Reset hours = 0 for each trial.
For each pile, add ceil(pile / k) whole hours; unused time cannot transfer between piles. Example 1 totals 27, 15, 10, and 8 at speeds 1, 2, 3, and 4.
After scanning all piles, return k if hours <= h; otherwise continue to the next speed. Example 1 first passes at 4, which is therefore the minimum.

Why It Works

Before trying speed k, every positive integer speed below k has been checked and found infeasible. Within a trial, hours equals the sum of the required whole hours for exactly the piles already visited; adding ceiling division preserves that invariant. Distinct piles cannot share an hour, so this sum is necessary and sufficient to finish them. The first feasible trial is minimal. At maxPile every pile takes one hour, and h is at least the pile count, so a feasible trial always exists.

Dry Run

Try Every Speed: variable states at each step
Phase	Bounds / speed	Pile	Added hours	hours before -> after	Update / return
Maximum scan	-	3	-	-	maximum 0 -> 3
Maximum scan	-	6	-	-	maximum 3 -> 6
Maximum scan	-	7	-	-	maximum 6 -> 7
Maximum scan	-	11	-	-	maximum 7 -> 11
Initialize	k = 1	-	-	0	start increasing trials
Trial reset	k = 1	-	-	0 -> 0	begin full pile scan
Accumulate	k = 1	3	3	0 -> 3	next pile
Accumulate	k = 1	6	6	3 -> 9	next pile
Accumulate	k = 1	7	7	9 -> 16	next pile
Accumulate	k = 1	11	11	16 -> 27	next pile
Decide	k = 1	-	-	27	exceeds h = 8; k = 2
Trial reset	k = 2	-	-	27 -> 0	begin full pile scan
Accumulate	k = 2	3	2	0 -> 2	next pile
Accumulate	k = 2	6	3	2 -> 5	next pile
Accumulate	k = 2	7	4	5 -> 9	next pile
Accumulate	k = 2	11	6	9 -> 15	next pile
Decide	k = 2	-	-	15	exceeds h = 8; k = 3
Trial reset	k = 3	-	-	15 -> 0	begin full pile scan
Accumulate	k = 3	3	1	0 -> 1	next pile
Accumulate	k = 3	6	2	1 -> 3	next pile
Accumulate	k = 3	7	3	3 -> 6	next pile
Accumulate	k = 3	11	4	6 -> 10	next pile
Decide	k = 3	-	-	10	exceeds h = 8; k = 4
Trial reset	k = 4	-	-	10 -> 0	begin full pile scan
Accumulate	k = 4	3	1	0 -> 1	next pile
Accumulate	k = 4	6	2	1 -> 3	next pile
Accumulate	k = 4	7	2	3 -> 5	next pile
Accumulate	k = 4	11	3	5 -> 8	next pile
Decide	k = 4	-	-	8	fits h = 8; return 4

Complexity Analysis

Time Complexity

O(m \cdot n)

Space Complexity

O(1)

Let n be the pile count and m the largest pile. Finding m scans n piles; at most m trials each scan all n piles, so worst-case time is O(nm). The implementations allocate no arrays or list of trial speeds: Python range is lazy, and JavaScript finds the maximum with a loop. Counters and totals use O(1) auxiliary space; the returned speed is a scalar. This baseline can be impractical when m = 1000000000.

Code

Solution.java

1class Solution {2    public int minEatingSpeed(int[] piles, int h) {3        int maxPile = 0;4        for (int pile : piles) {5            maxPile = Math.max(maxPile, pile);6        }7        for (int k = 1; k <= maxPile; k++) {8            long hours = 0;9            for (int pile : piles) {10                hours += (pile + (long) k - 1) / k;11            }12            if (hours <= h) {13                return k;14            }15        }16        return maxPile;17    }18}

Hints

Hint 1

The slowest possible speed is 1 and the fastest ever needed is the largest single pile.

Hint 2

If a speed finishes in time, every faster speed finishes too, so the answers form a false-then-true range.

Hint 3

Binary search that range, computing each trial speed hours with ceiling division per pile.

Edge Cases

When h equals the pile count, each pile must finish in one hour, so the answer is the largest pile.
Huge piles with a tiny trial speed make the hour total overflow 32-bit integers, so the accumulator must be 64-bit.
A single pile reduces the problem to ceiling division of that pile by h.
An exact multiple uses no extra hour: a pile of 8 at speed 4 takes 2 hours, while a pile of 9 takes 3.
When h is at least the total bananas, speed 1 is feasible and minimal. Extra allowed hours need not be used.
For 10000 piles of 1000000000 bananas and h = 10000, the answer is 1000000000. A trial at speed 1 would accumulate 10000000000000 hours.

Common Mistakes and Interview Tips

Using plain integer division instead of ceiling division, which undercounts partial hours and accepts speeds that are too slow.
Summing hours in a 32-bit integer, which overflows on large piles and flips a too-slow speed into a false pass.
Searching speeds above the largest pile, where extra speed changes nothing and the answer can never hide.
Taking ceil(sum(piles) / k) incorrectly shares spare hourly capacity across piles; [4, 4], h = 3 needs speed 4, not 3.
Returning on the first feasible middle speed finds a feasible value, not necessarily the minimum. Save it and keep searching lower.
Requiring hours to equal h rejects valid solutions that finish early; the feasibility test is hours <= h.
Interview tip: state the monotone predicate and the feasible upper bound before writing binary search. In Java promote before addition in ceiling division; long hours alone does not widen a prior int expression. Under these exact limits the numerator fits int, but explicit promotion is robust.

Key Takeaway

When a minimum feasible value has a monotone pass-fail test, binary search the answer range instead of the input: the first passing value is the optimum.