Koko Eating Bananas — Binary Search on Answer Space [LC 875, Google]

Problem Statement#

LeetCode 875 — Koko Eating Bananas · Difficulty: Medium

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 k. Each hour, she chooses one pile and eats k bananas from it. If the pile has fewer than k bananas, she eats all of them and will not eat from another pile during that 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

Example 1:

Input:  piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation: At speed 4 — hours needed: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4)
             = 1+2+2+3 = 8 hours. Speed 3 would need 9 hours (too slow).

Example 2:

Input:  piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Explanation: With 5 piles and exactly 5 hours, each pile needs its own hour.
             Minimum speed = max pile = 30.

Example 3:

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

Why This Problem Matters#

LC 875 is the canonical example of binary search on the answer space — a technique that unlocks an entire class of optimization problems that look nothing like array search on the surface. Google uses it frequently in interviews to test whether candidates know that binary search is not limited to searching arrays; it can search any monotone predicate over a range of values.

The structure here is: you have a decision variable k (speed), a feasibility function canFinish(k) that returns true if speed k is sufficient, and the property that canFinish is monotone: if speed k works, then speed k+1 also works. Any time a problem has this structure — "find the minimum (or maximum) value satisfying a monotone condition" — binary search on the answer is applicable.

This pattern solves LC 1011 (ship packages), LC 1482 (minimum days to make bouquets), LC 410 (split array largest sum), LC 875 (this), and many more. Mastering the template here gives you a skeleton for all of them.

The Core Insight#

The key observation: the total hours required to eat all bananas is a decreasing function of speed. Faster speed → fewer hours. This monotonicity is what makes binary search applicable.

The answer k lives in the range [1, max(piles)]:

• Minimum possible speed is 1 (at least eat one banana per hour).
• Maximum useful speed is max(piles) — eating faster than the largest pile never saves time because you still spend one full hour per pile.

For a given candidate speed mid, compute total hours as sum(ceil(pile / mid)) for each pile. Using integer arithmetic: ceil(pile / mid) = (pile + mid - 1) // mid.

If total hours <= h: speed mid is feasible — try going slower (search left). If total hours > h: speed mid is too slow — must go faster (search right).

Binary search finds the leftmost feasible speed.

Visual Dry Run#

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

Answer range: lo = 1, hi = 11 (max pile).

Step 4 detail: ceil(3/4)=1, ceil(6/4)=2, ceil(7/4)=2, ceil(11/4)=3 → sum = 8. Exactly h, so feasible. Step 2 detail: ceil(3/3)=1, ceil(6/3)=2, ceil(7/3)=3, ceil(11/3)=4 → sum = 10 > 8. Too slow.

Common Mistakes#

1. Setting hi = sum(piles) instead of hi = max(piles). The maximum useful speed is max(piles), not the sum. At speed max(piles), the largest pile takes exactly one hour. Going faster wastes computation and can cause overflow when piles contain large values.

2. Using integer division / instead of ceiling division. pile // mid rounds down, which undercounts the hours needed. Koko cannot eat a fraction of an hour — she must spend a full hour on any partial pile. Always use ceil(pile / mid) or equivalently (pile + mid - 1) // mid.

3. Getting the binary search bounds wrong for "find minimum feasible". The template is: when feasible, hi = mid; when not feasible, lo = mid + 1. Use while lo < hi as the loop condition. The loop exits with lo == hi == answer. Mixing hi = mid - 1 with this template will skip the minimum feasible value.

4. Overflow when summing hours. With piles[i] up to 10^9 and k = 1, each pile contributes up to 10^9 hours. With 10^4 piles, total hours can reach 10^13 — which overflows a 32-bit integer. In JavaScript, use Math.ceil with standard numbers (JavaScript uses 64-bit floats, safe up to 2^53). In Java/C++, accumulate in a long.

5. Not checking h >= len(piles). The constraint guarantees piles.length <= h, so Koko always has at least one hour per pile. But if you write this from scratch without reading constraints, missing this check leads to wrong boundary initialization.

6. Confusing "minimize speed" with "maximize speed". This problem asks for the minimum speed that is feasible. The binary search template for "find minimum feasible" moves hi = mid when feasible (shrink from the right). The template for "find maximum feasible" moves lo = mid when feasible (shrink from the left). Confusing them gives the maximum rather than the minimum.

Solutions#

Python#

import math
 
