Koko Eating Bananas
- 2 min read
- LC-Medium
- Binary-search
3 years ago
Solution
- The maximum value of k is equal to the maximum number in the piles array.
- This is because the fastest Koko can eat all the bananas in a pile is in 1 hour- which means, she needs to eat exactly piles[i] bananas per hour to eat all the bananas within h hours. Our value of 5 can never be less than the length of the array, because Koko needs at minimum one hour to finish each pile.
- We can work backwards from here. The brute force is a linear search. Let's take example 2.
- Our k is initially 30. She can finish all piles in 5 hours.
- We are looking for a minimum value of k. So we can either decrement k by 1 and check if 29 is valid, or do a binary search like technique and take the middle bound, which is (1 + 29) // 2. 1 is the minimum eating rate.
- Keep doing this until you reach your exit condition. At this point, k should be your minimum
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def can_eat(v):
return sum(map(lambda x: math.ceil(x / v), piles)) <= h
start, k = 1, max(piles)
while start < k:
mid = (start + k) // 2
if can_eat(mid):
k = mid
else:
start = mid + 1
return k