LeetEye LeetEye
Medium Binary Search ~5 min

Koko Eating Bananas

binary-search koko-eating-bananas

Problem

Koko loves to eat bananas. There are n piles of bananas, the ith 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 of k. Each hour, she chooses a pile and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them and will not eat any more bananas during that hour.

Return the minimum integer k such that she can eat all the bananas within h hours.

Examples

Example 1
Input: piles = [3,6,7,11], h = 8
Output: 4
At k=4: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1+2+2+3 = 8 hours
Example 2
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Must eat one pile per hour (fastest possible).
Example 3
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Key Insight

Binary search on the answer (k), not on the input.

Binary search on answer: k in [1, max(piles)]. Check if sum(ceil(pile/k)) ≤ h. Find minimum valid k.

How to Approach This Problem

Pattern Recognition: When you see keywords like koko eating bananas binary-search, think Binary Search.

Step-by-Step Reasoning

1 We're binary searching for:
Answer: The eating speed k
We want to find the minimum k that allows finishing in h hours. k is a value we're searching for, not an index.
2 The minimum possible eating speed is:
Answer: 1
Must eat at least 1 banana per hour. k=0 means never eating.
3 The maximum useful eating speed is:
Answer: max(piles)
Eating faster than the largest pile gains nothing (can only eat one pile per hour anyway). At k = max(piles), each pile takes exactly 1 hour.
4 To eat a pile of size p at speed k, hours needed:
Answer: ceil(p / k)
If p=7, k=4: eat 4 first hour, 3 second hour = 2 hours = ceil(7/4).
5 Total hours at speed k:
Answer: sum(ceil(p/k) for each pile)
Each pile takes ceil(size/k) hours. Sum all piles' times.
6 If k hours > h (too slow):
Answer: Try larger k
Need to eat faster (larger k) to finish in fewer hours.

Solution

import math

def minEatingSpeed(piles: List[int], h: int) -> int:
    left, right = 1, max(piles)
    
    while left < right:
        mid = left + (right - left) // 2
        
        # Calculate hours needed at speed mid
        hours = sum(math.ceil(p / mid) for p in piles)
        
        if hours <= h:
            right = mid  # Can go slower
        else:
            left = mid + 1  # Need to go faster
    
    return left

Complexity Analysis

Time O(n * log(max(piles)))
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Binary Search problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye