Egg Dropping Problem Dynamic Programming | Leetcode Hard Solutions
ฝัง
- เผยแพร่เมื่อ 22 ส.ค. 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 TH-cam to explain this concept flawlessly.
Most of the TH-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 !!
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 )
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 )
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?
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😊
Why I was not aware of this channel before. The way you teach is awesome. I am really grateful for such awesome videos.
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
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 ..
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)
This is the bestest explanation of any problem on youtube.
Woahhh sir finally egg 🥚 drop problem solution is here ❤️❤️🔥🔥
Great 👍
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
And this was exactly what I was looking for! Thank you so much for the wonderful explanation! 😃
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 )
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 TH-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😊
40:22 maximum value should be 4 else awesome content
The way you explain dynamic problems is far better than others. Thank you sir😁.
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😊
This channel is soo underrated!!!
discovering you late but you are a great teacher. you really put the effort in your video. i can see that.
Sir dimag ka dahi ho gya tha...but now the problem is crystal clear.... thanks ❤️❤️
wonderful explanation I have found in whole youtube. Thank you so muchhhhhhh
The way of explanation. Hats off to you 👏 👏 👏
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🙏
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!
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
Very nice explanation sir
Very well explained. Kudos to u for putting so much effort!
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.
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. !!! :)
best ever explanation I have seen on TH-cam ❤
Best video that explains the concept well.👍
Kyaa kamaal padhaate ho aap!! Majaa hi aa gya!!
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.
Aree bhaiyaji agg laga di...ande fodne ka estimate k sath placement mein fodne ka estimation acha lgg rha..:wink emoji inserted.
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, What an amazing solution. Understand everything
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..
Best explanation with a life lesson 🤩
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
tagda bhai...appreciate your effort...
don't know why so underrated
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.
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
Nice explanation sir....thanks a lot for the video....the content on your youtube channel is amazing...
Sir, aapki 4:56 wali baat dil pe lagti hai
For better experience and well organised content visit nados.pepcoding.com
thank you so much sir watch only manager question and has gotten the solution of egg dropping
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 - th-cam.com/users/Pepcodingplaylists?view_as=subscriber
Good to see new questions added to platform
very nice explanation, Thanks Sir
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 )
simply awesome explanation
badiya sawal tha sir, samajhne mein kaafi maza aaya. East or west sumeet sir is the best
keep motivating and Keep loving😊
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
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
Sir you are God for me...
God level teaching!! Kudos !!
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
th-cam.com/users/Pepcodingabout?view_as=subscriber
if you are able to get correct answer by this method please share the solution
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.
best explanation till now for this problem.
Best explanation of all the videos, kudos !
Glad you liked it!
For better experience and well-organised content
Visit - nados.pepcoding.com
Don't forget to follow us on Instagram
instagram.com/pepcoding/
Pranam Sir, pura confusion dur ho gya!
great explanation..bt this solution is giving tle in leetcode.
try to use binary search
best explanation
Nice Explanation!👍
Great sir, thanks😊.
Maza aa gaya Sir. O(n*k) ka bhi video banao please .
Best explanation of all the videos, kudos !!
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
Greatest explanation of all times
Glad to know, for better experience and well organised content sign up on nados.io and start learning.
g8t explanation buddy keep it up
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
sir, the explanation is so mesmerizing
Glad to hear that. Keep watching
May to prosper sir.
Kya gajab samjhate aap
great explanation sir
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 😃😃
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
48:43 kaun sa agla sawal? optimal strategy for a game??
perfectly explained sir
Great. Best logical explanation
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 )
noted life lessons epic explanation thankyou so much sir....
Most unrated channel of YT.
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
❤100/100 teaching.
Glad you think so!
this is the best explanation. thank you sir
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😊
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 )
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
no words to appreciate.
crystal clear. thanks!
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
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.
Thankyou so much sir. Your efforts are really great
Best Explanation
Great explanation!