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] <= 109Since 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.
C++
Java
Python
C#
JavaScript
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.
Time Complexity: O(N * M), where N is the number of piles and M is the largest pile size. Space Complexity: 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). |
Koko Eating Bananas - Binary Search - Leetcode 875 - Python • NeetCode • 263,635 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