Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition

[@BackToBackSWE]

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.

[@fpv_am]

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!

[@BackToBackSWE]

yeah

[@BackToBackSWE]

hahahaha nice

[@monil1601]

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 ?

[@BackToBackSWE]

@@monil1601 I don't remember

[@ahmedboutaraa8771]

your channel is like a NETFLIX of DS & algorithms. whenever i try to watch one of your videos i found 10 more intriguing ones

[@BackToBackSWE]

haha nice

[@chanman123]

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!

[@BackToBackSWE]

I have to feed the family. Everyone eats. Otherwise, I'm starving.

[@airysm]

These are some strong ass eggs

[@BackToBackSWE]

agreed

[@raymondyoo5461]

LOL

[@kuralamuthankathirvelan]

One (Back To Back SWE) video per day keeps tushar roy away !🤣🤣🤣

[@BackToBackSWE]

hahaha CALM DOWN

[@karthikrangaraju9421]

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

[@anunaysharma2718]

@@abhimishra2276 what's wrong with them?

[@ritwik121]

@@abhimishra2276 abdul bari is good

[@abhimishra2276]

@@ritwik121 yes bro i was so wrong he is amazing

[@chaitanyapvs4150]

Its nice to find a video explaining way of approach rather than repeating the dp tables from solutions.Thanks man.

[@BackToBackSWE]

sure

[@itsrahulraj]

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

[@studgaming6160]

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.

[@BackToBackSWE]

nice

[@rakeshsinha9541]

I Really like the way how you're explaining the problem thoroughly

[@BackToBackSWE]

thx

[@chetansahu1505]

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

[@BackToBackSWE]

hahaha, u gonna be a genius

[@krishnakrmahto97]

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.

[@BackToBackSWE]

dang...that's a long search hahaha, and thanks haha...more are a comin'

[@krishnakrmahto97]

@@BackToBackSWE looking forward to all of 'em!

[@BackToBackSWE]

@@krishnakrmahto97 nice

[@shashikantpunia9019]

how easily i understood that tough problem signifies that level of teaching of ben...he has fabulous teaching skills.

[@BackToBackSWE]

thanks

[@raymondyoo5461]

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]

Not familiar with parametric search. Is it related to binary search?

[@raymondyoo5461]

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

[@martinberridge9173]

These videos are the best I've seen on algorithms/problem solving on KZbin. Not code walkthroughs or dry mathematical proofs just the facts!

[@BackToBackSWE]

thx!

[@tanvirarjel]

One of the best explanations for this problem on the internet. ❤

[@zehrasubas9768]

Watched so many videos about this problem and got confused, this video made everything clear!

[@BackToBackSWE]

nice

[@erichlf]

By far the best explanation of the egg drop problem I have come across.

[@BackToBackSWE]

thx

[@meemee417]

cant believe it took me this long to just realize that its just break and not break on every floor lol. this video helped me pull the pieces together

[@dongshuowu3454]

I couldn't believe this amazing channel only has 13K subs.

[@BackToBackSWE]

Aw, thanks. I work pretty hard on this. I hope it grows. I've put my life into this.

[@bddyonetim539]

@@BackToBackSWE It is the greatest channel that I have found out...Thanks a lot...

[@Ashish-_-]

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

[@BackToBackSWE]

yeah haha, this is meant to be a resource of many

[@al-farouksaleh2144]

Where are the codes dude, we really need them. Ps: you’re a life saver, keep going ✌🏻💙

[@BackToBackSWE]

thanks and we only maintain code on backtobackswe.com

[@rashim]

Here's the code link: kzbin.info?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

[@hamidurrahman3183]

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.

[@BackToBackSWE]

Hahahahahaha. Yes.

[@ankitgoyal8556]

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

[@tastypie2276]

Sir, you're one of the best algorithm teachers I've ever seen! Your explanations are really fascinating!

[@BackToBackSWE]

Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

[@UnseenVivekC]

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.

[@BackToBackSWE]

thank you. stay around. we got a long road ahead

[@UnseenVivekC]

@@BackToBackSWE Yes, sir I will.

[@BackToBackSWE]

@@UnseenVivekC haha ok

[@thanga2317]

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

[@norbertnemesh]

Replace egg with ball and this video becomes much more fun to watch

[@BackToBackSWE]

Haha! great idea

[@Pickyricky69420]

My GUY!!! You are brilliant! I will invest my tuition to a service you provide. Take my money!

[@overclockinggames2419]

I want to see you and Tushar in one frame 😂. Anyways amazing explanation as always .

[@BackToBackSWE]

ok

[@Kasfas]

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

[@shahar7]

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

[@BackToBackSWE]

Im not sure I dont remember anything in this video

[@yashshreeshinde4394]

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!🌈✨

[@BackToBackSWE]

thx!

[@cristianouzumaki2455]

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.

[@BackToBackSWE]

thx

[@MyGroo]

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.

[@BackToBackSWE]

Hey - I dont remember this problem enough to answer this, shot this a while back

[@ChainForLife]

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 ?

[@BackToBackSWE]

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.

