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.
Since the constraint for hours is very large, a direct approach may not work efficiently. Instead, we can use binary search on the possible eating speeds (from 1 to the maximum value in the piles) to find the minimum speed at which Koko can eat all the bananas in the allotted time. For a given speed, compute the number of hours Koko would need to eat all the bananas.
The C solution uses a binary search to find the minimum eating speed. It first determines the maximum pile size, which sets the upper limit for the search range. A helper loop calculates the total number of hours needed if Koko eats at a particular speed, adjusting the search range based on whether the number of hours is within the allowed time.
Time Complexity: O(N log M), where N is the number of piles and M is the maximum number of bananas in a pile. Space Complexity: O(1), as the additional space used by the algorithm does not depend on input size.
In this approach, we iterate over every possible eating speed from 1 to the maximum pile size and check if Koko can finish eating all within h hours. Although inefficient for large inputs, it works correctly for smaller constraints but mainly serves as a fallback understanding of the problem dynamics.
The brute force Python solution iteratively checks each potential speed and calculates the total hours required with a direct loop comparison. It returns the first speed that allows completing all piles within the time limit.
Python
Time Complexity: O(N * M), where N is the number of piles and M is the largest pile size. Space Complexity: O(1).
We notice that if Koko can eat all the bananas at a speed of k within h hours, then she can also eat all the bananas at a speed of k' > k within h hours. This shows monotonicity, so we can use binary search to find the smallest k that satisfies the condition.
We define the left boundary of the binary search as l = 1, and the right boundary as r = max(piles). For each binary search, we take the middle value mid = \frac{l + r}{2}, and then calculate the time s required to eat bananas at a speed of mid. If s leq h, it means that the speed of mid can meet the condition, and we update the right boundary r to mid; otherwise, we update the left boundary l to mid + 1. Finally, when l = r, we find the smallest k that satisfies the condition.
The time complexity is O(n times log M), where n and M are the length and maximum value of the array piles respectively. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Binary Search on Eating Speed | Time Complexity: O(N log M), where N is the number of piles and M is the maximum number of bananas in a pile. Space Complexity: O(1), as the additional space used by the algorithm does not depend on input size. |
| Brute Force Method (Suboptimal) | Time Complexity: O(N * M), where N is the number of piles and M is the largest pile size. Space Complexity: O(1). |
| Binary Search | — |
| 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 |
BS-12. Koko Eating Bananas • take U forward • 414,729 views views
Watch 9 more video solutions →Practice Koko Eating Bananas with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor