Koko Eating Bananas | Leetcode 875 | Binary Search on Answers

The “Koko Eating Bananas” problem is a popular binary search interview question that tests your ability to optimize under constraints.

In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

Problem Statement

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 some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

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

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Brute Force Solution (Try Every Possible Speed)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Speed:
   Try every possible eating speed from 1 up to the largest pile.
2. Calculate Total Hours:
   For each speed, calculate the total hours Koko would take to eat all bananas.
3. Return the First Valid Speed:
   The first speed for which total hours is less than or equal to h is our answer.
4. Why does this work?
   We check every possible speed, so we’re sure to find the minimum one that works.

This approach is easy to understand but not efficient for large piles or high values.

Code Implementation

import math
from typing import List

class Solution:
    def totalHours(self, piles, hourly_rate):
        total = 0
        for i in range(len(piles)):
            total = total + math.ceil(piles[i] / hourly_rate)  # Calculate hours for each pile
        return total

    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        maximum_banana = max(piles)             # The highest possible eating speed
        for i in range(1, maximum_banana + 1):  # Try every possible speed
            total_hour = self.totalHours(piles, i)
            if total_hour <= h:                 # If Koko can finish in h hours
                return i                        # Return this speed

Code Explanation

• For each speed from 1 to the maximum pile size, calculate total hours needed.
• If total hours is within h, return that speed.

Dry Run

Input:
piles = , h = 8

• Try k = 1: total hours = 3+6+7+11 = 27 (too high)
• Try k = 2: total hours = 2+3+4+6 = 15 (too high)
• Try k = 3: total hours = 1+2+3+4 = 10 (too high)
• Try k = 4: total hours = 1+2+2+3 = 8 (just right, return 4)

Final Output:
4

Time and Space Complexity

• Time Complexity: O(max(piles) * n)
  For each speed, we check all piles.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The brute force approach is simple and works for small inputs, but it’s too slow for large values.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search on Speed:
   The answer lies between 1 and the largest pile size. Use binary search to find the minimum speed.
2. Check if Speed is Enough:
   For each mid value, calculate if Koko can finish in h hours.
3. Adjust Search Window:
   • If she can finish, try a smaller speed.
   • If not, try a larger speed.
4. Why does this work?
   The total hours function is monotonic: as speed increases, hours decrease. Binary search is perfect for this.

Code Implementation

class Solution:
    def totalHours(self, piles, hourly_rate):
        total = 0
        for i in range(len(piles)):
            total = total + math.ceil(piles[i] / hourly_rate)  # Calculate hours for each pile
        return total

    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        low = 1
        high = max(piles)
        ans = -1
        while low <= high:
            mid = (low + high) // 2
            total_hours = self.totalHours(piles, mid)
            if total_hours <= h:
                ans = mid                  # Try to find a smaller valid speed
                high = mid - 1
            else:
                low = mid + 1              # Need a higher speed
        return ans

Code Explanation

• Use binary search between 1 and max pile size.
• For each mid speed, calculate total hours needed.
• If total hours is within h, store the speed and try smaller.
• If not, try higher speeds.
• Return the minimum valid speed found.

Dry Run

Input:
piles = , h = 8

• low = 1, high = 11
• mid = 6, total_hours = 1+1+2+2 = 6 (can finish, try smaller speed)
• high = 5
• mid = 3, total_hours = 1+2+3+4 = 10 (too slow, try faster)
• low = 4
• mid = 4, total_hours = 1+2+2+3 = 8 (just right, try even smaller)
• high = 3

Loop ends, answer is 4.

Time and Space Complexity

• Time Complexity: O(n * log(max(piles)))
  Binary search on speed, checking all piles for each guess.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The optimal solution is efficient and works well for large arrays and high values. It’s the best approach for interviews and practical use.

Final Thoughts

The “Koko Eating Bananas” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.