Table of Contents: Intro 0:00 - 0:24 The Problem Introduction 0:24 - 2:39 Base Case #1: 1 Egg 2:39 - 6:21 Base Case #2: 0 or 1 Floors 6:21 - 8:47 Summarizing Our Base Cases 8:47 - 10:18 The Simulation. 6 Floors, 3 Eggs 10:18 - 18:36 DP Table Walkthrough 18:36 - 22:06 Camera Dies. Finishing Explanation of The Simulation. 22:06 - 23:30 Time Complexity 23:30 - 24:12 Space Complexity 24:12 - 24:51 Wrap Up 24:51 - 25:19 Update 4/3/19: Both the Top Down & Bottom Up approaches shown in the video time out on Leetcode due to the test cases changing. The code for the problem is in the description (both bottom up and top down). Fully commented for understanding.
Bro, just, aaaaaaaaaaaaaaaaaaah, just, aaaaaaaaaaaaaaaaaa, just, I applause you, thank youuuuuuuuuuuuuuuuuuuuuuu, brooo, I just cant express my feelings, aaaaaaa its so coooooooooooooool, I understood it!
Yep, I got that but what's the recurrence relation for construction of the DP table? If we denote optimal solution by OPT(m,n) where we have m eggs and n floors then how will we write it in terms of recurrence ?
I have been watching your videos recently and cant thank you enough for explaining hard puzzles in a layman's language. I haven't seen anyone who explain the actual "purpose" of the problem as you do. Well done and keep posting :)
I have watched several videos but none of them was as good as this one. Awesome job dude. Thank U. All the videos talk about solution without explaining subproblems of dynamic programming. But you explained it really well my friend.
Respect for both, for the lack of good dynamic programming videos, Tushar pioneered it well imo. Ben is teaching it better with the intuition behind things, can’t deny that either :)
I can see the amount of effort you've been putting on your videos. This is what I had been looking for the last 2 years. I feel very lucky that you started making videos before I graduate.
I know you have your own plan, but I have a suggestion. Recently I started learning 'parametric search' and I find it tricky. -> what is the proper condition to be put in "while( )" ??? -> when do I put '=' on "if (K < mid)", and when do I put '=' on "if (mid < K)" ??? I don't wanna break your pace, just wanted to give you an idea. thx!
@@BackToBackSWE I heard it is highly relevant to binary search. I found some example questions, I'll add the links here. Question 1 ) hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf -- Question #2 (It starts with the sentence "Lumberjack Mirko needs to chop down M metres of wood....") Question 2 ) www.acmicpc.net/problem/3703 Question 3 ) poj.org/problem?id=3273 I think I can solve above questions applying binary search... Do you agree? Or any better method to solve them???
Thank you, Lord. Finally found a video that can help. I wish I had this person teaching my algorithm class instead of my prof who looks at her notes and talks to the board.
I have been trying to understand this problem through many YoutTubers,but lemme tell you Sir, this is the best explanation I had. Keep the work up Sir.
I don't where you are these days, when I was fresher I learnt from your videos. Now I have experience of 3 years and I am still learning from you. Am I in love with you ? 😜
Here's the code link: ua-cam.com/users/redirect?q=https%3A%2F%2Fgithub.com%2Fbephrem1%2Fbacktobackswe%2Ftree%2Fmaster%2FDynamic%2520Programming%252C%2520Recursion%252C%2520%2526%2520Backtracking%2FEggDrop&redir_token=QUFFLUhqbnQ3T2tXamxoVTh5c205TlJCYjZCYmZsOWNjZ3xBQ3Jtc0trODRCQlRicjVIbXh0dXk5VEhrel9QQkZUNXFRamMzSVdablYxLUE5aVk3RGxrRUFOMjNTQkRWSk1qeFlrcVk1cEVIUU51b3E5X3dtSXh2M0FGcmxPY0ZiUFU5eTU4YjhuMDZYckl3YXNDeTQ2UFJIQQ%3D%3D&event=comments&stzid=UgzKhQ0U7vTf35sZifd4AaABAg
Its my first time watching your video and I gotta tell it "MAN U HAVE EARNED MY RESPECT" seriously man can just emphazize on how much easy u did this to me . . Just a single problem ... ur code link redirects to a page not found ... look up for that
Thanks for the detailed explanation : // if egg breaks then egg-1 and floor -1 ==> dp[e - 1][k - 1] // else no change in egg count and remaining floors which is f-k ==> dp[e][f - k] // k means which floor we are in -- > first floor , second floor // 2 Eggs -> 3 Floors // • 2 Eggs -> lets try from 1st Floor-> 1,0 ,, 2,2 // • 2 Eggs -> lets try from 2nd Floor -> 1,1 ,, 2,1 // 2 Eggs -> lets try from 3rd Floor -> 1,2 ,, 2,0
Your teaching are very clean and understandable ,I am glad to get a teacher like you in my journey of career.You deserve more subscribers.Good luck ,keep it up!🌈✨
I want to thank you sir for you really put in so much effort into these videos.I like the fact that you provide links to other channels too ( Like Tushar Roy etc).
I know this would be a difficult one to make, but you should make a video going over techniques for identifying overlapping subproblems and optimal substructure in DP problems in general. Pulling from examples like this and longest non-decreasing subsequence (and your other vids). Basically, abstracting the problem specific examples and giving some practical tips for how to identify subproblems. Fingers crossed xD
after watching several videos on this topic, this video proved out to be the best as always. explanations were very clear although the hiccup in the end disrupted the flow.
good video. I was with you until min 20:47. Why do you have drop (2,1) in addition to drop (2,2). I get the 2,2 one, but since 2 eggs,1 floor cell was a 1, why that one ?
I fudged making that part clear - I remember this vividly, I'd go in and explain but I'm rapid fire responding to 250 comments I got backed up after 2 weeks
In the case (2,1), you are on the Floor 1,just by using one egg, you would know which floor is the "won't break"(I will use F below) floor. If the egg breaks on Floor 1, then "F" floor will be Floor 0. Otherwise will be Floor 1. Only Floor 1 and Floor 0 are to be discussed in case(2,1). totalFloor = 1 is a base case, no matter how many eggs there are, the answer is always 1.
The diagram starting at 12:52 was a bit misguiding the first time I saw it, because the first 6 tree levels don't represent the same thing as the second pairs of "possibilities". In reality, the solution for just one of the subproblems (e.g. 5F, 3E in this list) needs to iterate again through simulations for all 5 floors (with both break/non-break possibilities). And then each of those smaller subproblems again needs to iterate through a bunch of floor-egg pairs. This is where the (F, E) pairs begin reappearing and the memoization (caching) of the subproblems leads to DP. One useful way of looking at it is to realize that the solution to (4F, 3F) is the same regardless of whether we are considering top 4 floors or bottom 4 floors - it doesn't matter and we will end up calculating them twice unless we cache them or use DP to get them ahead of time.
Hey great video, just a quick question, why is it that the minimum amount of egg drops for n floors is n? Wouldn't it be log(n) times since we can do sort of a binary search where we drop an egg from (n/2)th floor and if it breaks we know every egg dropped from above that floor will break and if it doesn't break we know that every egg dropped from below that floor won't break ?
We can do it logarithmically, that is the next best solution. I just presented the base solution that someone could practically come up with in an interview.
@@BackToBackSWE I see. Can I ask you just one more question? Why is it that we want the worst outcome of the drops, that is max(drop(eggs, totalFloor - currentFloor), drop(eggs - 1, currentFloor - 1)) ? This part still doesn't seem to click in my head.
@@ChainForLife Never limit questions. Always ask questions until you understand. Push the teacher as well as yourself because I don't know it all...or else we both learn nothing. So think about this....our goal is to tell the caller the SMALLEST amount of drops so that I can PROMISE that in those drops...I will find the pivotal floor. If I don't account for the worst outcome of drops...I could be lying...my promise could be broken. I have to take into account the WORST outcome and BOUND my drops to that because it promises that I find the pivotal floor in that amount of drops NO MATTER WHAT CASE happens. Does that make sense?
Thanks a lot, BTB SWE for crystal clear explanation, I always think in a Top to Down DP approach but always got confused in Bottom Up DP. Can you people make another separate video for thinking ina bottom up DP please?
Yes. I will address this in a video similar to this: ua-cam.com/video/Zq4upTEaQyM/v-deo.html one day. Don't worry, as long as this project stays active I will cover what people want to see.
Your channel is great and really helping me with learning and understanding Dynamic Programming. I wanted to know, can this problem be solved optimally using Jump Search Algorithm?
MISTAKE (always droop from the middle if you have more than one egg): There is a fundamental logical MISTAKE and while it does not affect the result, it does simplify the solution when realized. See: If you have more than one egg, you can start drooping the first egg from any of the N floors. So, you evaluate the cost of dropping from each floor and stay with the floor that yields the minimum cost (min). But when you think better, that is completely unnecessary: you don't need to evaluate all the floors, because the middle floor will always yield the minimum drooping cost. Always! Now, depending on N (even or odd), the middle floor might or might not have an equal number of floors above and below. When it does not, you stay with the worst case scenery: solve the problem with more floors (max). Applying this logic, you eliminate the min operation that evaluates all possible floors (go always with the middle) and the solution to the problem cuts down as follows: def eggs(N,e): if e==1: return N if N==1: return 1 mid=math.ceil(N/2) if (N-mid)>(mid-1): return eggs(N-mid,e)+1 else: return eggs(mid-1,e-1)+1 Explanation of the middle selection: Suppose you have 100 floors and just 2 eggs. You droop the first egg from 99: in the best case it does not break and with the remaining egg you scan the only floor left, the floor 100 (the one above you). So the best case is 2 droops! But in the worst case (it did not break), you have to scan 98 floors below you one by one with the only remaining egg. This makes 98 droops for the worst case. Thus, you are risking a lot (too much difference between the best and the worst case, and you don’t know what the case will be). So: 99: 2 (best)-98(worst) 98: 3(best)-97(worst) 97: 4(best)-96(worst) . . 4: 4(best)-96(worst) 3: 3(best)-97(worst) 2: 2 (best)-98(worst) Look! When you go downwards the risk reduces (the difference between best and worst case tends to zero) but, it happens like that also when you go upwards. So, in the middle point the risk will be near zero (depending of N being even or odd). But, in any case, the middle point (as Buddha said) will always be the most neutral or best option to droop any time you have more than one egg (the one with minimum cost).
@@BackToBackSWE Be aware that this reduces the problem to Logn time. I havent seen aneyone giving this solution, it seems I am the fisrt person realizing it
Great job, you deserve more subs than most others who do these type of videos. However, can you go in depth a bit on what you'd need to simulate all of the floors? Why can't you just start branching from 6 floors, 3 eggs?
We do. To solve the subproblem you just stated: drop(3, 6) -> we need to imagine, just imagine...that we start dropping from floor 1 with 3 eggs, floor 2 with 3 eggs, floor 3 with 3 eggs, floor 4 with 3 eggs, etc. At each simulation, we want to know the 2 possibilities. What do they yield in terms of worst drops. This is how we converge to base cases. Now, to your question. Why simulate? Well...what was the original question: "You are given n eggs and specified a number of k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break." How can I know FOR SURE...for sure...the MINIMUM # of drops to find the pivotal floor? Well for the solution presented (and there are others) we do a test from each floor and find the WORST performer. This worst performance is a possible reality. We must account for it. And thus, we take this worst reality/outcome AFTER DROPPING. After dropping. If we miss out on any simulation we will miss a possible outcome that may worsen our worst case. This brings me to why we add 1. The +1 is because we want to say that "The answer where I stand is the action I take, plus the result of the worst outcome that follows." the action. A drop. +1 to the worst case drops. the result. That is the worst subproblem result that happens after our action. I could keep going but check the code in the description. Keep asking questions. I have answers...most of the time.
Here's another way to look at it: think about every call to drop(eggs, floor) as literally throwing one of your eggs down from the chosen floor. So if you computed drop(3, 6) by only considering the 6th floor (instead of testing all the floors), what you are saying is - what is the minimum number of times I need to throw eggs off of floors to find the first floor it breaks... *given that you threw your FIRST egg off the 6th floor?* As you can imagine, we might be able to reduce the number of drops in the worst case by dropping the FIRST egg off, say, the third floor - (drop(3, 3)) - if it breaks, you've eliminated the top half of floors, and if it doesn't, you've eliminated the bottom half (had we just thrown it off the highest floor each time, if the egg breaks, we would have only eliminated one floor; if the egg broke from that floor, only one more floor, and so on). Of course, we don't really know which floor to drop off first to minimize the number of drops, so we try each floor. This reflects the floor we should throw our egg off first!
@@FloShaban I still feel like I could've made it clearer...oh well. There are better solutions but I just covered the most basic solution one would realistically get with previous dp experience.
If looking at finding floor is like finding an item in an array, then it will be an easy math calculation of if (eggs == 1) return floors // "floor by floor method" if (eggs >= log(floors)) return log(floors); "simple binary search" else // this is a mix of the two approaches - we want to start a binary search until we have one egg left. divide the floors by 2 and assume the egg will break in every test. do this until we have the chunk size we have to go with the "floor by floor" method and drop. so overall it's the amount of dividing by 2 we can do + the size of the chunk that is left also, this - while can probably be improved to a single formula but you said at the end of the video no hard math time = O(log(eggs)) space = O(1) I really wonder what am I missing here
It expresses the # of floors above where we dropped. Think on this. Example 1: 6 5 4 3 (drop here) 2 1 0 simFloor = 3 I drop at 3. No break. I go up. Do I have 6 - (3) = 3 floors above me? Or simfloor + 1 = (3) + 1 = 4 floors above me? Example 2: 6 (drop here) 5 4 3 2 1 0 simFloor = 6 I drop at 6. No break. I go up. Do I have 6 - (6) = 0 floors above me? Or simfloor + 1 = (6) + 1 = 7 floors above me? Check the code in the description. Really internalize it.
@@BackToBackSWE Yeah, I searched other videos or blogs, and I just saw 99% similar explanation to yours. I hope I can come back here later and I clearly understand this.
@@raymondyoo5461 Yeah, time helps as you see more dp problems. It is a specific way of thinking. When it does click it will be interesting. What is still unclear? If I may clarify it.
There are very smart people that theoretically could. It is just that I don't think there are enough of those high powered individuals to make it worth it to get that good at niche problems you may get (and lose to them in). Time is better spent on larger problem sets.
Question: Would this problem also be solved by a piecewise function of binary and linear search where you do binary search until eggnum == 1, then do linear search from the minpointer to the maxpointer? If I’m right and this is the case, the runtime complexity should be O(Height)/Θ(log(Height)), and space complexity O(1)? Also, pretty good job explaining the question in terms of DP. :)
Great video, but I really think that you should do binary search instead of going one floor up and down, would be much less drops and much more saved eggs :)
@@BackToBackSWE I understand that you didn't do binary search for simplicity, but I think at least mentioning it as possible optimization would open some eyes. Keep the good work!
why is it that we take the min of WORST CASE? what does WORST CASE represents here? The Maximum no of attempts that you can do at given floor without breaking the egg
at 20:50 You said that the answer is the one who do the worst but I think it minimum of "all the worst case possibilities at each floor" for a corresponding (eggs and floors)
Thanks for your perfect explanation!But for your code, I have one question. Why do you plus one here " int accountingForDroppingAtThisSubproblem = 1 + costOfWorstOutcome;" You mentioned that you were doing a test.Can you explain the test clearly?I'm feeling quite confused.
Hey, thanks for the explanation! The cases where the egg breaks seems logical, but I don't get the case where the egg doesn't break. If the egg doesn't break on floor 5 why i can use the function for 6-5 = 1 floor? When the egg survives the fall from floor 5, it must also stay unharmed when dropped from floor 1...
everything is okay.. but when saying if egg breaks on floor 4 we go down to floor 3 you could say that if the egg breaks on floor 4 we are left to check 3 floors because its not the n'th floor rather the total number of floors as argument in drop function...
Why don't we use a binary search for egg 2~n to narrow down the last egg searching range? What I mean is Assume we have 2 eggs and 6 floors drop(2,6) We fist try to drop an egg at the 3rd floor If it break, then search from 1 to 2 drop(1,2) If it doesn't break, then search from 4 to 6 drop(2,3) = 1 + Math.max(drop(1,2), drop(2,3)) Whenever number of eggs > 1, the sub problem can be drop(eggs, floor/2) and drop(eggs-1, floor/2 -1)
If the total numbers of eggs are 1, then why are we returning total floors? It may be the case that we don't need to get to the top floor and before that we get the pivotal floor
Update: When he says the least amount of eggs that you will ever drop, He means to say the least number of egg drops (moves) that one will ever that guarantees for a pivotal floor p; dropping an egg from p + 1 breaks and any floor (
Why cannot we approach the problem in a binary search manner? That would reduce the time a lot. So we wouldn't find the sub problem for +-1 floor, but we'd either half the floor towards the ground or towards the top.
I’m definitely misunderstanding the question because with one egg, couldn’t you just start at floor 0 and go up until it breaks, therefore solving this in O(totalFloors) time? What is the advantage of having more than one egg? What am I missing?
At 20:59 When we want value for drop(2,2) , then, Why do we simulate sim(2,1) & sim(2,2) . we are solving for is 2 (which is 'totalFloors') floors and 2 (which is 'totalEggs') eggs. We are doing 2 simulations: sim(2, 1) (2 eggs, start from floor 1) and sim(2, 2) (2 eggs, start from floor 2). why not just sim(2,1) ? beacuse sim(2,2) is bad choice... right ?
"why not just sim(2,1)?" If we just do one of the simulations (and not all of them) we may miss a case that would've yielded a truer bound to the worst amount of eggs that would need to be dropped to ensure we find the pivotal floor. For the approach in the video (and it is not the most optimal approach), we have to run all simulations to ensure our upper limit is correct with such a guarantee.
I love your channel but you have not posted in a while. If you do get time, would you be able to do Two city scheduling problem? It is a dynamic programming problem. :)
Table of Contents:
Intro 0:00 - 0:24
The Problem Introduction 0:24 - 2:39
Base Case #1: 1 Egg 2:39 - 6:21
Base Case #2: 0 or 1 Floors 6:21 - 8:47
Summarizing Our Base Cases 8:47 - 10:18
The Simulation. 6 Floors, 3 Eggs 10:18 - 18:36
DP Table Walkthrough 18:36 - 22:06
Camera Dies. Finishing Explanation of The Simulation. 22:06 - 23:30
Time Complexity 23:30 - 24:12
Space Complexity 24:12 - 24:51
Wrap Up 24:51 - 25:19
Update 4/3/19: Both the Top Down & Bottom Up approaches shown in the video time out on Leetcode due to the test cases changing.
The code for the problem is in the description (both bottom up and top down). Fully commented for understanding.
Bro, just, aaaaaaaaaaaaaaaaaaah, just, aaaaaaaaaaaaaaaaaa, just, I applause you, thank youuuuuuuuuuuuuuuuuuuuuuu, brooo, I just cant express my feelings, aaaaaaa its so coooooooooooooool, I understood it!
yeah
hahahaha nice
Yep, I got that but what's the recurrence relation for construction of the DP table?
If we denote optimal solution by OPT(m,n) where we have m eggs and n floors then how will we write it in terms of recurrence ?
@@monil1601 I don't remember
your channel is like a NETFLIX of DS & algorithms.
whenever i try to watch one of your videos i found 10 more intriguing ones
haha nice
Just wanted to say how much I appreciate these videos. You're really doing a great job of helping all of us out here and I can't thank you enough!
I have to feed the family. Everyone eats. Otherwise, I'm starving.
These are some strong ass eggs
agreed
LOL
Its nice to find a video explaining way of approach rather than repeating the dp tables from solutions.Thanks man.
sure
I have been watching your videos recently and cant thank you enough for explaining hard puzzles in a layman's language. I haven't seen anyone who explain the actual "purpose" of the problem as you do. Well done and keep posting :)
I have watched several videos but none of them was as good as this one. Awesome job dude. Thank U. All the videos talk about solution without explaining subproblems of dynamic programming. But you explained it really well my friend.
nice
One
(Back To Back SWE)
video per day keeps tushar roy away !🤣🤣🤣
hahaha CALM DOWN
Respect for both, for the lack of good dynamic programming videos, Tushar pioneered it well imo. Ben is teaching it better with the intuition behind things, can’t deny that either :)
@@abhimishra2276 what's wrong with them?
@@abhimishra2276 abdul bari is good
@@ritwik121 yes bro i was so wrong he is amazing
I can see the amount of effort you've been putting on your videos. This is what I had been looking for the last 2 years. I feel very lucky that you started making videos before I graduate.
dang...that's a long search hahaha, and thanks haha...more are a comin'
@@BackToBackSWE looking forward to all of 'em!
@@krishnakrmahto97 nice
You are the best mentor that I've ever seen in my life. You can even make a fool understand the complex concepts. (y) keep up the work bro :)
hahaha, u gonna be a genius
These videos are the best I've seen on algorithms/problem solving on UA-cam. Not code walkthroughs or dry mathematical proofs just the facts!
thx!
One of the best explanations for this problem on the internet. ❤
By far the best explanation of the egg drop problem I have come across.
thx
how easily i understood that tough problem signifies that level of teaching of ben...he has fabulous teaching skills.
thanks
Watched so many videos about this problem and got confused, this video made everything clear!
nice
I couldn't believe this amazing channel only has 13K subs.
Aw, thanks. I work pretty hard on this. I hope it grows. I've put my life into this.
@@BackToBackSWE It is the greatest channel that I have found out...Thanks a lot...
I know you have your own plan, but I have a suggestion.
Recently I started learning 'parametric search' and I find it tricky.
-> what is the proper condition to be put in "while( )" ???
-> when do I put '=' on "if (K < mid)", and when do I put '=' on "if (mid < K)" ???
I don't wanna break your pace, just wanted to give you an idea. thx!
Not familiar with parametric search. Is it related to binary search?
@@BackToBackSWE I heard it is highly relevant to binary search. I found some example questions, I'll add the links here.
Question 1 ) hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf -- Question #2 (It starts with the sentence "Lumberjack Mirko needs to chop down M metres of wood....")
Question 2 ) www.acmicpc.net/problem/3703
Question 3 ) poj.org/problem?id=3273
I think I can solve above questions applying binary search... Do you agree? Or any better method to solve them???
Thank you, Lord. Finally found a video that can help. I wish I had this person teaching my algorithm class instead of my prof who looks at her notes and talks to the board.
Hahahahahaha. Yes.
I Really like the way how you're explaining the problem thoroughly
thx
Replace egg with ball and this video becomes much more fun to watch
Haha! great idea
Sir, you're one of the best algorithm teachers I've ever seen! Your explanations are really fascinating!
Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
I have been trying to understand this problem through many YoutTubers,but lemme tell you Sir, this is the best explanation I had. Keep the work up Sir.
thank you. stay around. we got a long road ahead
@@BackToBackSWE
Yes, sir I will.
@@UnseenVivekC haha ok
I don't where you are these days, when I was fresher I learnt from your videos.
Now I have experience of 3 years and I am still learning from you.
Am I in love with you ?
😜
Where are the codes dude, we really need them.
Ps: you’re a life saver, keep going ✌🏻💙
thanks and we only maintain code on backtobackswe.com
Here's the code link:
ua-cam.com/users/redirect?q=https%3A%2F%2Fgithub.com%2Fbephrem1%2Fbacktobackswe%2Ftree%2Fmaster%2FDynamic%2520Programming%252C%2520Recursion%252C%2520%2526%2520Backtracking%2FEggDrop&redir_token=QUFFLUhqbnQ3T2tXamxoVTh5c205TlJCYjZCYmZsOWNjZ3xBQ3Jtc0trODRCQlRicjVIbXh0dXk5VEhrel9QQkZUNXFRamMzSVdablYxLUE5aVk3RGxrRUFOMjNTQkRWSk1qeFlrcVk1cEVIUU51b3E5X3dtSXh2M0FGcmxPY0ZiUFU5eTU4YjhuMDZYckl3YXNDeTQ2UFJIQQ%3D%3D&event=comments&stzid=UgzKhQ0U7vTf35sZifd4AaABAg
Its my first time watching your video and I gotta tell it "MAN U HAVE EARNED MY RESPECT" seriously man can just emphazize on how much easy u did this to me . .
Just a single problem ... ur code link redirects to a page not found ... look up for that
Thanks and got it
Thanks for the detailed explanation :
// if egg breaks then egg-1 and floor -1 ==> dp[e - 1][k - 1]
// else no change in egg count and remaining floors which is f-k ==> dp[e][f - k]
// k means which floor we are in -- > first floor , second floor
// 2 Eggs -> 3 Floors
// • 2 Eggs -> lets try from 1st Floor-> 1,0 ,, 2,2
// • 2 Eggs -> lets try from 2nd Floor -> 1,1 ,, 2,1
// 2 Eggs -> lets try from 3rd Floor -> 1,2 ,, 2,0
I want to see you and Tushar in one frame 😂. Anyways amazing explanation as always .
ok
Your teaching are very clean and understandable ,I am glad to get a teacher like you in my journey of career.You deserve more subscribers.Good luck ,keep it up!🌈✨
thx!
I want to thank you sir for you really put in so much effort into these videos.I like the fact that you provide links to other channels too ( Like Tushar Roy etc).
yeah haha, this is meant to be a resource of many
I know this would be a difficult one to make, but you should make a video going over techniques for identifying overlapping subproblems and optimal substructure in DP problems in general. Pulling from examples like this and longest non-decreasing subsequence (and your other vids). Basically, abstracting the problem specific examples and giving some practical tips for how to identify subproblems.
Fingers crossed xD
ok
after watching several videos on this topic, this video proved out to be the best as always. explanations were very clear although the hiccup in the end disrupted the flow.
thx
My GUY!!! You are brilliant! I will invest my tuition to a service you provide. Take my money!
I am almost in tears for how good this is explained
These have to be some hard ass eggs man.. Thanks for the lucid explanation bro..
ye
It's very clear that you have put in a lot of effort to come up detailed explanation. Thank you keep up the good work.
thanks
Thank you so much for your effort. You can't even imagine how much these help.
nice
Too good bro! Dead camera was a bummer but great explanation!
haha
Great clarification of the problem!! This was my 3rd vdeo for the egg problem and now i am satisfied!
great
good video. I was with you until min 20:47. Why do you have drop (2,1) in addition to drop (2,2). I get the 2,2 one, but since 2 eggs,1 floor cell was a 1, why that one ?
I fudged making that part clear - I remember this vividly, I'd go in and explain but I'm rapid fire responding to 250 comments I got backed up after 2 weeks
In the case (2,1), you are on the Floor 1,just by using one egg, you would know which floor is the "won't break"(I will use F below) floor. If the egg breaks on Floor 1, then "F" floor will be Floor 0. Otherwise will be Floor 1. Only Floor 1 and Floor 0 are to be discussed in case(2,1). totalFloor = 1 is a base case, no matter how many eggs there are, the answer is always 1.
The diagram starting at 12:52 was a bit misguiding the first time I saw it, because the first 6 tree levels don't represent the same thing as the second pairs of "possibilities". In reality, the solution for just one of the subproblems (e.g. 5F, 3E in this list) needs to iterate again through simulations for all 5 floors (with both break/non-break possibilities). And then each of those smaller subproblems again needs to iterate through a bunch of floor-egg pairs. This is where the (F, E) pairs begin reappearing and the memoization (caching) of the subproblems leads to DP.
One useful way of looking at it is to realize that the solution to (4F, 3F) is the same regardless of whether we are considering top 4 floors or bottom 4 floors - it doesn't matter and we will end up calculating them twice unless we cache them or use DP to get them ahead of time.
Hey - I dont remember this problem enough to answer this, shot this a while back
Great explanation!!
Egg Drops, from floor’s and not breaking its unsettling though!! Going to think of it as Coconut Drop 😐
Keep up the good work and keep making our life easier!!
ok
Hey great video, just a quick question, why is it that the minimum amount of egg drops for n floors is n? Wouldn't it be log(n) times since we can do sort of a binary search where we drop an egg from (n/2)th floor and if it breaks we know every egg dropped from above that floor will break and if it doesn't break we know that every egg dropped from below that floor won't break ?
We can do it logarithmically, that is the next best solution. I just presented the base solution that someone could practically come up with in an interview.
@@BackToBackSWE I see. Can I ask you just one more question? Why is it that we want the worst outcome of the drops, that is max(drop(eggs, totalFloor - currentFloor), drop(eggs - 1, currentFloor - 1)) ? This part still doesn't seem to click in my head.
@@ChainForLife Never limit questions. Always ask questions until you understand. Push the teacher as well as yourself because I don't know it all...or else we both learn nothing.
So think about this....our goal is to tell the caller the SMALLEST amount of drops so that I can PROMISE that in those drops...I will find the pivotal floor. If I don't account for the worst outcome of drops...I could be lying...my promise could be broken.
I have to take into account the WORST outcome and BOUND my drops to that because it promises that I find the pivotal floor in that amount of drops NO MATTER WHAT CASE happens. Does that make sense?
@@BackToBackSWE Yes sir, that last sentence pretty much made it crystal clear for me.
@@ChainForLife Ok, cool, haha don't "sir" me...I'm just a dude...a normal guy.
Thanks a lot, BTB SWE for crystal clear explanation, I always think in a Top to Down DP approach but always got confused in Bottom Up DP. Can you people make another separate video for thinking ina bottom up DP please?
Yes. I will address this in a video similar to this: ua-cam.com/video/Zq4upTEaQyM/v-deo.html one day. Don't worry, as long as this project stays active I will cover what people want to see.
Your channel is great and really helping me with learning and understanding Dynamic Programming.
I wanted to know, can this problem be solved optimally using Jump Search Algorithm?
thanks and not sure, I've never heard of Jump Search
www.google.com/amp/s/www.geeksforgeeks.org/jump-search/amp/
best explanation to this problem so far
thanks
I really like the way you teach, with so much clarity and to the point... Keep going 💪 Thankyou
thx
MISTAKE (always droop from the middle if you have more than one egg):
There is a fundamental logical MISTAKE and while it does not affect the result, it does simplify the solution when realized. See:
If you have more than one egg, you can start drooping the first egg from any of the N floors. So, you evaluate the cost of dropping from each floor and stay with the floor that yields the minimum cost (min).
But when you think better, that is completely unnecessary: you don't need to evaluate all the floors, because the middle floor will always yield the minimum drooping cost. Always!
Now, depending on N (even or odd), the middle floor might or might not have an equal number of floors above and below. When it does not, you stay with the worst case scenery: solve the problem with more floors (max).
Applying this logic, you eliminate the min operation that evaluates all possible floors (go always with the middle) and the solution to the problem cuts down as follows:
def eggs(N,e):
if e==1:
return N
if N==1:
return 1
mid=math.ceil(N/2)
if (N-mid)>(mid-1):
return eggs(N-mid,e)+1
else:
return eggs(mid-1,e-1)+1
Explanation of the middle selection: Suppose you have 100 floors and just 2 eggs. You droop the first egg from 99: in the best case it does not break and with the remaining egg you scan the only floor left, the floor 100 (the one above you). So the best case is 2 droops! But in the worst case (it did not break), you have to scan 98 floors below you one by one with the only remaining egg. This makes 98 droops for the worst case. Thus, you are risking a lot (too much difference between the best and the worst case, and you don’t know what the case will be). So:
99: 2 (best)-98(worst)
98: 3(best)-97(worst)
97: 4(best)-96(worst)
.
.
4: 4(best)-96(worst)
3: 3(best)-97(worst)
2: 2 (best)-98(worst)
Look! When you go downwards the risk reduces (the difference between best and worst case tends to zero) but, it happens like that also when you go upwards. So, in the middle point the risk will be near zero (depending of N being even or odd). But, in any case, the middle point (as Buddha said) will always be the most neutral or best option to droop any time you have more than one egg (the one with minimum cost).
chill
@@BackToBackSWE Be aware that this reduces the problem to Logn time. I havent seen aneyone giving this solution, it seems I am the fisrt person realizing it
I got my first job ( 18 lpa ) all coz of your videos.... Thanks a lot dude .. keep helping people ❤️
nice, best of luck internet friend
@@BackToBackSWE thank you so much 🤩🤩
@@waxylayer8353 Hey bro, Are you a Tamilian?
@@lokeshsenthilkumar4522 yes
Great job, you deserve more subs than most others who do these type of videos. However, can you go in depth a bit on what you'd need to simulate all of the floors? Why can't you just start branching from 6 floors, 3 eggs?
We do. To solve the subproblem you just stated:
drop(3, 6) -> we need to imagine, just imagine...that we start dropping from floor 1 with 3 eggs, floor 2 with 3 eggs, floor 3 with 3 eggs, floor 4 with 3 eggs, etc.
At each simulation, we want to know the 2 possibilities. What do they yield in terms of worst drops.
This is how we converge to base cases.
Now, to your question. Why simulate? Well...what was the original question: "You are given n eggs and specified a number of k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break."
How can I know FOR SURE...for sure...the MINIMUM # of drops to find the pivotal floor? Well for the solution presented (and there are others) we do a test from each floor and find the WORST performer.
This worst performance is a possible reality. We must account for it.
And thus, we take this worst reality/outcome AFTER DROPPING.
After dropping.
If we miss out on any simulation we will miss a possible outcome that may worsen our worst case.
This brings me to why we add 1. The +1 is because we want to say that "The answer where I stand is the action I take, plus the result of the worst outcome that follows."
the action. A drop. +1 to the worst case drops.
the result. That is the worst subproblem result that happens after our action.
I could keep going but check the code in the description.
Keep asking questions. I have answers...most of the time.
Here's another way to look at it: think about every call to drop(eggs, floor) as literally throwing one of your eggs down from the chosen floor. So if you computed drop(3, 6) by only considering the 6th floor (instead of testing all the floors), what you are saying is - what is the minimum number of times I need to throw eggs off of floors to find the first floor it breaks... *given that you threw your FIRST egg off the 6th floor?* As you can imagine, we might be able to reduce the number of drops in the worst case by dropping the FIRST egg off, say, the third floor - (drop(3, 3)) - if it breaks, you've eliminated the top half of floors, and if it doesn't, you've eliminated the bottom half (had we just thrown it off the highest floor each time, if the egg breaks, we would have only eliminated one floor; if the egg broke from that floor, only one more floor, and so on). Of course, we don't really know which floor to drop off first to minimize the number of drops, so we try each floor. This reflects the floor we should throw our egg off first!
@@Maholain Thank you, and thank you both. :)
@@FloShaban I still feel like I could've made it clearer...oh well. There are better solutions but I just covered the most basic solution one would realistically get with previous dp experience.
If looking at finding floor is like finding an item in an array, then it will be an easy math calculation of
if (eggs == 1) return floors // "floor by floor method"
if (eggs >= log(floors)) return log(floors); "simple binary search"
else // this is a mix of the two approaches - we want to start a binary search until we have one egg left.
divide the floors by 2 and assume the egg will break in every test.
do this until we have the chunk size we have to go with the "floor by floor" method and drop.
so overall it's the amount of dividing by 2 we can do + the size of the chunk that is left
also, this - while can probably be improved to a single formula but you said at the end of the video no hard math
time = O(log(eggs))
space = O(1)
I really wonder what am I missing here
Im not sure I dont remember anything in this video
Watched it while on the treadmill, nicely explained, just wish your cam didn't die
lmao nice
Eggs will break even if you drop them from floor 0 because they break even if you drop them from 10 cm above a hard surface - solved , 0 eggs dropped.
When the egg doesn’t break, why do we go for [ totalfloor - simfloor ] instead of [ simfloor + 1 ] ???
It expresses the # of floors above where we dropped. Think on this.
Example 1:
6
5
4
3 (drop here)
2
1
0
simFloor = 3
I drop at 3. No break. I go up. Do I have 6 - (3) = 3 floors above me?
Or simfloor + 1 = (3) + 1 = 4 floors above me?
Example 2:
6 (drop here)
5
4
3
2
1
0
simFloor = 6
I drop at 6. No break. I go up. Do I have 6 - (6) = 0 floors above me?
Or simfloor + 1 = (6) + 1 = 7 floors above me?
Check the code in the description. Really internalize it.
Hmm... interesting. Thank you very much for your explanation :)
@@raymondyoo5461 I think I could've done better with this, oh well. Just keep thinking on it if you still don't 100% understand it.
@@BackToBackSWE Yeah, I searched other videos or blogs, and I just saw 99% similar explanation to yours. I hope I can come back here later and I clearly understand this.
@@raymondyoo5461 Yeah, time helps as you see more dp problems. It is a specific way of thinking. When it does click it will be interesting.
What is still unclear? If I may clarify it.
Agreed on not bothering with math. No sane person could come up with one of those in 20-25 min
There are very smart people that theoretically could. It is just that I don't think there are enough of those high powered individuals to make it worth it to get that good at niche problems you may get (and lose to them in).
Time is better spent on larger problem sets.
Question: Would this problem also be solved by a piecewise function of binary and linear search where you do binary search until eggnum == 1, then do linear search from the minpointer to the maxpointer?
If I’m right and this is the case, the runtime complexity should be O(Height)/Θ(log(Height)), and space complexity O(1)?
Also, pretty good job explaining the question in terms of DP. :)
I don't know but I really like watching your videos. Feels so much satisfaction.
thanks
Thank you very much for these videos, they are really great. I seriously have no words to express my gratitude for these wonderful videos. Great job !
Say no words, let it be :) As a wise man once said:
"Let it be, let it be, let it be, let it be
There will be an answer, let it be" - Wayne Gretzky
Great video, but I really think that you should do binary search instead of going one floor up and down, would be much less drops and much more saved eggs :)
yeah that is the better approach.
@@BackToBackSWE I understand that you didn't do binary search for simplicity, but I think at least mentioning it as possible optimization would open some eyes. Keep the good work!
where is the link to your code?
why is it that we take the min of WORST CASE? what does WORST CASE represents here? The Maximum no of attempts that you can do at given floor without breaking the egg
The worst-case can happen so we must account for it. We want to know the best we can do given the worst case.
Can't find the code in the description. Also, not available on the site. :(
finally I am beginning to understand the problem!!
You are really gr8, thanks sir! I hope you do Great things in life! Respect
sure thx
at 20:50 You said that the answer is the one who do the worst but I think it minimum of "all the worst case possibilities at each floor" for a corresponding (eggs and floors)
yes
Thanks for your perfect explanation!But for your code, I have one question. Why do you plus one here " int accountingForDroppingAtThisSubproblem = 1 + costOfWorstOutcome;" You mentioned that you were doing a test.Can you explain the test clearly?I'm feeling quite confused.
The +1 denotes dropping an egg then solving the remaining subproblems passing the resulting state change to the next call
@@BackToBackSWE Thx!
@@jomosis9234 sure
One of the best explanation.
Thank you, sir!
thanks and sure
Awesome explanation !! Thank you so so much!
sure
You always say that the code is in the description but I never see it? Did this get moved to your subscription service? Either way thanks!
Hey, we had a public repository and we have deprecated it and only maintain backtobackswe.com from now on
unsubscribed
@@BackToBackSWE okay gotcha i found it and thanks again!
Hey, thanks for the explanation! The cases where the egg breaks seems logical, but I don't get the case where the egg doesn't break. If the egg doesn't break on floor 5 why i can use the function for 6-5 = 1 floor? When the egg survives the fall from floor 5, it must also stay unharmed when dropped from floor 1...
everything is okay..
but when saying if egg breaks on floor 4 we go down to floor 3 you could say that if the egg breaks on floor 4 we are left to check 3 floors because its not the n'th floor rather the total number of floors as argument in drop function...
This is the most explaination of this type of dp :>
Why don't we use a binary search for egg 2~n to narrow down the last egg searching range?
What I mean is
Assume we have 2 eggs and 6 floors
drop(2,6)
We fist try to drop an egg at the 3rd floor
If it break, then search from 1 to 2
drop(1,2)
If it doesn't break, then search from 4 to 6
drop(2,3)
= 1 + Math.max(drop(1,2), drop(2,3))
Whenever number of eggs > 1, the sub problem can be
drop(eggs, floor/2) and drop(eggs-1, floor/2 -1)
that was hilarious LOL..my cemera died
yeah it did
Hey amazing explanation!!! BTW where is the code !?
Hi, the code is maintained on www.backtobackswe.com
Where is the code , please help me to find it...
Best explanation ever!
Commendable explanation !
Dude finally you are not shouting at me. Btw bro great video ❤️
lol and thanks
If the total numbers of eggs are 1, then why are we returning total floors? It may be the case that we don't need to get to the top floor and before that we get the pivotal floor
I dont remember this problem to be honest
@@BackToBackSWE lmao
The n^2*k dp solution as discussed in the video is giving tle on leetcode after 80 test cases or so!
yes
Hey, can you make a video for O(K*log N) approach?
Right now cannot but would if I had the time
Update: When he says the least amount of eggs that you will ever drop, He means to say the least number of egg drops (moves) that one will ever that guarantees for a pivotal floor p; dropping an egg from p + 1 breaks and any floor (
Why cannot we approach the problem in a binary search manner? That would reduce the time a lot. So we wouldn't find the sub problem for +-1 floor, but we'd either half the floor towards the ground or towards the top.
yes you can do that
brother, YOU MUST MAKE A VIDEO ON MANACHER"S ALGORITHM!No video is enough clear. Please make one ASAP
Can't right now
Did u find one?
I’m definitely misunderstanding the question because with one egg, couldn’t you just start at floor 0 and go up until it breaks, therefore solving this in O(totalFloors) time? What is the advantage of having more than one egg? What am I missing?
I dont remember this video nor the question
Anyone else have an answer?
Why drop(2, 1) when we already know the answer to that???
At 20:59
When we want value for drop(2,2) ,
then,
Why do we simulate sim(2,1) & sim(2,2) .
we are solving for is 2 (which is 'totalFloors') floors and 2 (which is 'totalEggs') eggs. We are doing 2 simulations: sim(2, 1) (2 eggs, start from floor 1) and sim(2, 2) (2 eggs, start from floor 2).
why not just sim(2,1) ?
beacuse sim(2,2) is bad choice... right ?
"why not just sim(2,1)?" If we just do one of the simulations (and not all of them) we may miss a case that would've yielded a truer bound to the worst amount of eggs that would need to be dropped to ensure we find the pivotal floor. For the approach in the video (and it is not the most optimal approach), we have to run all simulations to ensure our upper limit is correct with such a guarantee.
Nice explanation man!
Loved your video. Thank you so much.
Where is the code? Am I mistaking the place where the description is supposed to be?
The code never in the description 😁
I am unable to find the implemented code in description .Where should i be looking?
very good and detailed explanation , thank you !
sure
Wow Thanks for the explanation man!
sure!
not sure if you will see this but the link for code is broken here.
I see every comment and I dont have time to fix it. I restructured the repo
Thank you very much
sure
Adding the recurisve function would make it perfect
yes
where is the link for the code it not in description.
The repository is deprecated - we only maintain backtobackswe.com now.
I love your channel but you have not posted in a while. If you do get time, would you be able to do Two city scheduling problem? It is a dynamic programming problem. :)
Hey, we have been working on a huge platform in the past 3 months. It launches in 2-3 weeks.