[@ChainForLife]

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

[@BackToBackSWE]

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

[@ChainForLife]

@@BackToBackSWE Yes sir, that last sentence pretty much made it crystal clear for me.

[@BackToBackSWE]

@@ChainForLife Ok, cool, haha don't "sir" me...I'm just a dude...a normal guy.

[@MMOlocation]

Thank you so much for your effort. You can't even imagine how much these help.

[@BackToBackSWE]

nice

[@prabhpreetsingh5341]

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

[@BackToBackSWE]

Thanks and got it

[@aamirjamal6833]

These have to be some hard ass eggs man.. Thanks for the lucid explanation bro..

[@BackToBackSWE]

ye

[@codetolive27]

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.

[@BackToBackSWE]

thanks

[@priyanktewari8841]

Too good bro! Dead camera was a bummer but great explanation!

[@BackToBackSWE]

haha

[@MithleshKumar-iz1dz]

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?

[@BackToBackSWE]

Yes. I will address this in a video similar to this: kzbin.info/www/bejne/kKKXpqOKesaEr68 one day. Don't worry, as long as this project stays active I will cover what people want to see.

[@tejasghone5118]

Great clarification of the problem!! This was my 3rd vdeo for the egg problem and now i am satisfied!

[@BackToBackSWE]

great

[@karmavadaa]

Great explanation!! Egg Drops, from floor’s and not breaking its unsettling though!! Going to think of it as Coconut Drop 😐

[@markfishman5242]

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 ?

[@BackToBackSWE]

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

[@jomosis9234]

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.

[@mrinaldhawan3959]

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?

[@BackToBackSWE]

thanks and not sure, I've never heard of Jump Search

[@mrinaldhawan3959]

www.google.com/amp/s/www.geeksforgeeks.org/jump-search/amp/

[@matthewbuchholz5251]

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

[@BackToBackSWE]

ok

[@allezzthepunk]

I am almost in tears for how good this is explained

[@faridashaikh9773]

I really like the way you teach, with so much clarity and to the point... Keep going 💪 Thankyou

[@BackToBackSWE]

thx

[@vibekdutta6539]

You are really gr8, thanks sir! I hope you do Great things in life! Respect

[@BackToBackSWE]

sure thx

[@sauravdas7591]

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

[@BackToBackSWE]

The worst-case can happen so we must account for it. We want to know the best we can do given the worst case.

[@hoelefouk]

Keep up the good work and keep making our life easier!!

[@BackToBackSWE]

ok

[@waxylayer8353]

I got my first job ( 18 lpa ) all coz of your videos.... Thanks a lot dude .. keep helping people ❤️

[@BackToBackSWE]

nice, best of luck internet friend

[@waxylayer8353]

@@BackToBackSWE thank you so much 🤩🤩

[@lokeshsenthilkumar4522]

@@waxylayer8353 Hey bro, Are you a Tamilian?

[@waxylayer8353]

@@lokeshsenthilkumar4522 yes

[@varunagarwal5189]

best explanation to this problem so far

[@BackToBackSWE]

thanks

[@ruchadeodhar1708]

Awesome explanation !! Thank you so so much!

[@BackToBackSWE]

sure

[@ShaliniNegi24]

One of the best explanation. Thank you, sir!

[@BackToBackSWE]

thanks and sure

[@jomosis9234]

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.

[@BackToBackSWE]

The +1 denotes dropping an egg then solving the remaining subproblems passing the resulting state change to the next call

[@jomosis9234]

@@BackToBackSWE Thx!

[@BackToBackSWE]

@@jomosis9234 sure

[@vaibhavlodha5398]

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 !

[@BackToBackSWE]

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

[@palashkamble2325]

Hey, can you make a video for O(K*log N) approach?

[@BackToBackSWE]

Right now cannot but would if I had the time

[@FloShaban]

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?

[@BackToBackSWE]

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.

[@Maholain]

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]

@@Maholain Thank you, and thank you both. :)

[@BackToBackSWE]

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

[@chakshujain7557]

I don't know but I really like watching your videos. Feels so much satisfaction.

[@BackToBackSWE]

thanks

[@Qrzychu92]

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]

yeah that is the better approach.

[@Qrzychu92]

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

[@raymondyoo5461]

When the egg doesn’t break, why do we go for [ totalfloor - simfloor ] instead of [ simfloor + 1 ] ???

[@BackToBackSWE]

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.

[@raymondyoo5461]

Hmm... interesting. Thank you very much for your explanation :)

[@BackToBackSWE]

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

[@raymondyoo5461]

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

[@BackToBackSWE]

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

[@vman049]

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?

[@BackToBackSWE]

I dont remember this video nor the question

[@vman049]

Anyone else have an answer?

[@shubhamdubey2283]

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)

[@BackToBackSWE]

yes

[@Skaguc]

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

[@architranjan9]

The n^2*k dp solution as discussed in the video is giving tle on leetcode after 80 test cases or so!

[@BackToBackSWE]

yes

[@adnanmasroor742]

finally I am beginning to understand the problem!!

