binary search
August 1, 2022
Koko eating bananas
Space
O(1)
Open original problem
We will search through each position of the piles till the largest pile, where it allows us to eat all the bananas within given h hours. We can do it in brute force, but if we search with binary search, we can reduce the time complexity in logarithmic time.
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
k = 0
while l <= r:
m = (l+r) // 2
time = 0
for p in piles:
time += ((p - 1) // m) + 1
if time <= h:
k = m
r = m - 1
else:
l = m + 1
return k
Time Complexity: O(p * log(max(p))), where p is the piles array length.
Space Complexity: O(1)