Algorithm

Koko Eating Bananas

Binary Search Pattern

Koko Eating Bananas

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses one pile of bananas and eats k bananas from that pile. If the pile has fewer than k bananas, she eats the whole pile. She cannot eat from another pile in the same hour. She wants to finish all the bananas within h hours. 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
EXAMPLE 2
Input: piles = [30,11,23,4,20], h = 5
Output: 30
5 piles, 5 hours — she must finish each pile in one hour, so speed must be at least the biggest pile.
EXAMPLE 3
Input: piles = [30,11,23,4,20], h = 6
Output: 23
If Koko finishes a pile before the hour is up, can she start the next pile in the same hour?
No. She eats from one pile per hour. Finishing early doesn't let her start another pile. Each pile takes ceil(pile / k) hours regardless.

Koko Eating Bananas is a brilliant "Evolution" of Binary Search. Most of the time, we use binary search to find a number in an existing array. Here, we use it to find a number in a range of possibilities that don't even exist yet.

The Answer Space Discovery

The problem asks for the "Minimum Eating Speed." Let's think about the boundaries of that speed:
- Absolute Slowest: 1 banana per hour.
- Absolute Fastest: The size of the largest pile. If Koko eats the largest pile in 1 hour, she is at her maximum efficiency because she can't eat another pile in the same hour anyway.

Discover: Even though we don't have an array of speeds, the "Answer Space" [1, Max_Pile] is naturally sorted! 1... 2... 3... 4... Max.

The Monotone Property

Does a pattern exist? Yes.
- If Koko is fast enough to finish at 5 bananas per hour, she is DEFINITELY fast enough to finish at 10.
- If she fails at 4 bananas per hour, she will DEFINITELY fail at 2.

This consistent "Success/Failure" transition is exactly what Binary Search needs to work. We pick a middle speed, simulate her eating journey, and fold the range based on whether she passed or failed the time limit.

Code Blueprint
text
left = 1
right = MAX(piles)
res = right

WHILE left <= right:
    mid = left + (right - left) / 2
    
    // Simulate the eating process (O(N))
    total_hours = 0
    FOR pile in piles:
        total_hours += CEIL(pile / mid)
        
    IF total_hours <= h:
        // Speed works! Save it and try to go even slower
        res = mid
        right = mid - 1
    ELSE:
        // Too slow! Must eat faster
        left = mid + 1

RETURN res
Why the Pattern is King

Koko Eating Bananas shifts Binary Search from a simple lookup tool into a powerful optimization strategy. Whenever you are asked for a "Minimum" or "Maximum" value in a predictable range, and checking a candidate value is easy, "Binary Search on Answer Space" is the optimal discovery path. It turns a massive search space into a few dozen quick simulations.

Interactive Strategy Visualization

Optimization via Search

Instead of trying every speed k, we use Binary Search on the range [1, max(piles)]. For each speed, we simulate the eating process and check if it's feasible.

4
bananas/h
⏱️
8 hours
Allowed Time
3
Pile 0
6
Pile 1
7
Pile 2
11
Pile 3
Total Time Used
--hours
Status
Waiting for Speed...

Adjust the speed k and press Play to see if Koko can finish all bananas in time.

O(Max_Pile * N) try every speed
→
O(N * log(Max_Pile)) binary search on answer space