TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
- You want to return the minimum number of bananas eaten per hour subject to the number of hours before the police come.
- To do so, you can loop from 1 banana per hour to the maximum bananas per hour in any pile.
- This will TLE since there are 10 to the 9 bananas maximum within a given pile.
- Therefore, you can utilize Bisect Left to check:
- If the hours needed to eat all bananas from pile given the current bananas eaten per hour is more than the time allotted before the police come, then you need to increase your number of bananas (left = bananas eaten per hour + 1)
- On the other hand, if you have the same or less hours, then it it possible that you can eat even less bananas per hour. Therefore, find the minimum possible, so continue iterating until you find that it is not possible to get a smaller amount.
Complexity
Runtime
- , where N is the number of piles, and M is the maximum number of bananas in a given pile. You need to binary search through that space.
- if not using binary search, which TLE’s since you are searching to up to which is the maximum number of bananas in a given pile.
Space
Code
Second Try
from math import ceil
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
# k = number of bananas eaten per hour
# Return the minimum number of bananas
min_k, max_k = 1, max(piles) # Represents the range of possible k
def calculateEatRate(amountThatCanEat):
res = 0
for pile in piles:
res += ceil(pile / amountThatCanEat)
return res
def bisectLeft(left, right):
while left <= right:
mid = (left + right) // 2 # The k we are searching for
hoursToEatAllPilesGivenK = calculateEatRate(mid)
print('Number of bananas eaten per hour (k)', mid)
print('hours taken to eat bananas from all piles given k', hoursToEatAllPilesGivenK)
if hoursToEatAllPilesGivenK <= h: # Ate all the bananas with more hours left to spare, so we can potentially eat LESS bananas per hour
right = mid - 1 # Decrease the number of bananas we eat
else:
left = mid + 1 # Ate all the bananas but ran out of time, so we need to eat more per hour
return left
return bisectLeft(min_k, max_k)Using Math Wizardry
from math import ceil
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
# Return the number of hours needed to eat all bananas from every pile
def hoursNeededToEatAllBananasFromPile(bananas_eaten_per_hour):
return sum(ceil(bananas / bananas_eaten_per_hour) for bananas in piles)
minimum_banana_pile, maximum_banana_pile = min(piles), max(piles)
hours_before_police_come = h
# Bisect left
def minimumBananasEatenPerHourSubjectToHoursBeforePoliceCome(left, right):
while left < right:
bananas_eaten_per_hour = (left + right) // 2
hours_needed_to_eat_all_bananas_from_pile_given_bananas_eaten_per_hour = hoursNeededToEatAllBananasFromPile(bananas_eaten_per_hour)
if hours_needed_to_eat_all_bananas_from_pile_given_bananas_eaten_per_hour > hours_before_police_come:
left = bananas_eaten_per_hour + 1 # Then you need to eat more bananas per hour
else:
right = bananas_eaten_per_hour # Check if there are less bananas to eat
return left
return minimumBananasEatenPerHourSubjectToHoursBeforePoliceCome(1, maximum_banana_pile)Using Bisect Left
from math import ceil
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
# Return the number of hours needed to eat all bananas from every pile
def hoursNeededToEatAllBananasFromPile(bananas_eaten_per_hour):
hours_needed_to_eat_all_bananas_from_all_piles = 0
for bananas_left_in_pile in piles:
# If you can eat more bananas than is in the pile in an hour, then it just takes one hour
hours_needed_to_eat_bananas_from_current_pile = 1
# Only if there are more bananas than the amount you can eat per hour
if bananas_left_in_pile > bananas_eaten_per_hour:
hours_needed_to_eat_bananas_from_current_pile = ceil(bananas_left_in_pile / bananas_eaten_per_hour)
hours_needed_to_eat_all_bananas_from_all_piles += hours_needed_to_eat_bananas_from_current_pile
return hours_needed_to_eat_all_bananas_from_all_piles
minimum_banana_pile, maximum_banana_pile = min(piles), max(piles)
hours_before_police_come = h
# Bisect left
def minimumBananasEatenPerHourSubjectToHoursBeforePoliceCome(left, right):
while left < right:
bananas_eaten_per_hour = (left + right) // 2
hours_needed_to_eat_all_bananas_from_pile_given_bananas_eaten_per_hour = hoursNeededToEatAllBananasFromPile(bananas_eaten_per_hour)
if hours_needed_to_eat_all_bananas_from_pile_given_bananas_eaten_per_hour > hours_before_police_come:
left = bananas_eaten_per_hour + 1 # Then you need to eat more bananas per hour
else:
right = bananas_eaten_per_hour # Check if there are less bananas to eat
return left
return minimumBananasEatenPerHourSubjectToHoursBeforePoliceCome(1, maximum_banana_pile)Using Linear Search (TLE)
Would be same as the Bisect Left approach, but ranging from 1 to the maximum number:
minimum_banana_pile, maximum_banana_pile = min(piles), max(piles)
#[minimum_banana_pile, maximum_banana_pile]
for bananas_eaten_per_hour in range(1, maximum_banana_pile):
if hoursNeededToEatAllBananasFromPile(bananas_eaten_per_hour) <= hours_before_police_come:
return bananas_eaten_per_hourNotes
Cards
START Basic Front: Koko Eating Bananas - LeetCode Back: Use Bisect Left to get the minimum possible bananas eaten per hour.
END