Koko Eating Bananas - Binary Search - Leetcode 875 - Python 

💡 BINARY SEARCH PLAYLIST: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-U8XENwh8Oy8.html

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

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

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

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

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

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.

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 !

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 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')

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 have a great ability to simplify solutions and present them in a very clear way. Thank you!

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

understanding the problem was half of the solution, thanks

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

in the older python it should be: hours += math.ceil(float(p) / k)

hours += math.ceil(float(p) / k) needs a float in line 10 btw for anyone who was confused why the code wasn't working

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.

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

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 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

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.

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 !

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

however if you initialize it to L,R = math.ceil(sum(piles)/h),max(piles) it will run

I love it when his voice goes deep, it makes the problem feel so much more serious 😆

It passes all cases with just 'res = k', instead of 'res = min(res, k)'

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 🙏🙏🙌🙌

After seeing your videos my brain was so sharp and able to do this question on my own

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?

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.

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...

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.

Minimum value can be further optimized as ceil(sum(nums)/h)

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

I would've never been able to solve this johnny-on-the-spot in an interview. hell no

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

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'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

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.

謝謝！

Minor typo? Shouldn't the brute-force complexity be: O(max(p).len(p)) and not O(max(p) . p)?

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

@Neetcode do we sort the piles array here before starting the loop?

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 ?

The THumbnail is a work of ART. will be in MET or Louvre one day

I keep coming back to this one because the thumbnail is amazing lol

this is one of those questions which i cant think of where do i start from . am i the only one ?

The first ever leetcode question i attempted two years ago

Thank you. Your explanation is so satisfying and refreshing!

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

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?

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.

Brutally Awesome Explanation! Thank you!!!

the solution is so elegant, thank you!

Gotta love this guy! OG 🔥🔥🔥

Best Explanation on the Earth!!!!

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 "

One of the best videos on this.

I like to see u running the code at the end. Maybe its just my OCD

please do these Magnetic force between balls(Lc: 1552), question Capacity to ship package(Lc:1011) and Smallest good base(483)

How do you get the idea that binary search will be used?. Can someone explain the thought process.

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 :')

AWESOME EXPLANATION!!!

Concise Solution with the best explanation out there

How would you identify that this is a binary search problem when you analyse before solving?

thank you senpai neetcode

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.

Great explanation ! Thanks

I know it's the right solution, but it feels like a bruteforce solution. That's why I thought there must be something quicker

it is not working

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?

well my code gave wrong answer with the same logic above. I used the exact code for cpp

Phenomenal explanation thank you.

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.

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; } };

You saved Koko with your solution.🤪

Your every video is worth to watch. Thanks for video Can you please cover this question 862- Shortest Subarray with Sum at least k

Thanks for very well explanation

best explanation!

Again I was able to come up with the solution, again I was unable to code the solution.

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.

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?

Hi, can you solve sudoku solver, the solve part is not at all going through my head

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

great logic thanks man

Hi @NeetCode, Hope you are doing well ! Could you please make a video on Brace Expansion II. Thanks and Regards!

It will according to the latest test cases

What is the time complexity of the brute force approach?

Awesome explanation bro

Could you please make a video on 2104. Sum of Subarray Ranges Thanks and Regards!

One detail he did not mention explicitedly is that l pointer has to start from 1 not 0. When I did try 0, i did get run time error (Divisible by 0) for some test cases. If L starts from 0 and the solution is 1, L and R both will go down to 0 after hitting 1 to check if 1 is indeed the smallest solution.

Mind Blowing Solution

Input: [312884470], 968709470 gives a division by zero error so you'd need a check for when your middle element is 0 then return

given solution is incorrect. Try this sol taken from neetcode - class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: l, r = 1, max(piles) res = max(piles) while l

I believe line 14 should be r = k, because you are looking for the first occurrence of the feasible eating speed, r = k - 1 will overskip a value.