LeetCode 875 Explained: Koko Eating Bananas Using Binary Search on Answer (Python)

LeetCode 875: Koko Eating Bananas – Binary Search on Answer Explained

LeetCode 875, Koko Eating Bananas, is a classic problem that looks simple at first glance but introduces a powerful and reusable concept: Binary Search on the Answer. In this article, we’ll break down the intuition, approach, and final Python solution step by step.

👉 Full source code is available here: GitHub – LeetCode 875 Solution

---

🧠 Problem Overview

Koko loves bananas and has h hours to eat all the bananas from multiple piles. She can choose a speed k (bananas per hour) and eats from only one pile per hour. The goal is to find the minimum eating speed that allows her to finish within h hours.

❌ Why Brute Force Fails

A naive approach would be to try every possible eating speed from 1 to max(piles) and check if Koko can finish on time. However, this leads to an inefficient solution with very high time complexity.

💡 Key Insight: Binary Search on the Result

Instead of searching inside the array, we apply binary search on the answer space. The possible eating speeds lie in a fixed range:

• Minimum speed: 1 banana/hour
• Maximum speed: max value in piles

If Koko can finish eating all bananas at a certain speed k, then she can also finish at any speed greater than k. This monotonic behavior makes binary search possible.

✅ Feasibility Check Function

For a given speed, we calculate the total hours required to eat all piles. If the total hours are less than or equal to h, the speed is valid.

def caneat(self, piles, mid, h):
    total_time = 0
    for i in piles:
        total_time += i // mid
        if i % mid != 0:
            total_time += 1
    return total_time <= h

    

🔍 Binary Search Implementation

We use binary search to minimize the eating speed while keeping it valid.

def minEatingSpeed(self, piles: List[int], h: int) -> int:
    l = 1
    r = max(piles)

    while l < r:
        mid = (l + r) // 2
        if self.caneat(piles, mid, h):
            r = mid
        else:
            l = mid + 1

    return l

    

⏱️ Time & Space Complexity

• Time Complexity: O(n log(max(piles)))
• Space Complexity: O(1)

The binary search reduces the answer space logarithmically, and each feasibility check scans the piles once.

📌 Final Takeaway

This problem teaches a powerful lesson: when the problem asks for a minimum or maximum value and the feasibility behaves monotonically, always consider Binary Search on Answer. Once this pattern clicks, many difficult problems become straightforward.

🔗 Complete solution: View on GitHub