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