Koko Eating Bananas Solution

Problem

Koko has n piles of bananas and must finish all of them before the guards return in h hours. Each hour she picks exactly one pile and eats up to k bananas — if the pile has fewer than k, she finishes it and the hour ends. Find the minimum eating speed k (bananas per hour) that still lets her finish in time.

Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation: At speed 4, she needs ⌈3/4⌉+⌈6/4⌉+⌈7/4⌉+⌈11/4⌉ = 1+2+2+3 = 8 hours, exactly fitting within the limit.

Intuition

As Koko's speed increases, the total hours needed never goes up — it either stays the same or decreases. This monotone property means we don't need to try every speed; we can binary search over the candidate range and efficiently home in on the minimum valid speed.

Approach 1 — Linear Scan

Try every speed from 1 upward, computing total hours at each step, and return the first speed that fits within h hours.

Steps:

Iterate speed from 1 to max(piles)
For each speed, sum ceil(pile / speed) across all piles
Return the first speed where the total is ≤ h

1import math
2
3def minEatingSpeed(piles: list[int], h: int) -> int:
4    for speed in range(1, max(piles) + 1):
5        hours_needed = sum(math.ceil(pile / speed) for pile in piles)
6        if hours_needed <= h:
7            return speed
8    return max(piles)

Time: O(n × max(piles)) — scans up to max(piles) candidate speeds, checking all n piles for each
Space: O(1) — only a constant number of variables beyond the input

Approach 2 — Binary Search on Speed (Optimal)

Binary search over the speed range [1, max(piles)]. For each midpoint, compute whether that speed finishes in time. If it does, try slower; if not, try faster.

Steps:

Set low = 1, high = max(piles) (the largest pile eaten in one hour is always sufficient)
While low < high, compute mid = (low + high) // 2
Compute hours_needed = sum(ceil(pile / mid)) across all piles
If hours_needed <= h, mid is valid but might be too fast — set high = mid to preserve it as a candidate
Otherwise mid is too slow — set low = mid + 1 to search faster speeds
Return low — the smallest speed where the condition is satisfied

1import math
2
3def minEatingSpeed(piles: list[int], h: int) -> int:
4    low, high = 1, max(piles)
5
6    while low < high:
7        mid = (low + high) // 2
8        hours_needed = sum(math.ceil(pile / mid) for pile in piles)
9
10        if hours_needed <= h:
11            high = mid  # mid works; try something smaller
12        else:
13            low = mid + 1  # mid is too slow; minimum valid speed is at least mid+1
14
15    return low

Time: O(n log M) where M = max(piles) — binary search runs O(log M) rounds, each scanning all n piles
Space: O(1) — only a constant number of variables beyond the input

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n × M)	O(1)	Never — max pile can be 10⁹, making this infeasible
Binary Search	O(n log M)	O(1)	Always — this is the intended approach

Common Mistakes

Using pile // k instead of ceil(pile / k): Integer division undercounts hours — a pile of 7 at speed 5 takes 2 hours, not 1. Use (pile + k - 1) // k for exact integer ceiling, or math.ceil(pile / k) in Python.
Setting high = mid - 1 when hours fit: Since mid itself may be the minimum valid speed, shrinking to mid - 1 discards the answer. The correct update is high = mid to keep the candidate in range.
Setting high = sum(piles): Technically valid but the answer is never larger than max(piles) — at that speed even the biggest pile takes just one hour. The unnecessarily wide range wastes O(log(sum) − log(max)) rounds.
Not using long for hoursNeeded in Java/C++: At speed 1 the total hours equals sum(piles), which can reach 10⁴ × 10⁹ = 10¹³ — far beyond a 32-bit int. Accumulate into a long / long long.
Returning high instead of low: Because the loop exits when low == high, both hold the same value — but in variants where they diverge at exit, returning the wrong one gives an off-by-one. Reasoning about which side of the invariant holds the answer avoids this.

Koko Eating Bananas — Solution