LeetCode · #875

Koko Eating Bananas Solution

Find the minimum eating speed k such that Koko can eat all bananas within h hours.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #875

🏗️

Pattern

Binary Search — search on answer

There are n piles of bananas with piles[i] bananas each. Guards return in h hours. Koko eats at speed k bananas/hour. Each hour she picks a pile and eats k bananas (if fewer remain, she eats them all and waits). Find the minimum integer k such that she can eat all bananas within h hours.

Example

 Input: piles = [3,6,7,11], h = 8 Output: 4 // At speed 4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 ≤ 8 ✓ // At speed 3: 1+2+3+4 = 10 > 8 ✗ 

Constraints

 • 1 ≤ piles.length ≤ 10⁴ • piles.length ≤ h ≤ 10⁹ • 1 ≤ piles[i] ≤ 10⁹ 

Section Two · Approach 1

Brute Force — O(n · max)

Try every speed from 1 upward. For each speed, compute total hours needed. Return the first speed that works.

Problem: max(piles) can be 10⁹. Testing each speed linearly is far too slow. The answer space [1, max(piles)] is monotonic — if speed k works, all speeds > k also work. Binary search on this monotonic space gives O(n log max).

Metric	Value
Time	O(n · max(piles))
Space	O(1)

Section Three · Approach 2

Binary Search on Answer — O(n log max)

Binary search the speed k in range [1, max(piles)]. For each candidate speed, compute total hours = Σ ceil(piles[i] / k). If total ≤ h, try a smaller speed (go left). Otherwise, try a larger speed (go right).

💡 Mental model: Imagine turning a speed dial from 1 to max. At some threshold, the total time drops from "too slow" to "fast enough." You're binary searching for that threshold — the minimum dial setting where Koko finishes on time.

Algorithm

Step 1: left = 1, right = max(piles).
Step 2: Compute mid = (left + right) / 2.
Step 3: Compute total hours at speed mid: Σ ceil(piles[i] / mid).
Step 4: If total ≤ h → speed might be too high (or just right), try lower: right = mid.
Step 5: If total > h → speed too slow: left = mid + 1.
Step 6: Return left.

🎯 "Search on answer" pattern:

When the problem asks for the minimum/maximum value that satisfies a condition, and you can write a feasibility check function, binary search the answer space.
The check must be monotonic: if speed k works, all k' > k also work.
This pattern appears in LC 875, LC 1011 (Ship Within D Days), LC 410 (Split Array Largest Sum), and LC 774 (Minimize Max Distance to Gas Station).

Ceiling division without float:

ceil(a / b) = (a + b - 1) / b using integer arithmetic. Avoids floating-point precision issues.
In Python you can also use -(-a // b).

Section Four · Trace

Visual Walkthrough

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

Binary Search on speed — feasibility check at each mid

Section Five · Implementation

Code — Java & Python

Java — Binary Search on Answer

 class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
for (int p : piles) right = Math.max(right, p);
while (left < right) {
int mid = left + (right - left) / 2;
long hours = 0;
for (int p : piles)
                hours += (p + mid - 1) / mid; // ceil division if (hours <= h)
                right = mid; // feasible — try smaller else
left = mid + 1; // too slow — need faster
}
return left;
    }
}

Python — Binary Search on Answer

 import math
class Solution:
def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left, right = 1, max(piles)
while left < right:
            mid = (left + right) // 2
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h:
                right = mid # feasible — try smaller else:
                left = mid + 1 # too slow return left

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n · max)	O(1)	Try every speed linearly
Binary Search on Answer ← optimal	O(n · log(max))	O(1)	log(max) candidates × O(n) feasibility check

Where max = max(piles): log₂(10⁹) ≈ 30. So we do at most 30 × n operations — very fast even for n = 10⁴.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
h == n	`[3,6,7,11], h=4`	Exactly one hour per pile → k = max(piles) = 11.
h very large	`[3,6,7,11], h=10⁹`	k=1 works — plenty of time. Binary search converges to 1.
Single pile	`[30], h=5`	Need ceil(30/k) ≤ 5 → k ≥ 6.
All piles size 1	`[1,1,1], h=3`	k=1 → 3 hours exactly. Minimum speed.
Integer overflow	Large piles, small k	Sum of hours can exceed int range. Use `long` in Java.

⚠ Common Mistake: Using left ≤ right instead of left < right. This is a "find minimum feasible" search — the answer converges when L==R. With ≤ and right = mid, the loop never terminates when L==R.

← Back to Binary Search problems

LearningTree

LC 875 · Koko Eating Bananas — Solution & Explanation | DSA Guide