Koko Eating Bananas 🍌

Meet Koko, the banana-loving gorilla 🦍.

She’s not your average primate — she’s got a deadline. Her jungle bedtime alarm goes off in exactly H hours, and in front of her is a mountain of banana piles. Each pile has a different number of bananas, and each hour, Koko picks one pile and eats at a constant speed of K bananas per hour.

Now, if the pile has fewer than K bananas, no problem — she eats the whole pile in an hour. Koko doesn’t do fractions or leftovers.

The challenge?

What is the minimum integer speed K such that Koko can eat all the bananas in H hours?

Let’s peel this problem open 🍌

🧾 Problem Statement

You're given:

An integer array piles, where piles[i] represents the number of bananas in the i-th pile.

An integer h — the number of hours before bedtime.

Your task:

Return the minimum integer speed K such that Koko can eat all the bananas within h hours.

🎯 Intuition — Banana Buffet Optimization

This is a classic case of Binary Search on the Answer — where the "answer" is the smallest possible value of K.

Why binary search?

• If Koko eats too slowly, she won’t finish all the bananas in time.
• If she eats super fast, she’ll definitely finish, but we might not be using the minimum possible speed.

So, we want the smallest K for which the total time taken to finish all piles is ≤ h.

🔍 Strategy

1. Define the Search Space:

• Left boundary: 1 (the slowest possible speed)
• Right boundary: max value in piles (the fastest she’d ever need to eat — gobbling up the biggest pile in an hour)

2. Check a Candidate Speed K:

For each pile, the time needed to eat it is:

time = ceil(pile / K)

We sum this across all piles. If the total time is:

• More than h → K is too small
• Within h → K might be valid; let’s try slower

Repeat this with binary search until we find the minimum working K.

🧪 Dry Run Example

Let’s say:

piles = [3, 6, 7, 11]

h = 8

Let’s apply binary search:

1. Left = 1, Right = 11 (max pile)

First Iteration:

• Mid = (1 + 11) / 2 = 6
• Compute hours:

🔹3/6 = 1

🔹6/6 = 1

🔹7/6 = 2

🔹11/6 = 2

• Total = 6 hours → Valid ✅

🔹Let’s try smaller K. Update: right = 6

Second Iteration:

• Mid = (1 + 6) / 2 = 3
• Hours:

🔹3/3 = 1

🔹6/3 = 2

🔹7/3 = 3

🔹11/3 = 4

• Total = 10 hours → Too much ❌

🔹Increase speed: left = 4

Third Iteration:

• Mid = (4 + 6) / 2 = 5
• Hours:

🔹3/5 = 1

🔹6/5 = 2

🔹7/5 = 2

🔹11/5 = 3

• Total = 8 hours → Valid ✅

🔹Try smaller: right = 5

Fourth Iteration:

• Mid = (4 + 5) / 2 = 4
• Hours:

🔹3/4 = 1

🔹6/4 = 2

🔹7/4 = 2

🔹11/4 = 3

• Total = 8 hours → Valid ✅

🔹Try smaller: right = 4

Now left == right == 4, so the answer is K = 4.

💻 Code Implementation (Java)

class Solution {

public int minEatingSpeed(int[] piles, int h) {

int left = 1;

int right = Arrays.stream(piles).max().getAsInt();

while (left < right) {

int mid = left + (right - left) / 2;

int hours = 0;

for (int pile : piles) {

hours += (pile + mid - 1) / mid; // Same as ceil(pile / mid)

}

if (hours > h) {

left = mid + 1;

} else {

right = mid;

}

}

return left;

}

}

⏰ Time & Space Complexity

Time: O(n * log m)

• n = number of piles
• m = max value in piles (range of speed)

Space: O(1)

• No extra space used

📦 Key Takeaways

✅ Binary Search on Answer is useful when you're trying to find the minimum or maximum value that satisfies a condition — even if the input array isn't sorted.

✅ Convert the problem into a yes/no question:

“Can Koko finish all bananas at speed K in h hours?”

✅ Use a greedy approach to check if a speed works:

Calculate how many hours Koko would take at a given speed, and adjust the speed accordingly.

✅ For ceil division without using floating-point math:

(pile + k - 1) / k // equivalent to ceil(pile / k)