Back to main article
LC 875 Search on Answer Medium

Koko Eating Bananas

The gateway to binary search on answer. The array doesn't contain the answer — the answer is a speed you binary search across all possible values.

Problem

What are we solving?

Problem Statement

Koko loves eating bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards will return in h hours. Koko can eat at most k bananas per hour. She eats one pile per hour and moves to the next. Return the minimum integer k such that she can eat all the bananas within h hours.

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

The answer is a speed, not an index

The key shift: we're not searching an array for a target. We're searching the space of possible speeds (1 to max(piles)) for the minimum speed that works. This is Binary Search on Answer.

→

Want to build this from first principles? Read the deeper intuition article for the brute-force solution, complexity breakdown, and the exact optimization leap to binary search.

If speed k works, speed k+1 also works. If speed k fails, speed k-1 also fails. This monotonic property is exactly what binary search needs.

piles=[3,6,7,11], h=8 · Search space: speed 1..11
condition: canEatAll(speed, h) — hours needed ≤ h?
k=1F
k=2F
k=3F
k=4T*
k=5T
k=6T
k=7T
k=8T
k=9T
k=10T
k=11T
At k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 hours. Fits exactly!

The feasibility check

For each pile, Koko needs ceil(pile / speed) hours. Sum all piles and check if total ≤ h. In code: (pile + speed - 1) / speed avoids floating point.

→

Search bounds: Minimum speed = 1 (always valid as a lower bound). Maximum speed = max(piles) — no point going faster since she can finish the biggest pile in 1 hour.

Solution

Binary search on speed

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int p : piles) right = Math.max(right, p);
        int boundary = right;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canEat(piles, mid, h)) {
                boundary = mid;       // works — try slower
                right = mid - 1;
            } else {
                left = mid + 1;       // too slow — try faster
            }
        }
        return boundary;
    }

    private boolean canEat(int[] piles, int speed, int h) {
        int hours = 0;
        for (int pile : piles)
            hours += (pile + speed - 1) / speed; // ceiling division
        return hours <= h;
    }
}
import math

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left, right = 1, max(piles)
        boundary = right

        while left <= right:
            mid = left + (right - left) // 2
            if self.can_eat(piles, mid, h):
                boundary = mid
                right = mid - 1
            else:
                left = mid + 1
        return boundary

    def can_eat(self, piles, speed, h):
        return sum(math.ceil(p / speed) for p in piles) <= h

Complexity

Time
O(n log m)
log m iterations (m = max pile), each scanning n piles.
Space
O(1)
No extra structures beyond loop variables.
↑ Pattern map