Koko Eating Bananas: Binary Search on the Answer

Koko Eating Bananas is LeetCode 875, and it is one of the best problems for learning binary search on the answer space. You are not searching through an array for a target. You are searching through all possible eating speeds to find the smallest one that works. Once you see this pattern, an entire class of "minimize the maximum" and "find the minimum valid X" problems opens up.

If you have worked through the binary search pattern, you already know the template. Koko Eating Bananas is the classic application of the "search on the answer" variant described there.

The problem

There are n piles of bananas. Pile i has piles[i] bananas. Koko can eat at speed k bananas per hour. Each hour, she picks one pile and eats k bananas from it. If the pile has fewer than k bananas, she eats the whole pile and waits out the rest of the hour (she cannot start another pile in the same hour).

Given h hours before the guards return, find the minimum integer k such that Koko can eat all the bananas within h hours.

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

At speed k = 4, Koko needs ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8 hours. That is exactly 8, so it works. Anything slower (like k = 3) takes 10 hours and fails. So k = 4 is the answer.

The brute force approach

You could try every possible speed from 1 up to max(piles). For each speed, compute the total hours. Return the first speed that fits within h.

def min_eating_speed_brute(piles, h):
    for k in range(1, max(piles) + 1):
        total = sum((p + k - 1) // k for p in piles)
        if total <= h:
            return k

This works, but it is O(max(piles) * n). If the largest pile is a billion bananas, you are checking a billion speeds. That is way too slow.

The key insight: monotonic feasibility

Here is the observation that makes binary search work. If Koko can finish at speed k, she can definitely finish at speed k + 1, and k + 2, and any faster speed. If she cannot finish at speed k, she also cannot finish at k - 1 or anything slower.

That is a monotonic condition. The answer space [1, max(piles)] splits neatly into two regions:

• Infeasible: speeds 1 through answer - 1 (too slow, takes more than h hours)
• Feasible: speeds answer through max(piles) (fast enough, takes h hours or fewer)

When you have a monotonic condition over a range, binary search finds the boundary in O(log n) time.

The feasibility check

Before writing the binary search, you need a function that answers: "Can Koko eat all the bananas at speed k within h hours?"

def can_finish(piles, k, h):
    hours = 0
    for p in piles:
        hours += (p + k - 1) // k  # same as math.ceil(p / k)
    return hours <= h

For each pile, ceil(p / k) gives the hours Koko spends on it. Sum them up. If the total is at most h, the speed is feasible. This runs in O(n) time.

The expression (p + k - 1) // k is the integer ceiling division trick. It avoids floating-point math and is the standard way to compute ceil(p / k) with integers.

Visual walkthrough

Let's binary search for the minimum valid k with piles = [3, 6, 7, 11] and h = 8. The search range is [1, 11].

Five steps. Instead of checking all 11 possible speeds, we checked 4 and found the answer. With larger ranges (say, up to a billion), binary search still takes at most about 30 steps. That is the power of O(log n).

The code

Here is the complete Python solution for LeetCode 875, koko eating bananas:

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = sum((p + mid - 1) // mid for p in piles)

        if hours <= h:
            hi = mid
        else:
            lo = mid + 1

    return lo

Let's walk through the important decisions.

lo = 1, hi = max(piles). The minimum possible speed is 1 (eat one banana per hour). The maximum useful speed is max(piles), because eating faster than the biggest pile does not save any time (she still spends one hour on each pile at that point).

while lo < hi, not while lo <= hi. We are narrowing down to a single answer. When lo == hi, that is our answer.

if hours <= h: hi = mid. If the current speed works, it might be the answer, or a slower speed might also work. So we keep mid in the range and search left.

else: lo = mid + 1. If the current speed does not work, we need something strictly faster. So we move lo past mid.

Return lo. When the loop ends, lo == hi and that is the minimum feasible speed.

Complexity analysis

Time: O(n * log(max(piles))). The binary search runs O(log(max(piles))) iterations. Each iteration computes the feasibility check in O(n) time by looping through all piles.

Space: O(1). Just a few variables. No extra data structures.

For the constraints in LeetCode 875 (piles[i] up to 10^9, n up to 10^4), this is about 30 * 10,000 = 300,000 operations. Very fast.

Edge cases to watch for

• Single pile: piles = [10], h = 5. Answer is ceil(10/5) = 2. The binary search handles this naturally.
• h == n (one hour per pile): Koko must eat each pile in one hour, so k = max(piles).
• h is very large: Koko has plenty of time, so even k = 1 works.
• All piles equal: piles = [5, 5, 5, 5], h = 4. She needs to eat each pile in one hour, so k = 5.

The building blocks

This problem is built on one core building block: binary-search-on-answer.

The skeleton is the standard binary search template, but instead of searching a sorted array for a target, you are searching a range of candidate answers for the smallest one that satisfies a condition.

# Standard binary search (find target in array):
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1

# Binary search on answer (find min valid k):
while lo < hi:
    mid = lo + (hi - lo) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

The structural similarity is clear. The only real difference is what you do at mid: instead of comparing a value, you call a feasibility function. If you can write the binary search template from memory and you know how to write the feasibility check, Koko Eating Bananas is just plugging the two together.

This same binary-search-on-answer pattern shows up in several related problems:

• Split Array Largest Sum (LeetCode 410): binary search on the maximum subarray sum
• Capacity to Ship Packages Within D Days (LeetCode 1011): binary search on ship capacity
• Minimum Number of Days to Make M Bouquets (LeetCode 1482): binary search on the number of days

In every case, the structure is identical: define the range, write the feasibility check, binary search.

From understanding to recall

The logic is clean. Binary search the speed range, check feasibility at each midpoint, narrow down to the smallest valid speed. You probably get it right now.

But try writing it cold in an interview three weeks from now. Was it lo < hi or lo <= hi? Do you set hi = mid or hi = mid - 1? What are the initial bounds? These small details are exactly the kind of thing that slips under pressure.

Spaced repetition is designed for this. You type the solution from scratch today, then again tomorrow, then in three days. After a few rounds, the while lo < hi and hi = mid pattern is muscle memory. You do not have to rederive it. You just write it.

LeetCode 875 is a perfect SRS candidate because the code is short (about 8 lines), the pattern is reusable across many problems, and the boundary conditions are easy to get wrong if you have not drilled them.

Related posts

• Binary Search: More Than Finding a Number - The full binary search pattern guide, including the search-on-answer variant that Koko Eating Bananas is built on
• Find Minimum in Rotated Sorted Array - Another binary search variant where the comparison logic changes but the template stays the same