[@Dal.alef.]

Watched it while on the treadmill, nicely explained, just wish your cam didn't die

[@BackToBackSWE]

lmao nice

[@cautioni]

where is the link to your code?

[@ckfun1skf]

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)

[@akshatsamdani]

Can't find the code in the description. Also, not available on the site. :(

[@sahilk335]

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 ?

[@BackToBackSWE]

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

[@chandnibhatia1211]

Hey amazing explanation!!! BTW where is the code !?

[@BackToBackSWE]

Hi, the code is maintained on www.backtobackswe.com

[@Md.DillshadulIslam]

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

[@kwanji.feb2]

This is the most explaination of this type of dp :>

[@jiradetounjai8307]

Thank you for the very clear explanation. I am confused that when an egg does not break we go up (totalFloors - currentFloor), but at 21:35, why totalFloors is 2 instead of 4 as shown in the table.

[@BackToBackSWE]

Our subproblem we are solving for is 2 (which is 'totalFloors') floors and 2 (which is 'totalEggs') eggs. We can do 2 simulations: sim(2, 1) (2 eggs, start from floor 1) and sim(2, 2) (2 eggs, start from floor 2). Where is 4 coming from?

[@JuanGomez-uu6wf]

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]

chill

[@JuanGomez-uu6wf]

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

[@vaibhavsinha2728]

Where is the code , please help me to find it...

[@gurtagel]

Agreed on not bothering with math. No sane person could come up with one of those in 20-25 min

[@BackToBackSWE]

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.

[@anthonytonev1357]

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.

[@vedantverma5185]

Commendable explanation !

[@CsabaTothMr]

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.

[@BackToBackSWE]

yes you can do that

[@rati396]

very good and detailed explanation , thank you !

[@BackToBackSWE]

sure

[@anmoljhanwar5843]

I am unable to find the implemented code in description .Where should i be looking?

[@vijay6877]

Loved your video. Thank you so much.

[@amartyamishra6961]

Where is the code? Am I mistaking the place where the description is supposed to be?

[@안광훈-x3p]

Best explanation ever!

[@ayanbizz]

How was drop (2,2) , broken into sub problems of drop(2,1) & drop (2,2) ? Shouldnt the sub problem be drop (2,1) & drop(1,2) ?

[@BackToBackSWE]

I don't remember this video well enough to reply to this but I saw this and appreciate u watching

[@demidrek-heyward]

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!

[@BackToBackSWE]

Hey, we had a public repository and we have deprecated it and only maintain backtobackswe.com from now on

[@dnield]

unsubscribed

[@demidrek-heyward]

@@BackToBackSWE okay gotcha i found it and thanks again!

[@kartikaygoel3042]

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

[@BackToBackSWE]

I dont remember this problem to be honest

[@silverzero9524]

@@BackToBackSWE lmao

[@caseyschneider1974]

What would the complete dynamic programming table look like in the example?

[@BackToBackSWE]

it is filled out in the video?

[@caseyschneider1974]

Back To Back SWE your camera dies at 22:06 before you’re able to finish filling out the last 6 cells

[@tirthjayswal9895]

that was hilarious LOL..my cemera died

[@BackToBackSWE]

yeah it did

[@gurleenkaur5786]

Can binary search be applied to this problem..like in this particular ques..try the middle floor i.e 3rd floor..if the egg does not break then consider only 3-6 floors and check on mid..let's say 4th floor..otherwise check on 0-3 floors..can it be done this way?

[@BackToBackSWE]

yes

[@TheDEMMX]

@@BackToBackSWE Thank you for your videos. I thought about binary search too, why DP if we can use binary search. The worst case is a function of floors only, not the eggs. Then at the end, you either have enough eggs or you don't? Or am I missing something in the problem statement?

[@vicliur2]

Wow Thanks for the explanation man!

[@BackToBackSWE]

sure!

[@ihtemad]

brother, YOU MUST MAKE A VIDEO ON MANACHER"S ALGORITHM!No video is enough clear. Please make one ASAP

[@BackToBackSWE]

Can't right now

[@reassume4826]

Did u find one?

[@Blixy95]

Adding the recurisve function would make it perfect

[@BackToBackSWE]

yes

[@techbarikcom]

The code never in the description 😁

[@anonymousvoid6356]

Nice explanation man!

[@VocalWithShubham]

Hi Benyam, I just want to say that can you make a video that explains the optimal version of this algorithm with takes O(totalEggs*totalFloors) time or any lesser time because this code showing TLE in interviewbit and leetcode as they both have large input constraints. I can't able to understand their solution and also there is no video that explains that optimized solution.

[@BackToBackSWE]

I currently cannot due to time constraints Im sorry

[@bruriahassidim8369]

Thank you very much for these videos really helpful! just one question. I get it when we have one egg, so we just go one floor upwards at each time and if it breaks we know it's one floor below but how does having more eggs help me? am I throwing from a few more floors at the same time? I am missing something

[@BackToBackSWE]

A few more eggs would allow us to not have to drop every floor up to the breaking floor