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)
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.
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
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
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
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.
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 !
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
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 🙏🙏🙌🙌
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)).
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...
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
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
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.
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
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 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.
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.
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?
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.
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.
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?
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.
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 ?
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
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.
You kinda just have to notice that you can only eat x bananas / hr where that x is in the range of 1 to max(piles). Since you will be getting a sorted array that is in increasing order, you can use binary search on to see which one of x in the range of (1 to max(piles) allows you to eat all the bananas in less than or equal to h hours. and from there on, in case you find that x , you also want to look to the left of the sorted array to see if a smaller value for x satisfies the same condition.
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();
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
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.
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; } };
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.
💡 BINARY SEARCH PLAYLIST: th-cam.com/video/U8XENwh8Oy8/w-d-xo.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)
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.
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 !
understanding the problem was half of the solution, thanks
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.
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
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
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
You have a great ability to simplify solutions and present them in a very clear way. Thank you!
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
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
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.
No way I'd come up with this on the fly. Definitely just gonna memorize the code lol
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
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 !
謝謝！
I would've never been able to solve this johnny-on-the-spot in an interview. hell no
It passes all cases with just 'res = k', instead of 'res = min(res, k)'
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
I love it when his voice goes deep, it makes the problem feel so much more serious 😆
however if you initialize it to L,R = math.ceil(sum(piles)/h),max(piles)
it will run
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 🙏🙏🙌🙌
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)).
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...
it is not working
Minimum value can be further optimized as ceil(sum(nums)/h)
Minor typo? Shouldn't the brute-force complexity be: O(max(p).len(p)) and not O(max(p) . p)?
Brutally Awesome Explanation! Thank you!!!
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!
@@user-sn8hz2le5s 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.
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
Thank you. Your explanation is so satisfying and refreshing!
Best Explanation on the Earth!!!!
the solution is so elegant, thank you!
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
After seeing your videos my brain was so sharp and able to do this question on my own
I keep coming back to this one because the thumbnail is amazing lol
The THumbnail is a work of ART. will be in MET or Louvre one day
@Neetcode do we sort the piles array here before starting the loop?
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.
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
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
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
this is one of those questions which i cant think of where do i start from . am i the only one ?
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.
AWESOME EXPLANATION!!!
Gotta love this guy! OG 🔥🔥🔥
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.
One of the best videos on this.
The first ever leetcode question i attempted two years ago
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.
Great explanation ! Thanks
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?
thank you senpai neetcode
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.
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.
Phenomenal explanation thank you.
Concise Solution with the best explanation out there
I like to see u running the code at the end. Maybe its just my OCD
best explanation!
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?
Thanks for very well explanation
You saved Koko with your solution.🤪
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.
Again I was able to come up with the solution, again I was unable to code the solution.
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 ?
Awesome explanation bro
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
well my code gave wrong answer with the same logic above. I used the exact code for cpp
mine too
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.
How do you get the idea that binary search will be used?. Can someone explain the thought process.
You kinda just have to notice that you can only eat x bananas / hr where that x is in the range of 1 to max(piles).
Since you will be getting a sorted array that is in increasing order, you can use binary search on to see which one of x in the range of (1 to max(piles) allows you to eat all the bananas in less than or equal to h hours. and from there on, in case you find that x , you also want to look to the left of the sorted array to see if a smaller value for x satisfies the same condition.
great logic thanks man
Mind Blowing Solution
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
U a God - Harambe
I know it's the right solution, but it feels like a bruteforce solution. That's why I thought there must be something quicker
thanks
It will according to the latest test cases
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
please do these Magnetic force between balls(Lc: 1552), question Capacity to ship package(Lc:1011) and Smallest good base(483)
thx
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.
Nice drawing brotha
thanks man
What is the time complexity of the brute force approach?
Your every video is worth to watch. Thanks for video
Can you please cover this question 862- Shortest Subarray with Sum at least k
does't work
Thanks
why this solution still falls in binary search. where we create extra memory for lowest pile 1 to highest pile 11 to get maximum pile per hour?
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;
}
};
Could you please make a video on 2104. Sum of Subarray Ranges
Thanks and Regards!
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.
Thank you, wonderful
Hi, can you solve sudoku solver, the solve part is not at all going through my head