Watch 10 video solutions for Koko Eating Bananas, a medium level problem involving Array, Binary Search. This walkthrough by take U forward has 414,729 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104piles.length <= h <= 1091 <= piles[i] <= 109Problem Overview: You are given an array piles where each element represents bananas in a pile. Koko can choose a constant eating speed k bananas per hour and must finish all piles within h hours. The task is to compute the minimum integer k that allows her to finish on time.
Approach 1: Brute Force Method (O(n * max(pile)) time, O(1) space)
This approach directly simulates every possible eating speed from 1 up to max(piles). For each speed k, iterate through the array and compute the hours required for each pile using ceil(pile / k). Sum the hours and check if the total is less than or equal to h. The first speed that satisfies the constraint is the answer. While the logic is simple and demonstrates the relationship between speed and total hours, the search space can be extremely large when pile sizes are big. The algorithm repeatedly scans the array for every possible speed, leading to poor performance on large inputs.
Approach 2: Binary Search on Eating Speed (O(n log m) time, O(1) space)
The key observation is that the required hours decrease as the eating speed increases. If Koko eats faster, she always finishes in fewer or equal hours. This monotonic behavior allows you to apply binary search on the answer space. Instead of checking every speed, search between 1 and max(piles). Pick a midpoint speed mid, compute total hours needed by iterating through the piles and summing ceil(pile / mid). If the required hours exceed h, the speed is too slow so move the left boundary up. Otherwise the speed works, and you try smaller speeds by moving the right boundary down.
Each feasibility check scans the array once, giving O(n) work per step. Since binary search reduces the candidate range logarithmically, the overall complexity becomes O(n log m) where m is the maximum pile size. This pattern is commonly called binary search on the answer. The problem does not require additional data structures beyond basic iteration over the array, and the space usage stays constant.
Recommended for interviews: The expected solution is the binary search approach. Interviewers want to see if you recognize monotonic conditions that allow searching over the answer space. Mentioning the brute force approach first shows you understand the problem constraints, but implementing the binary search optimization demonstrates stronger algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Speed Check | O(n * m) | O(1) | Conceptual understanding or very small pile values |
| Binary Search on Eating Speed | O(n log m) | O(1) | Optimal solution for large inputs and interview settings |