Sponsored
Sponsored
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.
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.
1var minEatingSpeed = function(piles, h) {
2 let left = 1, right = Math.max(...piles);
3 const canEatAll = (speed) => piles.reduce((hours, pile) => hours + Math.ceil(pile / speed), 0) <= h;
4
5 while (left < right) {
6 const mid = Math.floor((left + right) / 2);
7 if (canEatAll(mid)) right = mid;
8 else left = mid + 1;
9 }
10 return left;
11};The JavaScript implementation performs binary search to determine the minimal eating speed Koko requires, ensuring that it uses a helper function to calculate the summation of hours needed at a proposed speed.
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.
Time Complexity: O(N * M), where N is the number of piles and M is the largest pile size. Space Complexity: O(1).
1class Solution:
2 def minEatingSpeed(self, piles, h):
3The 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.