Koko Eating Bananas - Binary Search - Leetcode 875 - Python

0:00 - Read the problem
1:40 - Intuition
6:55 - Drawing Explanation

12:55 - Coding Explanation

leetcode 875

#binary #search #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[faence]

I am horrified by the amount of bananas Koko is eating.

[Grawlix]

A couple tips/optimizations I noticed:

1. We shouldn't start at l = 1. We should start at l = ceil(sum(piles)/h. Take [3, 6, 7, 11] and h = 8 as an example. Logically, we know that to finish all bananas within 8 hours, the minimum rate is [3 + 6 + 7 + 11] / 8 = 27 / 8 = 3.375. Koko can't eat partial bananas, so round up to 4.

2. We don't need to use min() to track the result. We can simply store 'res = k' every time, instead of 'res = min(res, k)'. Think about this logically:
a) If we cannot eat all the bananas within H hours at rate K, we increase our L (slow) pointer and do not store a result
b) If we can eat all the bananas within H hours at rate K, we decrease our R (fast) pointer and store a result
c) If we hit an exact match (Koko eats all bananas in exactly H hours), we store our result and decrease our R (fast) pointer. Since we have just decreased our fast pointer, there are two options:
Option 1: It is impossible for us to ever eat all bananas within H hours.
Option 2: We find a valid rate, but this rate is less than the previous rate we discovered.

3. Minor, more obvious point: We *cannot* break early the first time we eat all bananas in exactly H hours. Take [3, 6, 7, 11] and h = 8 as an example. If our rate is 5, we will eat all bananas in 8 hours, but 5 is not the lowest possible rate of consumption.


The code:

def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = ceil(sum(piles)/h), max(piles)
res = r
while l <= r:
k = l + (r - l) // 2
hrs = 0
for pile in piles:
hrs += ceil(pile / k)

if hrs > h:
l = k + 1
else:
res = k
r = k - 1

return res

[symbol]

I hate this problem honestly, one of the weirder binary search problems for me...
Coming up with the intuition and understanding the problem was the hardest part

[aaen]

This is the fist time that I ALMOST got a medium leetcode right by myself, I was just missing the part of how to get the max(piles) values without having to order the array first, thus having a O(n logn) complexity. Thanks man, it's very motivational to feel like my solutions are slowly resembling yours

[almasabdrazak]

I understood that it had to be a binary search but I didn't get how to change the range values until I watched your explanation, Thank you !

[financewithsom]

honestly man you are the best explainer in youtube . dont stop uploading i wonder why people will go for algoexpert when they can get this masterpice content

[inderwool]

You would be able to optimise this solution even further by calculating the min instead of just using 1. As we know the total number of bananas is equal to the sum of all the piles and given the time h, we can calculate that the min will have to be total no. of bananas / h. Koko couldn't possibly finish the entire piles of bananas if she were to eat slower that this rate.

[numberonep]

Super dupper video! two small improvements: the left ind can start at max(1, -1+sum(piles)//h) and we can "break" the for loop before it finishes looping when the sum of hours is strictly bigger than h

[jedlechner]

Your vids are great. Just a comment for the watchers. Once the algo is defined try coding the problem yourself. I have improved so much by doing that.

[mmansaa]

You have a great ability to simplify solutions and present them in a very clear way. Thank you!

[ShamiSBhat]

Your neetcode practice problems are such a life saver. I'm grateful to have stumbled across your channel earlier this year. I have a request to ask, could you please make a list of recursive problems too. Thanks a ton for your amazing content !

[telnet]

understanding the problem was half of the solution, thanks

[cluster]

Thank you for this. I really like how you broke the problem down and watching your video made everything click. I was going through the discussions in lc before watching this but their explanations were too big brain for me...

[joaquinbadillo]

Great video as always! I am following your amazing roadmap and I usually check my approaches with your videos to see if I missed something. When going through this one I wanted to point out that a time complexity of O(max(p) * p) is actually way worse than it seems: it is Knapsack problem level bad. This has to do with it being a "pseudo-polynomial time" algorithm, because it gets worse (exponentially) depending on the number of bits used to represent an integer in the machine being used. Using binary search removes such threat because it becomes polynomial on the number of bits as well

[jigglypikapuff]

Thanks! A slight improvement would be to tighten "l" (lower bound) to be =math.ceil(min(piles) * len(piles) / h) since we cannot go better than that

[jlecampana]

Brutally Awesome Explanation! Thank you!!!

[TadesseDev]

You are incredibly good at driving the solution, It's not like you are telling what the answer is, but teaching how to see the problem. coming to this tutorial I had no idea what the optimal solution could be, then I just watch from 0:25 to 0:35 and understand how to approach and solve it ❤❤. And by the way, I google back to the video to say Thank you 🙏🙏🙌🙌

[rohithjanardhan]

Small tip: you do not have to store res variable. While will exit when l == r + 1, So you can return l and it would still work

[julesrules]

Thank you. Your explanation is so satisfying and refreshing!

[jayp]

No way I'd come up with this on the fly. Definitely just gonna memorize the code lol