Table of Contents: (yes, I know I'm screaming. I messed up...this video is old...ok.) Me Talking (Who Cares) 0:00 - 0:28 The Problem Introduction 0:28 - 1:13 LIS vs. LNDS vs. LDS 1:13 - 2:48 The Approaches 2:48 - 4:38 Full Dynamic Programming Table Walkthrough 4:38 - 16:45 Applying This To Other Dynamic Programming Problems 16:45 - 17:18 Time Complexity 17:18 - 18:00 Space Complexity 18:00 - 18:13 Handling Dynamic Programming In The Interview 18:13 - 18:43 The Usual 18:43 - 19:01 This problem also has an O( n * log(n) ) solution which is faster than the O( n ^ 2 ) DP solution here: leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation In my opinion, this isn't practical to pull off in an interview if you have never seen this question before and that is what matters to me. So I covered the O( n ^ 2 ) way since it is more reasonable. The code for this question (with exhaustive comments for teaching purposes) is in the description. It is for the Longest Increasing Subsequence problem. We talked about the Longest Non-Decreasing Subsequence.
Dude, you nailed it straight home, perfectly. I had been struggling with this problem for most of my Saturday afternoon. After a gruesome day of zero-progress and infinite hopelessness, the sheer joy and sigh of relief of finally having understood another concept is what made the evening a little better. Thanks !
The way you explained the problem is absolutely brilliant. Wasted my entire day on other videos. I'm following you for some months now, every video from you is absolutely Gold. More power to you!
Your videos are breaking certain things wide open for me that I've never seen before. Thanks man. I'm budgeting in time to watch at least one of your videos a night until I've seen them all
I was looking at leetcode discussion solutions for an hour trying to wrap my head around and understand it, but after watching this video it completely clicked and could code the problem with ease!
Finally someone could clearly explain (even to a non-native english speaker) this problem. I was beating my head against the wall because all explanations I've seen so far were difficult to understand, now I can easily understand the underlying code
Best Ever Explanation.You are just putting all the lights in the way to darkness to achieve the Algorithmic Destination.Keep posting such videos.And really appreciate the kind of effort you are putting to make these informative videos.Thanks
Dude, the way you explain it (and your energy) really helps me absorb and understand this. Also the way you emphasize the key technique helps make it click.
I rarely comment on videos, but I really appreciate your clear explanation. I was able to understand and code the solution based on your explanation by looking at your videos _just once_ - that's amazing! Keep up the good work! I'd love to donate/contribute to you once I pass my interviews at a Big N and get a job.
this is a 5 years old video, but i just wanted to say when it comes looking up problem my solutions, thanks to you i understood backtracking perfectly and now i watching this if i ever made transition into swe i am definitely crediting you
Happy Holidays 🎉 Thank you for your kind words, Siddharth! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
I never find the 'code in the description'. In every single video I never find the code. Can you clarify where it is? Btw your are amazing and help me a lot, thanks!
This is my first comment on youtube, but really dude you are seriously the best, loved your explanation... simple and clear, great job man keep it up :)
Your explanations are so intuitive and clear. I feel like I am starting to have a good feel on this subject after watching your videos. Love your awesome work!
"Subproblem Subproblem Subproblem" Thanks Ben, now I'm feeling much more better about how to solve the DP questions By the way, I really like your T-shirt :)
I actually love that you're screaming. I can feel the passion. That's one things that makes your videos great. Please don't become dry and all "professional" with future videos or with the content on your website. That's too boring. You make the topics exciting and fun. That's contagious. Keep it up. And people, please go check out his leetcode-like website backtobackswe.com. It's awesome. So impressed you did this all while in college.
Thanks for explaining the answers. I tried reading the explanations on blogs and leetcode, but they didn't click. Your videos already made things clicked for me and you teach the patten that I should recognize. DP is really hard for me for now, thanks for lessening the pain!
recently started interviewing, your videos are very helpful for solving leetcode problems in the most efficient way, i was even able to attempt hard category question on an actual interview after watching your videos, keep these videos coming \m/
@@BackToBackSWE can you please make a video about interleaving strings? The dynamic programming solution to the problem is a little difficult to understand and come up with.
I wish I watched this before my Amazon interview today. Although, they took it even further, and asked for longest geometric subsequence. Soul crushed...
Dude you explanations are just so unbelievably good. Like seriously you should open a school or something haha.....also if you guys make T shirts or something, I'd buy one
I love your energy and your videos For the dynamic programming videos like this one I think what you're missing is a section explaining what the core sub problem is, because that is the main challenge in dynamic programming, understanding the sub problem (which is not constant from problem to problem).
Its a very good video, helped me a lot, thank you. I like it that u tackle every question with the way thinking should be done in order to get it during interviews. Its very helpful.
At first, I was a little confused about what you meant by 'includes both bounds' for each of the sub-problems. Once I realized that you were only comparing the elements at i and j, it sort of clicked, but at the same time I realized there's a couple of flaws with the 'includes both bounds' requirement. - If the first element is the largest value in the array, then no non-decreasing subsequences including both bounds exist for any of the sub-problems. - All sub-problems after 0-0 should have a default answer of 2 instead of 1, since you're defining them to include both bounds. I think it makes more sense to say 'includes last element' instead.
The O(n log n) solution is niche but often in interviews they explicitly ask for an n log n solution. You have to follow a Binary Search approach to do that. Google Longest Increasing Subsequence Binary Search or Longest Increasing Subsequence nlogn for that.
Happy Halloween 🎃 Thank you, brother! You get some extraaa treats - 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50
This is trickier than usual dynamic programming. I think you should have done an example where the max is not at the end of the array. Also note that what we cache in case of the "sub-problems" is not the same as how we usually do dynamic prorgamming. That is because the sub-problems are not exactly the same as the problem. The problem is "what is the longest increasing subsequence which which may or may not include this last_index" whereas the sub problems are "what is the longest increasing subsequence which which MUST include this last_index" because we need to be able to evaluate quickly whether we can extend is later. This is why the max operation at the end is important.
This was great, but sometimes I think it's best if you write down something like max (a, b) because it's easier to follow. Fewer mistakes would be nice too because then it leads to more brain power spent on trying to figure out where the mistake was. I see you wrote down min (....) with the coin change one and I feel like it was easier to understand. Keep up the great work tho! You're the best out here.
Table of Contents: (yes, I know I'm screaming. I messed up...this video is old...ok.)
Me Talking (Who Cares) 0:00 - 0:28
The Problem Introduction 0:28 - 1:13
LIS vs. LNDS vs. LDS 1:13 - 2:48
The Approaches 2:48 - 4:38
Full Dynamic Programming Table Walkthrough 4:38 - 16:45
Applying This To Other Dynamic Programming Problems 16:45 - 17:18
Time Complexity 17:18 - 18:00
Space Complexity 18:00 - 18:13
Handling Dynamic Programming In The Interview 18:13 - 18:43
The Usual 18:43 - 19:01
This problem also has an O( n * log(n) ) solution which is faster than the O( n ^ 2 ) DP solution here: leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation
In my opinion, this isn't practical to pull off in an interview if you have never seen this question before and that is what matters to me. So I covered the O( n ^ 2 ) way since it is more reasonable.
The code for this question (with exhaustive comments for teaching purposes) is in the description. It is for the Longest Increasing Subsequence problem. We talked about the Longest Non-Decreasing Subsequence.
can u tell from where i can learn dp. its too difficult to understand
plz reply if u see this comment or make a video on this
@@deepakpaliwal2200 He has a playlist for DP.
Could you please sort the videos in DP playlist from easy to hard questions? It would be of great help!
The book "Algorithm Design" by Kleinberg and Tardos is really good if you want a very deep understanding
I wanted to but never ended up doing it :(
the high spirit in your voice and the medium pace is really motivating and keeps our brain focused. thanks buddy for your favor.
hahahaha, I'm just shouting...didn't have a mic
@@BackToBackSWE was playing lofi in spotify and your loud voice sounded like its in syhnc with the beats
Learning from him :p
@@TejasM14 true
"yes, we can" is very emotional. I will be very strong when I listen to this word. Feel that I can solve this algorithm question now! thanks, Ben
hahahaha sure.
You must be a fan of Barack Obama then lol
Love how this dude always answers the why questions to the small things compared to other people on youtube
hey haha
Amen to this
Not all heroes wear capes, some wear glasses and a amazon tshirt too :D
lol
True :D
@@BackToBackSWE Down with Amazon!!! j.k.
Dude, you nailed it straight home, perfectly. I had been struggling with this problem for most of my Saturday afternoon. After a gruesome day of zero-progress and infinite hopelessness, the sheer joy and sigh of relief of finally having understood another concept is what made the evening a little better. Thanks !
haha nice, if you like this check out our coding interview class, I'm posting video like this frequently there
The way you explained the problem is absolutely brilliant. Wasted my entire day on other videos.
I'm following you for some months now, every video from you is absolutely Gold. More power to you!
thx
o
I like how consistent you go through the whole run of the algorithm. It really helps understand it.
One of the most energetic guys I found explaining DP.
Thank you.
lol, old video, sorry
Your videos are breaking certain things wide open for me that I've never seen before. Thanks man. I'm budgeting in time to watch at least one of your videos a night until I've seen them all
nice
bro you are really a good teacher who tech something more essential rather than just the solution
ye
The more I watch your videos, the more I think that this channel deserves to grow.
Hahahahaha, thanks and I know right? This isn't the most scalable content...I'm cooking up somethin'....just wait.
You did great. You did not mess up. You exhibited passion, which is very engaging to those in your audience. Great presentation.
thanks
I was looking at leetcode discussion solutions for an hour trying to wrap my head around and understand it, but after watching this video it completely clicked and could code the problem with ease!
great
Honestly I like the loud voice you have. Wakes me up doing late night homework. Thank you tons can't wait to watch more videos.
great lol
You are better than 3/4th of the teachers I have studied from and one of the bests on online platforms! Keep going :)
thanks and tahnks
You are absolute mad-man by repeating those things. Thank you man, I can't believe you made me understund those things. Never stop!
nice
Someone give this man a noble price...🙌❤
haha thanks mate! subscribe to our DSA course with a flat 30% discount for some amazing content b2bswe.co/3HhvIlV
The amount of patience you have to explain this is commendable! Thanks!
Finally someone could clearly explain (even to a non-native english speaker) this problem. I was beating my head against the wall because all explanations I've seen so far were difficult to understand, now I can easily understand the underlying code
Man, I went through 5 youtube videos and finally understand how to implement it from yours. You da best!
thanks
Wow.
THE BEST explanation of dynamic programming approach for this problem.
Good teaching skills are rare and you've got them.
Thanks for this!
thanks!
You are the best. There is no one on UA-cam who teaches fantastic as you
Every time I encounter a problem and don't understand it, I go to this channel.
Huge thanks to you for explaining things so clearly, King.
Best Ever Explanation.You are just putting all the lights in the way to darkness to achieve the Algorithmic Destination.Keep posting such videos.And really appreciate the kind of effort you are putting to make these informative videos.Thanks
thanks
Dude, the way you explain it (and your energy) really helps me absorb and understand this. Also the way you emphasize the key technique helps make it click.
nice
Thanks for the Amazon Falcon for posting video and save students' lives while working in Advengers.
After literally months of trying to figure out DP, after this video I finally got it!
nice
I rarely comment on videos, but I really appreciate your clear explanation. I was able to understand and code the solution based on your explanation by looking at your videos _just once_ - that's amazing!
Keep up the good work! I'd love to donate/contribute to you once I pass my interviews at a Big N and get a job.
thanks! and nah u good, just get the job
One of the better explanations of the solution to this problem. Well done.
ye
Teaching is an art and you have mastered it . Oh captain , my captain . It is just pure joy learning from you.
this is a 5 years old video, but i just wanted to say when it comes looking up problem my solutions, thanks to you i understood backtracking perfectly and now i watching this
if i ever made transition into swe i am definitely crediting you
This channel is one of the best about computer science
It is ok - can be better
Only because of you i can understand dynamic Programming. Your one video explanation is sufficient to solve multiple other problems.
Happy Holidays 🎉 Thank you for your kind words, Siddharth! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
I wrote my code based on this method all by myself. Pretty proud of the baby steps. Thank you!
great
I never find the 'code in the description'. In every single video I never find the code. Can you clarify where it is? Btw your are amazing and help me a lot, thanks!
The repository is deprecated - we only maintain backtobackswe.com now
Thank you for being so clear, specific and for explaining everything slowly. You're way better than my teacher!
sure
first min in and was amazed by the way of explanation . Truly Respectable!
This is my first comment on youtube, but really dude you are seriously the best, loved your explanation... simple and clear, great job man keep it up :)
thanks
Your explanations are so intuitive and clear. I feel like I am starting to have a good feel on this subject after watching your videos. Love your awesome work!
nice!
dude ur energy is superb that helps understanding better
ha ok
"Subproblem Subproblem Subproblem"
Thanks Ben, now I'm feeling much more better about how to solve the DP questions
By the way, I really like your T-shirt :)
ye
"Oooo, Amazon shirt, he must be good at computer science" lmaooo
my bad - old video, no one watched then
I actually love that you're screaming. I can feel the passion. That's one things that makes your videos great. Please don't become dry and all "professional" with future videos or with the content on your website. That's too boring. You make the topics exciting and fun. That's contagious. Keep it up. And people, please go check out his leetcode-like website backtobackswe.com. It's awesome. So impressed you did this all while in college.
Thank you so much for this. This was of really great help and I must mention how the energy and positivity in your voice makes me really attentive.
Thanks for explaining the answers. I tried reading the explanations on blogs and leetcode, but they didn't click. Your videos already made things clicked for me and you teach the patten that I should recognize. DP is really hard for me for now, thanks for lessening the pain!
recently started interviewing, your videos are very helpful for solving leetcode problems in the most efficient way, i was even able to attempt hard category question on an actual interview after watching your videos, keep these videos coming \m/
great
@@BackToBackSWE can you please make a video about interleaving strings? The dynamic programming solution to the problem is a little difficult to understand and come up with.
@@akankshajain3997 I can look into that but not sure I'll ever get to it
You are a life saver! I cannot thank you enough for posting these!! Bless you!
sure
I struggled so much and your videos have really guided and helped me to clarity!
nice
you and Abdul Bahri are carrying me through CS
The way you explain things is so easy to understand. Thanks for doing this.
sure
Dude, you channel is growing quick. Now when I go to the discussion I'll first look for your user name bephrem.
Thank you for all the helps!
hahahahaha, I want it to grow faster. Too slow for me. Thanks.
I wish I watched this before my Amazon interview today. Although, they took it even further, and asked for longest geometric subsequence. Soul crushed...
ur good - you'll make it
Did you get your amazon shirt?
Let's test you on random sh*t you'll never rarely come across in your day job, how about that?
Thanks a lot, buddy you not only cleared the concept of this problem but also the core of DP. Appreciate your efforts :D
sure
You are awesome dude ! I always felt DP was too complex but watching your vids have greatly simplified it !! Keep making more videos ! :)
no ur awesome
Dude you explanations are just so unbelievably good. Like seriously you should open a school or something haha.....also if you guys make T shirts or something, I'd buy one
thanks and haha nice
I love your energy and your videos
For the dynamic programming videos like this one I think what you're missing is a section explaining what the core sub problem is, because that is the main challenge in dynamic programming, understanding the sub problem (which is not constant from problem to problem).
ok
Much obliged but if you could take that drill sergeant tone down a notch next time, that would be even more fantastic .
Dude, just keep it up.. Awesome explaining
I am absolutely sure that ur channel will explode
thanks
So much passion and enthusiasm in your style of explaining things. Thanks, man! Was really helpful.
sure
Love your lectures and love your energy, thanks so much for making these!
thanks
You deserve more subscribers dude
thanks.
this guy shouted knowledge to my brain.and my brain accepted it.thank you bro
lmao - sorry old video - had no mic
I could grab the solution straight away, very well explained, thanks!!
great.
you are really a miracle teacher, thank you, professor.
Your videos are amazing, i love that you explain beyond just solving the problem. You're an amazing teacher
thx
i wish you could teach me every one of my classes! great teacher greeat structure , great video overall !
lol
You are like a missionary urging us to learn DP.
Yes
Back To Back SWE keep up the good stuff!
all your videos make the solution click, keep going!
wow finally got it your explanation is crystal clearr....keep up the good energy!
nice
I really enjoy this guy yelling at me lol. Thanks dude for this video!
sorry, older videos had no microphone
Nice. Thank you for going through the entire thing, and cutting out the non-important clips.
sure
Wonderful sir...ur explanation, is a concept building solution for many people.
thanks
I just have started learn DP. But after see your video, I now comprehend how it work. Thanks for awesome explainning 😎
nice
thanks for the explanation of the algorithm....I got confused when i first saw the code, but watching the video, the idea behind it became clear :)
great
what an amazing way to build intuition for such problems! thank you!!
Man, thanks God I have found your channel, this is so easy to understand now.
nice
Thank you so much for uploading this video.
This helps me a lot, cuz I'm not good at dp.
sure
Great video! Thanks for taking the time to make this!
love.
Excellent explanation, better than mind numbing reccurrence relations.
nice.
Its a very good video, helped me a lot, thank you. I like it that u tackle every question with the way thinking should be done in order to get it during interviews. Its very helpful.
thanks.
You put so much hard work to explain the concepts! You're the best!
no u
@@BackToBackSWE You always reply! Thanks! You should now remember my name!
At first, I was a little confused about what you meant by 'includes both bounds' for each of the sub-problems. Once I realized that you were only comparing the elements at i and j, it sort of clicked, but at the same time I realized there's a couple of flaws with the 'includes both bounds' requirement.
- If the first element is the largest value in the array, then no non-decreasing subsequences including both bounds exist for any of the sub-problems.
- All sub-problems after 0-0 should have a default answer of 2 instead of 1, since you're defining them to include both bounds.
I think it makes more sense to say 'includes last element' instead.
The O(n log n) solution is niche but often in interviews they explicitly ask for an n log n solution. You have to follow a Binary Search approach to do that. Google Longest Increasing Subsequence Binary Search or Longest Increasing Subsequence nlogn for that.
ok
The best I have come across. Good work guys. Thank you for this
sure
You just took 20 Minutes to explain what could be done in 4 minutes. Felt like i am in a TeleShow Advertisement.
leave
Love your energy brother!!
Happy Halloween 🎃 Thank you, brother! You get some extraaa treats - 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50
Now this is a great video, clear when speaking and dividing into very useful portions
Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/
have u made video for that "nlogn" solution too?
not yet
@@BackToBackSWE wow that's really fast never expected that. Btw please make one if u get time. Thanks for this
You are really amazing at explaining reasoning behind the solution. Thank you so much for your work.
sure
Your videos are awesome, you explain beyond just solving the problem. It's really good.
This video is really helpful. It taught me how to approach complex dynamic programming problems very easily. thanks a lot.
sure
Yeah same for me
thanks for your videos(nice explanation bro.)
sure.
best way to make us understand. Keep going . Luv ur videos
thanks
This is trickier than usual dynamic programming. I think you should have done an example where the max is not at the end of the array. Also note that what we cache in case of the "sub-problems" is not the same as how we usually do dynamic prorgamming. That is because the sub-problems are not exactly the same as the problem. The problem is "what is the longest increasing subsequence which which may or may not include this last_index" whereas the sub problems are "what is the longest increasing subsequence which which MUST include this last_index" because we need to be able to evaluate quickly whether we can extend is later. This is why the max operation at the end is important.
thx
Love your style! I feel smarter after watching your videos!
haha nice
Back To Back SWE is the powerhouse of the cell ;)
amazed by his energy !!!!!!
Yess
cheers to you bro, you teach better than my algorithms prof
thx
This was great, but sometimes I think it's best if you write down something like max (a, b) because it's easier to follow. Fewer mistakes would be nice too because then it leads to more brain power spent on trying to figure out where the mistake was. I see you wrote down min (....) with the coin change one and I feel like it was easier to understand. Keep up the great work tho! You're the best out here.