def minEatingSpeed(piles: list[int], h: int) -> int:
    lo = 1                  # minimum possible speed (eat at least 1 banana/hour)
    hi = max(piles)         # maximum useful speed (no benefit beyond largest pile)
 
    # Binary search for the LEFTMOST (minimum) feasible speed.
    # Invariant: lo is always a feasible speed or higher; hi may not be feasible.
    while lo < hi:           # exit when lo == hi — the answer
        mid = lo + (hi - lo) // 2   # safe midpoint
 
        # Compute total hours needed at speed `mid`.
        # ceil(pile / mid) using integer arithmetic: (pile + mid - 1) // mid
        total_hours = sum(math.ceil(p / mid) for p in piles)
 
        if total_hours <= h:
            # Speed `mid` is feasible — it finishes within h hours.
            # Try a smaller speed: move hi down to mid (keep mid as candidate).
            hi = mid
        else:
            # Speed `mid` is too slow — needs more than h hours.
            # Must go faster: move lo up past mid.
            lo = mid + 1
 
    # lo == hi — this is the minimum feasible speed
    return lo

JavaScript#

function minEatingSpeed(piles, h) {
    let lo = 1;                          // minimum speed
    let hi = Math.max(...piles);         // maximum useful speed
 
    // Binary search: find the leftmost speed where total hours <= h
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2); // safe midpoint
 
        // Calculate total hours needed at speed `mid`.
        // Use Math.ceil to round up — partial piles still cost a full hour.
        let totalHours = 0;
        for (const pile of piles) {
            totalHours += Math.ceil(pile / mid);     // ceil division
        }
 
        if (totalHours <= h) {
            // Feasible: can finish within h hours at this speed.
            // Try slower by moving hi down (keep mid as a candidate answer).
            hi = mid;
        } else {
            // Too slow: needs more than h hours.
            // Must eat faster — move lo up past mid.
            lo = mid + 1;
        }
    }
 
    // lo == hi is the minimum speed that finishes within h hours
    return lo;
}

Complexity Analysis#

n is the number of piles (up to 10^4) and M is the maximum pile size (up to 10^9). The binary search makes O(log M) iterations, and each iteration evaluates all n piles. Total: O(n log M). For n = 10^4 and M = 10^9, this is about 10^4 * 30 = 300,000 operations — very fast. Space is O(1).

Follow-up Questions#

Q: What if h < len(piles)? Impossible — at minimum one pile per hour, so h >= len(piles). The problem constraints guarantee this.

Q: What if multiple piles have the same maximum value? No impact. hi = max(piles) is still correct. The binary search finds the minimum feasible speed regardless of pile distribution.

Q: How does this generalize? Any problem of the form "find the minimum value x in range [lo, hi] such that feasible(x) is true, where feasible is monotone non-decreasing" uses this exact template. Identify the search space bounds, write the feasibility check, and plug into the while lo < hi loop.

Q: Can you use (pile + mid - 1) // mid instead of math.ceil? Yes — (pile + mid - 1) // mid is integer ceiling division and avoids floating-point. In Python both are fine; in Java/C++ the integer form is preferred to avoid floating-point errors.

This Pattern Solves#

• LC 875 — Koko Eating Bananas (this problem)
• LC 1011 — Capacity to Ship Packages Within D Days
• LC 1482 — Minimum Number of Days to Make Bouquets
• LC 410 — Split Array Largest Sum
• LC 2064 — Minimized Maximum of Products Distributed to Any Store
• Any "minimize X such that condition(X) is achievable" problem with a monotone feasibility function

Key Takeaway#

When a problem asks for the minimum value satisfying a monotone condition, binary search over the answer space. Identify bounds [lo, hi], write a feasible(mid) check, and use the template: if feasible(mid): hi = mid else: lo = mid + 1, with while lo < hi. The loop exits with lo == hi == minimum feasible value. For Koko specifically: the search space is [1, max(piles)] and feasibility checks sum(ceil(pile/k)) <= h. This template — not the array-search template — is what you reach for whenever the problem says "minimum" or "maximum" and the answer lies on a monotone curve.

Key Takeaways#

• LC 875 (Koko Eating Bananas) is the canonical binary search on answer problem, asked by Google and Amazon to test whether candidates apply binary search beyond sorted arrays.
• The search space is the set of possible speeds [1, max(piles)] — not the array elements — and feasibility is monotone: higher speed always means fewer or equal hours needed.
• Write a feasible(k) check: compute sum(ceil(pile / k) for pile in piles) and compare to h. If feasible, try slower; if not, go faster.
• Use while lo < hi with hi = mid on success and lo = mid + 1 on failure to converge on the minimum feasible speed.
• Ceiling division can be written as (pile + k - 1) // k in integer arithmetic — avoid floating-point to prevent rounding errors.
• Time complexity is O(n log M) where M = max(piles): at most log(10^9) ≈ 30 binary search iterations, each scanning n piles.
• This same template solves LC 1011 (ship packages), LC 1482 (bouquets), LC 410 (split array), and all "minimize X satisfying condition" problems.