Egg Dropping Problem Dynamic Programming | Leetcode Hard Solutions
Вставка
- Опубліковано 12 вер 2024
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this problem, we discuss the egg dropping problem using dynamic programming. In this problem,
1. You are given two integers N and K. N represents the number of eggs and K represents the number of floors in a building.
2. You have to find the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.
3. The critical floor is defined as the lowest floor from which you drop an egg and it doesn't break.
4. There are certain which you have to follow -
a. All eggs are identical.
b. An egg that survives a fall can be used again.
c. A broken egg can't be used again.
d. If the egg doesn't break at a certain floor, it will not break at any floor below.
e. If the egg breaks at a certain floor, it will break at any floor above.
To attempt and to submit this question, click here: www.pepcoding....
For a better experience and more exercises, VISIT: www.pepcoding....
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
if you watch starting 10 minutes of this video, you will realize that how he has focused and explained the concept rather than solving the question that other youtubers are doing. Thanks for this video.
Thanks :). If you want more detailed content like this with better experience please sign up on nados.pepcoding.com and also follow us on Instagram for latest updates. instagram.com/pepcoding/
I can bet,
Only video on UA-cam to explain this concept flawlessly.
Most of the UA-camr themselves haven't understood the question
Watch
Aditya Verma video for egg dropping problem 🔥🔥.. 👍
But sumit sir ka toh mukabla hi nahi hai... 🔥
@@nitinkumar5974 usiko dekha pehle,nhi smjh aaya tbhi yha aaya : | , aur yha aane pr to jaante hi ho.... : )
@@theuntoldtree exactly
@@theuntoldtree Same bro
Best explanation ever. Thank you, sir :)
but at 40:22 max of (2,4) will be 4 and mat[2][7] will become 4.
Yes, It's by Mistake
best explanation so far, was struggling to understand the intuition, cleared up so well !!
I was struggling for more than 2 days to understand this problem.15 minutes into this video I understood the problem completely. Thank you for this great explanation.
Glad it helped and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Why I was not aware of this channel before. The way you teach is awesome. I am really grateful for such awesome videos.
This is the best explanation I came across. Watched 4 explanation videos on youtube and this one steals the show. Thank you for sharing this video.
Thank you. Why don't you check out all our content on nados.pepcoding.com?
His efforts🥺 sir ko pta h ki baache video ko dobara dobara dekh k try kr skte hai lekin still he tries his best by repeating many times
Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Sir this solution is not accepting on leetcode, its time complexity is O(n*n*k) and try to use binary search while checking for egg survives or fails, it will reduce complexity to TC-O(n*k*logn)
Log code padhaate hai, aapne concept samja diya. Thank you so much. I don't have much subs but will definitely promote you in my videos!
I am glad. Your kind words are the kind of motivation that truly help me in making more and more content. Especially, these days, not everybody is generous with motivating anybody either. It means a lot.😊
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding Already done!! :-D
Clapps for you Sir ! Thanks for making the concept so easy !
Thankyou beta!
I am glad you liked it. I also hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, Will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Keep learning and keep loving Pepcoding😊
@@Pepcoding sir but this code is giving tle on leetcode
four years of my engineering, never understood this problem till I watched this video. This is gold.
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
And this was exactly what I was looking for! Thank you so much for the wonderful explanation! 😃
Woahhh sir finally egg 🥚 drop problem solution is here ❤️❤️🔥🔥
Great 👍
You are the only capable person right now who actually extracted the real CRUX of the problem and hit that hard with your approach.
No other famous youtubers were able to find out the real crux of problem.
Hats off Sir, This is my sixth or seventh video in UA-cam watching for this particular problem and here I got my final satisfactory understanding of the problem.
keep motivating, keep learning and keep loving Pepcoding😊
yaad krli hai line.
jo apne haath me uska best or jo luck pr depend hai uska worst.
Ye line to zindagi mei bhi kaam aa sakti hai
@@Pepcoding haa sr hmaare haath me prep krna wo krre hai referral lge na lge interview mile na mile ye luck wali baat. jo apne haath me usko best krre hai ..
I generally do not comment on any video but believe me he is just awesome . He is clearing not only question statement but also the depth of concept involved many famous youtubers have not released a video on this topic Hats off to him
The way you explain dynamic problems is far better than others. Thank you sir😁.
This is the bestest explanation of any problem on youtube.
wow.....this is great!!!
sir u r amazing.... u do the post mortem of each problem which helps in building the logics as well
much love sir
thanks for these kind of tutorial.....god bless u :)
So nice of you, I am glad. Keep learning. Keep supporting. Your kind words are the kind of motivation that truly help me in making more and more content. Especially, these days, not everybody is generous with motivating anybody either. It means a lot🙏
Thank you for the detailed explanation.
Can you please also cover a solution with binary search approach with time complexity of O(K*N*logN)
Soon beta.
Bro you save me.... Hats off. I was having problem Optimal Strategy problems. And you cleared my doubts so well. Kudos man. I generally don't comment. But your efforts forced me to appreciate your work!
40:22 maximum value should be 4 else awesome content
Man ,seriously Heads off to your patience and Explanation ,This made my day !!!This is the best explanation and correlating the real world CEO-Manager problem was really cherry on the cake. !!! :)
Very well explained. Kudos to u for putting so much effort!
wonderful explanation I have found in whole youtube. Thank you so muchhhhhhh
Itne simple way me samjhaya hai..... Hats off 🙏
Thankyou beta!
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Keep learning and keep loving Pepcoding😊
The way of explanation. Hats off to you 👏 👏 👏
discovering you late but you are a great teacher. you really put the effort in your video. i can see that.
No one can explain better than you sir. Thanks a lot sir.
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Sir dimag ka dahi ho gya tha...but now the problem is crystal clear.... thanks ❤️❤️
I am getting TLE, Can u please make a video on the optimization of the egg dropping problem?
Use matrix to store ans N*K size
This channel is soo underrated!!!
Very nice explanation sir
Nice explanation sir....thanks a lot for the video....the content on your youtube channel is amazing...
mza aa gya sir , ye best of the worst ka technique game theory mei bhi padha that Maine , aaj pta chala things are related
Glad you enjoyed it :) For more content like this you can visit nados.pepcoding.com
This is my 🙃best of best😅 video on egg droping problem
Thank you sir.
now the whole concept is clear . the part of office project distribution is really concept clearing example..
Thank You so much sir, What an amazing solution. Understand everything
Aree bhaiyaji agg laga di...ande fodne ka estimate k sath placement mein fodne ka estimation acha lgg rha..:wink emoji inserted.
I understood the problem clearly because of you so thanks, and the humor when you said, "jisko samaj ana hoga aa chuka hoga ab tak" hahaa .
Glad it helped!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
Sir, really great explanation, i would just request you to increase the frequency of questions as we have to cover a lot of questions from different topics.
I will try my best
Best explanation with a life lesson 🤩
Best video that explains the concept well.👍
best ever explanation I have seen on UA-cam ❤
I have seen lot of videos on this problem but not able to understand, but this video clears all my doubts. Thank you sumit sir and #pepcoding
Kyaa kamaal padhaate ho aap!! Majaa hi aa gya!!
I can watch these videos the entire day :)
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
thank you so much sir watch only manager question and has gotten the solution of egg dropping
Bow down to king absolutely legend 🙏
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Sir, aapki 4:56 wali baat dil pe lagti hai
For better experience and well organised content visit nados.pepcoding.com
Sir at DP[2][7] there should be 4 because we are calculating the max(2,4) so it will be 4 and the whole max array will becm (3,3,3,3,4,5,6) not [(3,3,3,3,2,5,6)(written in video)]. so the min of max will be 3 and the attempt will be 3+1=4
Good to see new questions added to platform
48:43 kaun sa agla sawal? optimal strategy for a game??
Sir you are God for me...
don't know why so underrated
tagda bhai...appreciate your effort...
great explanation..bt this solution is giving tle in leetcode.
try to use binary search
Sir best of worst k liye maine priority queue(min heap) use kari usse kaafi aadan hua.
Maine Math.max() se queue mai add karte gaya aur end mai peek karke min value le liya
Hats off. You are the best teacher on earth !
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.
@Pepcoding can we treat this as binary search as floors are always sorted and then we directly check at middle of building i.e we can directly return ceil(log2(k)) k-number of buildings and get the and in o(1) time
Did you get the answer to why binary search cannot be applied to this question?
you need to have unlimited eggs for that case
Here is the binary search solution,lc accepted
public int solve(int k,int n,int[][]memo)
{
if(n==0||n==1||k==1) return n;
if(memo[k][n]!=0) return memo[k][n];
int ans = Integer.MAX_VALUE,l=1,h=n;
while(l
sir u explain so great, im enjoying the explanation, how u clear the question as well as the solution and build intution , its really the best we can get on youtube. thanks a lot sir
Sir koti koti pranam hai itna acha content dene ke liye.
Thank you so much Beta and If you like the content could you post something on LinkedIn about us? This will help us in reaching out to more people and help a lot of other students as well
Something like this
Sumeet Malik from Pepcoding is making all his content freely available to the community
You can check it out here - www.pepcoding.com/resources
/
Also, this is the youtube channel - ua-cam.com/users/Pepcodingplaylists?view_as=subscriber
No one literally no one explained in such an easy way ✌️
Keep learning and keep motivating.
For more such exciting content, don't forget to visit nados.pepcoding.com
40:20 max of 2 and 4 will be 4, I think sir has made a mistake. The answer at 2/7 will be 4 instead of 3. Please correct me if I am wrong.
Yeah
Why can't we do binary search on the floors to find critical floor? We will check if egg breaks from middle floor. If it does, then we will check in the bottom range. Otherwise, in the top range. And this way, the number of attempts will be logF. So we can for sure find a critical floor in logF attempts right? So when will there be a case when it is less than logF?
God level teaching!! Kudos !!
Sir u r doing a great job,thank u.Just a question,when will u b continuing with graph questions?
Will upload soon
best explanation till now for this problem.
simply awesome explanation
Great explanation sir! The CPP version for this logic was giving a TLE on leetcode. Instead of linear search, we must do binary search to pass the testcases.
can u share ur code?
@@yashrajpathak8103
class Solution {
public:
int superEggDrop(int k, int n) {
vector dp(k+1,vector(n+1,0));
for(int i=1; i
@@aditidey9366 thanks 😃😃
very nice explanation, Thanks Sir
Sir amazing expalnattion!!! Can u plz tell that which question you are referring as the next question, in last of the video, that will give complete insight??
Great sir, thanks😊.
Sir why we had not apply binary search
Sir apne dp main 1st column zero se initialize ni kiya ...app java use krte ho isliye automatically zero assign hua hoga na.
Hanji beta
Best explanation of all the videos, kudos !!
best explanation
Harr roz with each n every videos of U I see I become a more diehard fan of Your explanation and hardwork(Aap ki baat kya hi bole aap to ho hi Gurudev❤❤).
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
@@Pepcoding Done sir
I have a confusion on 40:23 seconds , should not it be Min from (3,3,3,3,4,5,6) + 1 = 4
yes correct
great explanation sir as usual just the way you make us understand the problem, there is no need to see the code part!
Glad to hear that
no words to appreciate.
That is why we love Sumit sir explanation ❣️
Glad you love the explanation, for better experience and well organised content sign up on nados.io and start learning.
Pranam Sir, pura confusion dur ho gya!
badiya sawal tha sir, samajhne mein kaafi maza aaya. East or west sumeet sir is the best
keep motivating and Keep loving😊
Thanks a lot for your efforts!
Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
sir this method is giving TLE in leetcode submission
on leetcode you need to submit O(n*logn*k) solution where as this solution is O(n^2*K) n is the floors and k is the eggs
Watch Aditya Verma for egg dropping 🔥🔥.. 👍
@@nitinkumar5974 Both will give TLE on leetcode and InterviewBit. You have to use Binary Search then only it will be accepted.
sir, the explanation is so mesmerizing
Glad to hear that. Keep watching
noted life lessons epic explanation thankyou so much sir....
crystal clear. thanks!
Greatest explanation of all times
Glad to know, for better experience and well organised content sign up on nados.io and start learning.
Nice Explanation!👍
Maza aa gaya Sir. O(n*k) ka bhi video banao please .
for 5 years i have been searching for that brief explanation..great work..
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
if you are able to get correct answer by this method please share the solution
this is the best explanation. thank you sir
SIR I THINK EGG DROPPING MAINE KITNA TRY KIYA THA SMAAJHNE KA...KAASH PEHLE PATA HOTA HAI PEPCODING KE BARE MEIN TOH MERE 2 SAAL BARBAAD NHI HOTE...KHAIR ABHI BHI TIME HAI..KARUNGA FODNE KA TRY MAI..GR8 EXPLANATION...claps
Foodi koi company?
@@kashba working as sde 1 at bajaj finserv markets
@@pranjalpatel256 😎🤝 Badiya bhai
Mai bhi 6 mahine ke andar andar badiya company fodunga koi
❤100/100 teaching.
Glad you think so!
Great. Best logical explanation
You really make the problem interesting 💯
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Excellent explanations !! You are the best mate.
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
May to prosper sir.
Kya gajab samjhate aap