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
I was able to figure out the problem, but seeing the time complexity of nlogn made me think there was a more optimised soln out there...... there wasnt.
whenever you need to check solution with an ordered list of values such as this, ask yourself this: 'if the solution is negative, does that mean we can skip the values before or after this value?' if the answer is yes, the solution can be optimized by binary search.
@@rryann088 Sure, think about how BS is taking advantage of a sorted list to select either the left or right portion. The same principle applies here. Let me show the relevant code: ``` while (l
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 h: l = k + 1 else: res = k r = k - 1 return res
I agree with that 2nd point of yours but abt the 1st one: Actually what you're doing is sum(piles) which is an O(n) operation. Think abt getting a larger list of 5000 or 8000 numbers. Would you still think that doing a summation is better than using two pointers? Just my assumption but I'd say 1st point takes a bit longer time than the one explained by NeetCode.
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
@@Kenny-st8cg true. Thanks for pointing out. No need to sort anything. Finding the max value in an array with a loop or the max() function only requires O(n)
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
I think the only reason is because we didn't know about the existence of Neetcode. I bought the AlgoExpert package a while ago, and now I find myself using Neetcode instead. Not to disrespect AlgoExpert content, it's good. Neetcode is just amazing (and free). Don't worry Neetcode, we'll make you popular and will contribute you financially as well!
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
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 🙏🙏🙌🙌
Hi, what happens when the initial K is actually already the minimum? lets say at 12:01, k = 6 is already the optimal minimum, by searching to the left, won't the binary search miss the target?
reading your comment i didnt store the variable and it gave wrong answer, its possible that while loops exits just after a condition where time taken by koko>hours in that case mid isnt the answer and answer stored earlier (which satisfies time_taken
@@ary_21 agreed, the key for this practice is to store the res. Or you would not guarantee to find the least K, but a K that can generate the right h. there are brunch of those K's, and the right answer is the smallest among them.
@@willshen5051 True , have you solved it now ? Every time i try to find time taken by koko by deviding piles[i] by mid i get error that says t is not in range of int , i also tried long long and got the wame error
@@ary_21 careful if you are suing "/" or "//", and use mod operation "%" to help you in necessary and believe Neetcode did something tricky there without explaining. I have a less clever version: if piles[i] % mid == 0: counter += piles[i] % mid. else: counter += piles[i] % mid +1 ex: piles[i] = 6, mid =3, counter should += 2 piles[i] = 7, mid =3, counter should += 3
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.
Bro you are a godsend, I was pulling my hair out on why the code wasn't working even through it was identical. Could you explain why this fixes the code though? It seems like some python specific adjustment. EDIT: I read some more comments and figured it out, older python does integer division unless specified.
at 11:09 you cross out the right half of the array. What if the correct number was 6? You checked if there was a smaller value but what if there wasnt one? Lets say you guessed 6 and that computed to be less than or equal to the target of 8 but then you move your right pointer to 6-1 (5). Now you've excluded 6 from being the solution. How does this work?
both min and max can be approximated before binary search. dont start at 1 and end at max You can optimize further to reduce complexity. although binary search is log of max so might not be worth extra optimization. min can be approximated we know that koko has to eat all the bananas in h hours. So koko has to eat at least some minimum x bananas per hour to finish all the bananas. if x = all bananas koko has 1 hour koko must eat at least x bananas per hour if koko has 2 hours koko must eat at least x/2 bananas per hour. ...and so on Using [3,6,7,11] and h = 8 koko must eat at least 3+6+7+11 = 27 bananas in 8 hours 27/8 = 3.3... (round up to 4 since koko cant eat fractional bananas per hour) minimum is 4 per hour not 1 max also can be approximated. if we take arbitrary x as max and assume it takes 2 hours to eat that pile if there is remaining hours to eat all the other piles in 2 hours then max is not x but x/2 Using [3,6,7,11] and h = 8 max = 11 so 11 / 2 = 5.5 (round up to 6) rate of 6 to eat 11 in 2 hours we would still have 6 hours remaining for other piles since 8 - 2 = 6 we have still 2 hours per other 3 piles remaining. 6/ remainder of piles = 6 / 3 = 2 so there is a remainder of 2 hours per pile so actual max is 6 not 11 Even if every pile was 11 you have 2 hours per pile so worst case you eat 6 bananas per hour. So actual_max = max/ (hours/n) ; where n = number of piles
Rather than starting from l = 1, I think we can further optimize further by starting from l = math.ceil(sum(piles)/h). This is because in the optimal scenario, each pile can be perfectly divided by the rate to meet the time limit. Using a rate smaller than this is unlikely to reach the time limit.
Understanding the problem it self was the main challange for me and afterwards finally got it was able to solve it for smaller values as it reminded me of the 278. First Bad Version Leetcode problem, but who knew Koko can eat so mnay bananas per hour and that the guards will leave Koko for soo long and had to adjust the way i was calcualting the min hours which in hindsight is better and looking at the comments I optimised it better with a the min starting at ceil(sum(piles)/h) class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: l = math.ceil(sum(piles)/h) r = max(piles) res = r while l
I was initially thinking, why don't we need to sort the piles in ascending order before performing the binary search? And I finally understood why; in fact, all but the largest pile in the list of piles are irrelevant to solve this problem for the binary search solution. Basically we're first assigning left = 1 and right = max(piles) since, at the very worst case, Koko can only eat 1 banana per hour* and, at the best case, Koko can eat as many bananas as there are in the largest pile of the given piles of bananas (if there were five piles = [30, 11, 23, 4, 20], the largest pile contains 30 bananas). Note that we can't control how many piles of bananas (ie. len(piles)) Koko is given, but we do know that-- at most-- Koko can finish *one* entire pile in an hour and no more piles in that hour**. So essentially we just need the two pointers, again pointing to both the minimum and maximum number of bananas Koko can eat in one hour. With those two points are defined, we essentially have ourselves a "sorted" list to perform the binary search. For instance, following the above example where piles = [30, 11, 23, 4 ,20], our initial range to perform the binary search would be a sorted list of 30 elements in ascending order = [1, 2, 3, 4, ... 27, 28, 29, 30]. Upon watching the video solution multiple times, I see that Neetcode does explain this well but it didn't click for me the first time watching it; hope it's helpful to others who also had the same confusion. *: Koko can't eat a fraction of a banana (we need to return the minimum '*integer* of k), so the least number of bananas Koko can eat is 1 banana (and not, eg, 0.5 bananas). **: Admittedly the problem description wasn't super explicit about this condition, though it does read: "Each hour, she chooses som pile (note: singular) of bananas and eats `k` bananas from that pile (note again: singular 'pile' not plural pile's')
Thank your for the comment. I got it when first watching this video several days ago, but then I forgot about the "sorted" part. We actually make a new list ourselves
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
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 !
Math.ceil is pretty important to the solution, otherwise, the code won't take care of cases where the number of piles < the rate we are eating each pile. Math.ceil rounds these cases up to 1(since the division would return a decimal < 1). Therefore, this satisfies the constraint that if the number of bananas in a pile is < the rate, only eat all the bannas in that pile and nothing else(since we round the time taken to eat that pile to 1). Pretty interesting solution!
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...
What's the time complexity? because there is a max() so it takes O(n), binary search takes log(n), and it loops through all piles takes O(len(piles)), so is it like O(log(O(n))*O(len(piles)),which should round to O(n)? Can someone help explain it, please? Thank you in advance
Remember that you can have different variables in Big O, so let's make it easier to talk about by saying there's "n" elements in the array and the largest value is "k". Max is O(n) because we have to iterate over n values, but that only needs to be done once => O(n) Binary search is O(log(k)) since we start with the largest value, and then each time we do it, we need to consider the n values in the array. Therefore, with log(k) repetitions, each "costing" n, we get O(n * log(k)) For Big O you need to focus on the asymptotically largest values, so O(n) + O(n * log(k)) simplifies to O(n * log(k)).
Wow, this particular question shows that you don't exactly need an array to perform binary search, binary search isn't tied to a data structure per se. I tried creating an array with all the possible values [1 -> max(piles)] from one up until the maximum value in the array so that I would be able to use binary search on an array as I've always used binary search. This method of just using pointers really opened my eyes to how much tunnel vision I had. Learning from example is great and all, however how do people come up with these solutions from their head? Is it something you can only learn from a computer science degree? Or is there some step by step process to algorithm design that I don't know of?
Hello, I solved the question by myself, I don't have CS degree, I have about 80 LC problems. I think the ability to solve such problems will come with time, so just practice every day!
@@dera_ng I also scratched my head around this, like how come there is no actual array??, but realized that array could be totally avoided here since possible values are consecutive, let us say if they aren't then we do (l+r)/2 it might lead to value which maynot be present in the range of values we are looking for
No we actually don't need to sort the piles, this confused me at first too. We are doing the binary search on potential values of k, not the piles themselves. It's a binary search of a range of values. You are right to think that we do need to sort. If we were doing a binary search on piles, we would definitely need to sort before implementing binary search
A simpler version of implementation. When we find a speed meet the criteria set it as the right bound and keep searching a better one. def minEatingSpeed(self, piles: List[int], h: int) -> int: l, r = 1, max(piles) while l < r: m = (l + r) // 2 hours = 0 for p in piles: hours += math.ceil(p / m) if hours > h: l = m + 1 else: r = m return l
i have a doubt neetcode. why is the algorithm not working if u write the standard binary search code: if hours < h: r = k - 1 elif hours > h: l = k + 1 else: return k
Regardless of how many bananas are present in one pile, koko would need atleast 1 hour to finish that pile no matter what the value of h is, so the value of k(numbers of total hours taken) will always be greater than or equal to length of the array so we could go from len(array) to max(piles), not too much of an optimization though.
Hey, I bought neetcode premium. Got to this one and couldn't even begin to think about how to apply the BS range solution to it, but the other mediums so far I have been able to solve. Not sure why i struggled on it so much. Do you have any tips for using your premium product that would help me become better at recognizing and thinking through how to apply the patterns to the problem and recognizing which patterns to apply? Bear in mind, I'm still working through the DS&A section.
The most difficult thing is, I think, if totalTime == h, what should we do? Just remember if we find an appropriate k, we should try to find a smaller k. So, totalTime == h, we find a good k, then we should try to find a smaller k.
In the example, very first time you found 6 and move searching window to the left and exclude 6, how can we make sure we will have a better solution than 6? any possible chance 6 may be the best solution ?
It took me a bit of time to figure out i should be using binary search for this. And even then I wrote much messier code. I definitely should have spent more time drawing things out and trying to think it through before even doing the pseudo code and I’d probably have done a lot better.
why is k == h (or rate = hour) not a separate statement like other binary search algos? why don't we return the rate when they are equal to the hour? why do we have to include it as part of the "
Because the valid minimum rate of eating could be equal to or less than the given number of hours, hence both of those conditions can be handled within the same conditional. However, it can never be more than the hours given hence a separate conditional for the greater than part.
I'll have interview with one of the big company. If you would not be exist, I'd not even have any hope. Thanks for your great solutions mate! I hope I can catch your level one day
It changes the complexity actually, even though not that much. If we know the minK, the time complexity is O(p*log(max(p) - S/h)) where p is the size of piles and S is the sum of piles.
@@nguyen-dev There is also another small optimization you can do. You don't need to go through all the piles once hours is higher than h, you can break it there. Here is the solution merging both optimizations. Here is the optimized solution if someone is interested class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: if len(piles) == h: return max(piles) l, r = math.ceil(sum(piles)/h), max(piles) res = r while l
For the new cases is not working and an unsorted list destroy this solution so my approach is just add a sort(piles) at the beginning and continues with this solution.
I don't know about all problems but if you can abstract a problem into searching through a range, binary search is most likely applicable If you're given a sorted array, binary search is also probably applicable although you might need to modify it (e.g in the case of a rotated sorted array) one thing to keep in mind is that if you have an unsorted array you could still apply binary search once you sort it, but chances are there might be a better solution since sorting is O(nlogn), you're automatically going to have a time complexity of at least that
I dont understand why we needed the res = min(res, k) part of the code. I thought k would always be the result we're looking for. Could someone explain that to me please?
can anyone help me understand why this code is always undercounting the speed: class Solution { bool canFinish(int speed, int h, vector& piles){ int hoursTaken = 0; for(int bananas : piles) hoursTaken += ceil(bananas/speed); return hoursTaken 1; if(canFinish(speed,h,piles)){ res = speed; r = speed - 1; }else l = speed + 1; } return res; } };
without question my least favorite problem ive ever come across. normally really enjoy solving these questions but this was a horrific problem in my opinion. The way it was worded made it drastically more confusing than it had to be. little clarity on how to treat bananas that are unfinished...if you eat 4 from a pile that has 5, maybe that extra 1 carries over to the pile you eat next. the problem should have been much more clearly stated. after you explained, and I reread the problem i can see how it makes sense, but in my eyes this was very poorly worded. a question should demand somebody spend the time trying to figure out a solution. NOT spending too long just trying to understand the problem...wow how frustrating.
Hey, Nice explanation, But I have one doubt about the problem itself. As per the problem, "each hour, Koko chooses some pile of bananas and eats k bananas from that pile". Here what does it mean by some pile? I understood it as we can take more than one pile in an hour. According to your solution, There must not be some pile.
Now I know that min = math.ceil(sum(piles) / h) is easy to understand But can someone explain why max = math.ceil( sum(piles) / (h - len(piles) + 1) ) works? It really does.
This code is literally impossible in C++. That math.ceil(p /k) he did can't be done in C++. Assuming p/k= 3/4 then it directly becomes 0 not 0.75. I used loop for his. now getting TLE :')
instead of doing math.ceil(p/k), you can try math.ceil(p/(float)k). Although it will still give error in later test cases. This worked for me class Solution { public: int minEatingSpeed(vector& piles, int h) { int start = 1, end = 1000000000, n = piles.size();
@@phatnguyenthanhtien2465 You're casting the result of an integer division to a double. When one of the operands in a division is a double and the other is an int (in this case: Math.ceil(int * double, int)) the operation turns into a double and you pass that double to Math.ceil. For example, 4 / 3 = 1.33, but since it is an int division it gives you 1 so you would be calling Math.ceil(1) which results to 1.0 If you have 4.0 / 3 then you get 1.33 and Math.ceil(1.33) gives you 2.0 Hope that made sense to anyone that was confused by this.
I tried the same in java but some test cases fails. I find it difficult to understand why. @NeetCode can you spot the error. public int minEatingSpeed(int[] piles, int h) { int i =1; int count =0; int j = Arrays.stream(piles).max().getAsInt(); int res =j; while(i
The reason you are failing is because you are returning too early. Remove this line if(count == h)return mid; Why does this line fail? Because it is possible that your count == h, but your mid (or the rate of koko eating bananas is still too high. You want further binary searches to narrow down the mid.
Is there really no way to solve this with a simple mathematical equation once you have max(piles), piles.length, and h? Seems like there should be but I suppose not.
Had no clue what was going on in this problem spent an hour and didn't make a single dent. I knew it had binary search involved but I literally had no clue in what sense at all
💡 BINARY SEARCH PLAYLIST: ua-cam.com/video/U8XENwh8Oy8/v-deo.html
thanks!
Can you do this question please? leetcode.com/problems/binary-tree-cameras/
I am horrified by the amount of bananas Koko is eating.
Lol
Koko is high on carbs these days.
@@humbleguy9891 lmao
the funny thing is, the problem never specified that it's a monkey. It very well could be a human named Koko
@@leeroymlg4692 The funniest thing is, no one asked.
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
I was able to figure out the problem, but seeing the time complexity of nlogn made me think there was a more optimised soln out there...... there wasnt.
whenever you need to check solution with an ordered list of values such as this, ask yourself this: 'if the solution is negative, does that mean we can skip the values before or after this value?' if the answer is yes, the solution can be optimized by binary search.
@@case6339 i did not understand what you said, sorry, care to explain?
@@rryann088 Sure, think about how BS is taking advantage of a sorted list to select either the left or right portion. The same principle applies here. Let me show the relevant code:
```
while (l
@@case6339 thank you so much! got it 👌
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 h:
l = k + 1
else:
res = k
r = k - 1
return res
Great point
Awesome explanation, thanks 😊
I agree with that 2nd point of yours but abt the 1st one: Actually what you're doing is sum(piles) which is an O(n) operation. Think abt getting a larger list of 5000 or 8000 numbers. Would you still think that doing a summation is better than using two pointers? Just my assumption but I'd say 1st point takes a bit longer time than the one explained by NeetCode.
@@tobiichiorigamisan Wouldnt that O(n) summation potentially save you from doing a certain number of O(n) operations where you add ceil(0/k) to hours?
@@tobiichiorigamisanfor p in piles is already a O(N)
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
How does one come up with the solution for this problem without help, but then not know how to find the maximum value in an array?
@@Kenny-st8cg true. Thanks for pointing out. No need to sort anything. Finding the max value in an array with a loop or the max() function only requires O(n)
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
I think the only reason is because we didn't know about the existence of Neetcode. I bought the AlgoExpert package a while ago, and now I find myself using Neetcode instead. Not to disrespect AlgoExpert content, it's good. Neetcode is just amazing (and free). Don't worry Neetcode, we'll make you popular and will contribute you financially as well!
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.
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 !
You have a great ability to simplify solutions and present them in a very clear way. Thank you!
謝謝！
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
Both of those weirdly make it slower on leetcode
as computer scientists at the core of what we do is calculating the number of bananas a monkey can eat without being noticed by the guards
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 🙏🙏🙌🙌
Hi, what happens when the initial K is actually already the minimum? lets say at 12:01, k = 6 is already the optimal minimum, by searching to the left, won't the binary search miss the target?
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
reading your comment i didnt store the variable and it gave wrong answer, its possible that while loops exits just after a condition where time taken by koko>hours in that case mid isnt the answer and answer stored earlier (which satisfies time_taken
@@ary_21 agreed, the key for this practice is to store the res.
Or you would not guarantee to find the least K, but a K that can generate the right h.
there are brunch of those K's, and the right answer is the smallest among them.
@@willshen5051
True , have you solved it now ? Every time i try to find time taken by koko by deviding piles[i] by mid i get error that says t is not in range of int , i also tried long long and got the wame error
@@ary_21 careful if you are suing "/" or "//", and use mod operation "%" to help you in necessary
and believe Neetcode did something tricky there without explaining.
I have a less clever version:
if piles[i] % mid == 0:
counter += piles[i] % mid.
else:
counter += piles[i] % mid +1
ex:
piles[i] = 6, mid =3, counter should += 2
piles[i] = 7, mid =3, counter should += 3
you mean counter += piles[i] / mid. otherwise counter will have 0. but a good trick
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.
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
hours += math.ceil(float(p) / k)
needs a float in line 10 btw for anyone who was confused why the code wasn't working
Bro you are a godsend, I was pulling my hair out on why the code wasn't working even through it was identical. Could you explain why this fixes the code though? It seems like some python specific adjustment.
EDIT: I read some more comments and figured it out, older python does integer division unless specified.
at 11:09 you cross out the right half of the array. What if the correct number was 6? You checked if there was a smaller value but what if there wasnt one? Lets say you guessed 6 and that computed to be less than or equal to the target of 8 but then you move your right pointer to 6-1 (5). Now you've excluded 6 from being the solution. How does this work?
both min and max can be approximated before binary search.
dont start at 1 and end at max
You can optimize further to reduce complexity. although binary search is log of max so might not be worth extra optimization.
min can be approximated
we know that koko has to eat all the bananas in h hours. So koko has to eat at least some minimum x bananas per hour to finish all the bananas.
if x = all bananas
koko has 1 hour koko must eat at least x bananas per hour
if koko has 2 hours koko must eat at least x/2 bananas per hour.
...and so on
Using [3,6,7,11] and h = 8
koko must eat at least
3+6+7+11 = 27 bananas in 8 hours
27/8 = 3.3... (round up to 4 since koko cant eat fractional bananas per hour)
minimum is 4 per hour not 1
max also can be approximated.
if we take arbitrary x as max and assume it takes 2 hours to eat that pile if there is remaining hours to eat all the other piles in 2 hours then max is not x but x/2
Using [3,6,7,11] and h = 8
max = 11 so
11 / 2 = 5.5 (round up to 6)
rate of 6 to eat 11 in 2 hours
we would still have 6 hours remaining for other piles
since 8 - 2 = 6
we have still 2 hours per other 3 piles remaining.
6/ remainder of piles = 6 / 3 = 2
so there is a remainder of 2 hours per pile
so actual max is 6 not 11
Even if every pile was 11 you have 2 hours per pile so worst case you eat 6 bananas per hour.
So
actual_max = max/ (hours/n) ; where n = number of piles
No way I'd come up with this on the fly. Definitely just gonna memorize the code lol
in the older python it should be:
hours += math.ceil(float(p) / k)
king
Thanks king, I was stuck at this for so long and I finally decided to come to comments once chatgpt couldn't help.
Rather than starting from l = 1, I think we can further optimize further by starting from l = math.ceil(sum(piles)/h). This is because in the optimal scenario, each pile can be perfectly divided by the rate to meet the time limit. Using a rate smaller than this is unlikely to reach the time limit.
Understanding the problem it self was the main challange for me and afterwards finally got it was able to solve it for smaller values as it reminded me of the 278. First Bad Version Leetcode problem, but who knew Koko can eat so mnay bananas per hour and that the guards will leave Koko for soo long and had to adjust the way i was calcualting the min hours which in hindsight is better and looking at the comments I optimised it better with a the min starting at ceil(sum(piles)/h)
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l = math.ceil(sum(piles)/h)
r = max(piles)
res = r
while l
understanding the problem was half of the solution, thanks
I was initially thinking, why don't we need to sort the piles in ascending order before performing the binary search?
And I finally understood why; in fact, all but the largest pile in the list of piles are irrelevant to solve this problem for the binary search solution.
Basically we're first assigning left = 1 and right = max(piles) since, at the very worst case, Koko can only eat 1 banana per hour* and, at the best case, Koko can eat as many bananas as there are in the largest pile of the given piles of bananas (if there were five piles = [30, 11, 23, 4, 20], the largest pile contains 30 bananas). Note that we can't control how many piles of bananas (ie. len(piles)) Koko is given, but we do know that-- at most-- Koko can finish *one* entire pile in an hour and no more piles in that hour**.
So essentially we just need the two pointers, again pointing to both the minimum and maximum number of bananas Koko can eat in one hour. With those two points are defined, we essentially have ourselves a "sorted" list to perform the binary search. For instance, following the above example where piles = [30, 11, 23, 4 ,20], our initial range to perform the binary search would be a sorted list of 30 elements in ascending order = [1, 2, 3, 4, ... 27, 28, 29, 30].
Upon watching the video solution multiple times, I see that Neetcode does explain this well but it didn't click for me the first time watching it; hope it's helpful to others who also had the same confusion.
*: Koko can't eat a fraction of a banana (we need to return the minimum '*integer* of k), so the least number of bananas Koko can eat is 1 banana (and not, eg, 0.5 bananas).
**: Admittedly the problem description wasn't super explicit about this condition, though it does read: "Each hour, she chooses som pile (note: singular) of bananas and eats `k` bananas from that pile (note again: singular 'pile' not plural pile's')
Thank your for the comment. I got it when first watching this video several days ago, but then I forgot about the "sorted" part. We actually make a new list ourselves
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
There is no need of res = min(res, k) writing res = k will also work as we are eventually moving towards left and thats always gonna be smaller.
you get it
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 !
Math.ceil is pretty important to the solution, otherwise, the code won't take care of cases where the number of piles < the rate we are eating each pile. Math.ceil rounds these cases up to 1(since the division would return a decimal < 1). Therefore, this satisfies the constraint that if the number of bananas in a pile is < the rate, only eat all the bannas in that pile and nothing else(since we round the time taken to eat that pile to 1).
Pretty interesting solution!
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...
What's the time complexity? because there is a max() so it takes O(n), binary search takes log(n), and it loops through all piles takes O(len(piles)), so is it like O(log(O(n))*O(len(piles)),which should round to O(n)? Can someone help explain it, please? Thank you in advance
Remember that you can have different variables in Big O, so let's make it easier to talk about by saying there's "n" elements in the array and the largest value is "k".
Max is O(n) because we have to iterate over n values, but that only needs to be done once => O(n)
Binary search is O(log(k)) since we start with the largest value, and then each time we do it, we need to consider the n values in the array. Therefore, with log(k) repetitions, each "costing" n, we get O(n * log(k))
For Big O you need to focus on the asymptotically largest values, so O(n) + O(n * log(k)) simplifies to O(n * log(k)).
I love it when his voice goes deep, it makes the problem feel so much more serious 😆
Wow, this particular question shows that you don't exactly need an array to perform binary search, binary search isn't tied to a data structure per se. I tried creating an array with all the possible values [1 -> max(piles)] from one up until the maximum value in the array so that I would be able to use binary search on an array as I've always used binary search.
This method of just using pointers really opened my eyes to how much tunnel vision I had. Learning from example is great and all, however how do people come up with these solutions from their head? Is it something you can only learn from a computer science degree? Or is there some step by step process to algorithm design that I don't know of?
Hello, I solved the question by myself, I don't have CS degree, I have about 80 LC problems. I think the ability to solve such problems will come with time, so just practice every day!
@@ЕрасылОразбек-ч3ъ Thanks 🙂
@@dera_ng I also scratched my head around this, like how come there is no actual array??, but realized that array could be totally avoided here since possible values are consecutive, let us say if they aren't then we do (l+r)/2 it might lead to value which maynot be present in the range of values we are looking for
Yeah and I still didn’t learn anything.
@Neetcode do we sort the piles array here before starting the loop?
No we actually don't need to sort the piles, this confused me at first too. We are doing the binary search on potential values of k, not the piles themselves. It's a binary search of a range of values.
You are right to think that we do need to sort. If we were doing a binary search on piles, we would definitely need to sort before implementing binary search
@@thereasonableprogrammer4921 but then how would we know the max value from the list without sorting?
It passes all cases with just 'res = k', instead of 'res = min(res, k)'
I would've never been able to solve this johnny-on-the-spot in an interview. hell no
A simpler version of implementation. When we find a speed meet the criteria set it as the right bound and keep searching a better one.
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
while l < r:
m = (l + r) // 2
hours = 0
for p in piles:
hours += math.ceil(p / m)
if hours > h:
l = m + 1
else:
r = m
return l
however if you initialize it to L,R = math.ceil(sum(piles)/h),max(piles)
it will run
Brutally Awesome Explanation! Thank you!!!
i have a doubt neetcode.
why is the algorithm not working if u write the standard binary search code:
if hours < h:
r = k - 1
elif hours > h:
l = k + 1
else:
return k
Because you found a solution where hours == h, but it might not be the minimum value of k you can find.
@@andrenbr that makes sense Andre. Thanks I appreciate it
Regardless of how many bananas are present in one pile, koko would need atleast 1 hour to finish that pile no matter what the value of h is, so the value of k(numbers of total hours taken) will always be greater than or equal to length of the array so we could go from len(array) to max(piles), not too much of an optimization though.
Gotta love this guy! OG 🔥🔥🔥
The THumbnail is a work of ART. will be in MET or Louvre one day
You actually don't even need to keep track of result here. When the binary search ends the value at the left pointer should always be the result
Thank you. Your explanation is so satisfying and refreshing!
I think there is no need for "res = min(res, k)" part, "res = k" is enough. Since it is impossible to have greater k value once "hours
the solution is so elegant, thank you!
Hey, I bought neetcode premium. Got to this one and couldn't even begin to think about how to apply the BS range solution to it, but the other mediums so far I have been able to solve. Not sure why i struggled on it so much. Do you have any tips for using your premium product that would help me become better at recognizing and thinking through how to apply the patterns to the problem and recognizing which patterns to apply? Bear in mind, I'm still working through the DS&A section.
After seeing your videos my brain was so sharp and able to do this question on my own
The most difficult thing is, I think, if totalTime == h, what should we do? Just remember if we find an appropriate k, we should try to find a smaller k. So, totalTime == h, we find a good k, then we should try to find a smaller k.
The first ever leetcode question i attempted two years ago
In the example, very first time you found 6 and move searching window to the left and exclude 6, how can we make sure we will have a better solution than 6? any possible chance 6 may be the best solution ?
It took me a bit of time to figure out i should be using binary search for this. And even then I wrote much messier code. I definitely should have spent more time drawing things out and trying to think it through before even doing the pseudo code and I’d probably have done a lot better.
why is k == h (or rate = hour) not a separate statement like other binary search algos? why don't we return the rate when they are equal to the hour? why do we have to include it as part of the "
Because the valid minimum rate of eating could be equal to or less than the given number of hours, hence both of those conditions can be handled within the same conditional. However, it can never be more than the hours given hence a separate conditional for the greater than part.
I'll have interview with one of the big company. If you would not be exist, I'd not even have any hope.
Thanks for your great solutions mate! I hope I can catch your level one day
Best Explanation on the Earth!!!!
You can make it slightly faster by starting at minK = math.ceil(sum(piles) / h) instead of minK = 1, but it doesn't really change the time complexity
It changes the complexity actually, even though not that much.
If we know the minK, the time complexity is O(p*log(max(p) - S/h)) where p is the size of piles and S is the sum of piles.
@@nguyen-dev There is also another small optimization you can do. You don't need to go through all the piles once hours is higher than h, you can break it there. Here is the solution merging both optimizations.
Here is the optimized solution if someone is interested
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
if len(piles) == h:
return max(piles)
l, r = math.ceil(sum(piles)/h), max(piles)
res = r
while l
Minimum value can be further optimized as ceil(sum(nums)/h)
For the new cases is not working and an unsorted list destroy this solution so my approach is just add a sort(piles) at the beginning and continues with this solution.
This is actually very good,
Thank you
Concise Solution with the best explanation out there
Minor typo? Shouldn't the brute-force complexity be: O(max(p).len(p)) and not O(max(p) . p)?
I keep coming back to this one because the thumbnail is amazing lol
How would you identify that this is a binary search problem when you analyse before solving?
I don't know about all problems but if you can abstract a problem into searching through a range, binary search is most likely applicable
If you're given a sorted array, binary search is also probably applicable although you might need to modify it (e.g in the case of a rotated sorted array)
one thing to keep in mind is that if you have an unsorted array you could still apply binary search once you sort it, but chances are there might be a better solution since sorting is O(nlogn), you're automatically going to have a time complexity of at least that
you explained it so well I was able to solve without checking the code
AWESOME EXPLANATION!!!
One of the best videos on this.
no need for min(k, res) as we already made sure to explore only those k's which are smaller from the one we found
thank you senpai neetcode
Phenomenal explanation thank you.
theres nothing in the question description that implies koko is a monkey, it doesnt even say zoo keeper. guards?? like is she a woman in prison
Thanks for very well explanation
I like to see u running the code at the end. Maybe its just my OCD
What is the time complexity of the brute force approach?
please do these Magnetic force between balls(Lc: 1552), question Capacity to ship package(Lc:1011) and Smallest good base(483)
You saved Koko with your solution.🤪
Great explanation ! Thanks
I dont understand why we needed the res = min(res, k) part of the code. I thought k would always be the result we're looking for. Could someone explain that to me please?
the question asks to return the minimum k out of all valid k(s).
You are correct the min is not needed in the if statement
can anyone help me understand why this code is always undercounting the speed:
class Solution {
bool canFinish(int speed, int h, vector& piles){
int hoursTaken = 0;
for(int bananas : piles) hoursTaken += ceil(bananas/speed);
return hoursTaken 1;
if(canFinish(speed,h,piles)){
res = speed;
r = speed - 1;
}else l = speed + 1;
}
return res;
}
};
without question my least favorite problem ive ever come across. normally really enjoy solving these questions but this was a horrific problem in my opinion. The way it was worded made it drastically more confusing than it had to be. little clarity on how to treat bananas that are unfinished...if you eat 4 from a pile that has 5, maybe that extra 1 carries over to the pile you eat next. the problem should have been much more clearly stated. after you explained, and I reread the problem i can see how it makes sense, but in my eyes this was very poorly worded. a question should demand somebody spend the time trying to figure out a solution. NOT spending too long just trying to understand the problem...wow how frustrating.
I'm pretty sure the person who invited this problem got his dog to write the problem.
this is one of those questions which i cant think of where do i start from . am i the only one ?
Hey, Nice explanation, But I have one doubt about the problem itself. As per the problem, "each hour, Koko chooses some pile of bananas and eats k bananas from that pile". Here what does it mean by some pile? I understood it as we can take more than one pile in an hour. According to your solution, There must not be some pile.
some pile basically means any one pile
Ordering of the piles doesn't matter.
Now I know that min = math.ceil(sum(piles) / h) is easy to understand
But can someone explain why max = math.ceil( sum(piles) / (h - len(piles) + 1) ) works? It really does.
Input: [312884470], 968709470 gives a division by zero error so you'd need a check for when your middle element is 0 then return
That's weird, i'm not sure how middle would ever be zero if left is initialized as L=1
@@NeetCode that makes sense! I think I initialized left as 0
She died by eating too much banana
Awesome explanation bro
It will according to the latest test cases
I know it's the right solution, but it feels like a bruteforce solution. That's why I thought there must be something quicker
This code is literally impossible in C++. That math.ceil(p /k) he did can't be done in C++. Assuming p/k= 3/4 then it directly becomes 0 not 0.75. I used loop for his. now getting TLE :')
instead of doing math.ceil(p/k), you can try math.ceil(p/(float)k). Although it will still give error in later test cases.
This worked for me
class Solution {
public:
int minEatingSpeed(vector& piles, int h) {
int start = 1, end = 1000000000, n = piles.size();
while(start
If anyone is using C++, then use hours += ceil(p * 1.0 / k); instead of hours += ceil(p / k);
Hi, I encountered the same problem while using Math.ceil(p/k) in Java. Can you please explain why we need to multiply * 1.0?
@@phatnguyenthanhtien2465 You're casting the result of an integer division to a double. When one of the operands in a division is a double and the other is an int (in this case: Math.ceil(int * double, int)) the operation turns into a double and you pass that double to Math.ceil.
For example,
4 / 3 = 1.33, but since it is an int division it gives you 1 so you would be calling Math.ceil(1) which results to 1.0
If you have
4.0 / 3 then you get 1.33 and Math.ceil(1.33) gives you 2.0
Hope that made sense to anyone that was confused by this.
I have no idea what this question is asking lol
I tried the same in java but some test cases fails. I find it difficult to understand why. @NeetCode can you spot the error.
public int minEatingSpeed(int[] piles, int h) {
int i =1;
int count =0;
int j = Arrays.stream(piles).max().getAsInt();
int res =j;
while(i
The reason you are failing is because you are returning too early. Remove this line
if(count == h)return mid;
Why does this line fail? Because it is possible that your count == h, but your mid (or the rate of koko eating bananas is still too high. You want further binary searches to narrow down the mid.
it is not working
Is there really no way to solve this with a simple mathematical equation once you have max(piles), piles.length, and h? Seems like there should be but I suppose not.
Mind Blowing Solution
Thank you, wonderful
U a God - Harambe
Had no clue what was going on in this problem spent an hour and didn't make a single dent. I knew it had binary search involved but I literally had no clue in what sense at all
wow this was simple i am cooked
great logic thanks man
thank you neetcode