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.
1import math
2class Solution:
3 def minEatingSpeed(self, piles, h):
4 def canEatAll(speed):
5 return sum(math.ceil(pile / speed) for pile in piles) <= h
6
7 left, right = 1, max(piles)
8 while left < right:
9 mid = (left + right) // 2
10 if canEatAll(mid):
11 right = mid
12 else:
13 left = mid + 1
14 return leftThe Python solution defines a helper function to check if Koko can eat all the bananas at a given speed. A binary search is implemented to minimize this speed, engaging the canEatAll function to verify within the loop.
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.