Koko Eating Bananas LeetCode 875 Guide

LeetCode 875 — Koko Eating Bananas — gives you n piles of bananas and h hours before the guards return. Koko can decide her eating speed k (bananas per hour). Each hour she chooses one pile and eats up to k bananas from it. If the pile has fewer than k bananas, she finishes the pile and does not eat from another pile that same hour. The goal is to find the minimum integer eating speed k such that Koko can eat all bananas within h hours.

The key formula is: for a given speed k, the hours needed to finish a single pile is ceil(pile / k). The total hours needed is the sum of ceil(pile / k) for all piles. Koko can finish within h hours if and only if this total is at most h. Your task is to find the smallest k for which this condition holds.

This problem is a classic example of binary search on the answer — sometimes called parametric search. Rather than searching through an array, you search through the space of possible answers (eating speeds) and test each candidate with a feasibility function. The feasibility function is what makes binary search applicable here.

The answer k is monotonic with respect to feasibility: if Koko can finish all piles at speed k, she can also finish at any speed greater than k. This monotonicity is the prerequisite for binary search. The eating space ranges from 1 (minimum possible speed) to max(piles) (eating the largest pile in a single hour, so total hours equals n which is at most h). This gives a well-bounded search range.

Instead of trying every possible speed from 1 to max(piles) in O(max_pile) time, binary search cuts this down to O(log(max_pile)) iterations. At each iteration, we test the midpoint speed with the feasibility function. If speed mid works, we try lower speeds by moving hi to mid. If it does not work, we need a higher speed so we move lo to mid+1. This is the leftmost-true binary search pattern.

The total time complexity is O(n * log(max_pile)) where n is the number of piles and the log factor comes from binary search iterations. Space is O(1) since the feasibility check only needs a running sum. For the given constraints (n up to 10^4, pile sizes up to 10^9), this is comfortably fast — at most about 30 binary search iterations, each scanning all n piles.

The feasibility function canFinish(piles, h, k) computes the total hours Koko needs at speed k. For each pile, the hours needed is ceil(pile / k). Summing these up gives the total hours. If the total is at most h, speed k is feasible — Koko can finish in time. If the total exceeds h, speed k is too slow.

Ceiling division is the critical operation. For a pile of size 7 and speed k=3, Koko needs ceil(7/3) = 3 hours (3 bananas in hour 1, 3 in hour 2, 1 in hour 3). Python's math.ceil(pile/k) works correctly but introduces floating point. The preferred approach is integer ceiling division: (pile + k - 1) // k. This is exact, fast, and avoids any float imprecision for large pile sizes.

The feasibility check runs in O(n) time. Since it is called O(log(max_pile)) times during binary search, the overall complexity is O(n * log(max_pile)). The check short-circuits early if the running total exceeds h — once we know speed k is too slow, there is no need to continue summing the remaining piles. This optimization matters when h is small.

The binary search operates over the range [1, max(piles)]. Initialize lo = 1 and hi = max(piles). While lo < hi: compute mid = (lo + hi) // 2. If canFinish(mid) is true, set hi = mid (mid might be the answer, or something smaller might also work). If canFinish(mid) is false, set lo = mid + 1 (mid is too slow, so the answer must be strictly greater). When the loop exits, lo == hi and is the minimum valid speed.

This is the "leftmost true" binary search template. The invariant is: lo is always a candidate speed that might or might not be valid, and hi is always a speed that is known to be valid or will converge to the valid boundary. The midpoint is computed as (lo + hi) // 2 to avoid integer overflow (in Python this is not an issue, but in Java use lo + (hi - lo) / 2). The loop condition lo < hi ensures the loop terminates when the range collapses to one element.

Why hi = max(piles) and not max(piles) + 1? At speed k = max(piles), Koko finishes every pile in exactly one hour, so she finishes n piles in n hours. Since h >= n is guaranteed, this speed is always feasible. Therefore max(piles) is always a valid upper bound, and we never need to search beyond it.

Integer ceiling division is computed as (a + b - 1) // b for positive integers a and b. This is equivalent to math.ceil(a / b) but uses only integer arithmetic. For example, ceil(7 / 3) = (7 + 3 - 1) // 3 = 9 // 3 = 3. For ceil(9 / 3) = (9 + 3 - 1) // 3 = 11 // 3 = 3. For ceil(10 / 3) = (10 + 3 - 1) // 3 = 12 // 3 = 4. Always correct for positive integers.

Why avoid floating point? With pile sizes up to 10^9 and speed k = 1, the division pile/k = 1e9 is exact in floating point. But for pathological values — say pile = 10^15 (hypothetically) or accumulated sums — floating point rounding can produce off-by-one errors that cause incorrect feasibility decisions. Using integer arithmetic eliminates this risk entirely and is also slightly faster since it avoids the FPU.

In Python, the // operator performs floor division on integers, so (pile + k - 1) // k is always exact. In Java, the / operator on integers also performs floor division for positive values, so the same formula applies. Both Python's math.ceil(pile / k) and the integer formula are accepted by LeetCode, but the integer formula is more robust and preferred in production code.

Python solution: def minEatingSpeed(piles, h): lo, hi = 1, max(piles); while lo < hi: mid = (lo + hi) // 2; total = sum((pile + mid - 1) // mid for pile in piles); if total <= h: hi = mid; else: lo = mid + 1; return lo. The canFinish logic is inlined into the binary search for conciseness. Time: O(n * log(max_pile)), Space: O(1). Alternatively, use math.ceil: total = sum(math.ceil(pile / mid) for pile in piles).

Java 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; int total = 0; for (int p : piles) total += (p + mid - 1) / mid; if (total <= h) hi = mid; else lo = mid + 1; } return lo; } Same O(n * log(max_pile)) time, O(1) space. Java uses lo + (hi - lo) / 2 for mid to avoid integer overflow.

The helper function pattern separates concerns cleanly: private boolean canFinish(int[] piles, int h, int k) { int total = 0; for (int p : piles) { total += (p + k - 1) / k; if (total > h) return false; } return true; } This early-exit version is more efficient when the answer is a small speed and many piles would overflow h. For interview settings, inline is fine; for production code, the helper improves readability.

Capacity to Ship Packages Within D Days (LeetCode 1011) is a direct sibling of Koko Eating Bananas. Given package weights and d days, find the minimum ship capacity so all packages ship within d days. The feasibility check computes days needed at a given capacity — greedy packing, not ceiling division — but the binary search structure is identical: search [max(weights), sum(weights)], find leftmost feasible capacity.

Split Array Largest Sum (LeetCode 410) asks for the minimum possible largest sum when splitting an array into k subarrays. Binary search on the answer: search [max(nums), sum(nums)], feasibility checks whether the array can be split into at most k subarrays each with sum at most mid. Find Minimum in Rotated Sorted Array (LeetCode 153) is standard binary search, not binary search on answer, but reinforces the template.

The binary search on answer family includes LeetCode 875, 1011, 410, 1482, 774, and 1552. What unifies them is a monotonic predicate — some property that transitions from false to true (or true to false) as the answer increases, with no oscillation. Whenever you see "find minimum X such that condition Y holds," think binary search on answer. Identifying the search range and feasibility function is the entire challenge.