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!
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
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!
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
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.
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.
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
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
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 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!
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!
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!
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...
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.
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 :)
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.
Remember guys, when the problem says largest subsequence, it means the largest subsequence size. Both are slightly different things, hence why the shown approach may look a bit confusing at first. The intuition here is not that we are trying to find the largest subsequence size among all subsequences till a given element, no, instead we are trying to find all the subsequences including (or rather ending at) the given element while remembering which subsequence size was the largest, then doing it for the next element and so on. And finally, the largest subsequence size of an entire array is just the largest subsequence among all the largest subsequences. This is the reason why you may think that for an element at index i, the largest subsequence till it should simply be the largest of all subsequence sizes behind it, but with this approach, we are not trying to find the largest subsequence size till the element at index i, instead we are simply trying to find the largest subsequence that includes the element at index i and then storing the size of this subsequence. This could be bit confusing but once you understand it, you'll get why largest subsequence size and largest subsequence are slightly different and how you can subproblem it by looking at the question a little bit differently.
"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 :)
Hey I am new to programming I watch your videos to learn about such topics, I approached the problem in a bit different way what I did was made use of another temporary space and to store the given array in it but in sorted form. So now basically we can have two arrays(one given array and other sorted given array), we can find LCS (longest common sub sequence). I know the LCS is applied to strings but the idea here is pretty same. However your solution is anyways space efficient than mine.
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).
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.
I saw this problem as a graph problem and did a DFS. Sort of worked out for me. Still watching this video to get better insights though. Need help with the time complexity?
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
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.
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
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
One of the most energetic guys I found explaining DP.
Thank you.
lol, old video, sorry
I like how consistent you go through the whole run of the algorithm. It really helps understand it.
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
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.
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
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
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
The amount of patience you have to explain this is commendable! Thanks!
You did great. You did not mess up. You exhibited passion, which is very engaging to those in your audience. Great presentation.
thanks
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 absolute mad-man by repeating those things. Thank you man, I can't believe you made me understund those things. Never stop!
nice
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.
You are the best. There is no one on UA-cam who teaches fantastic as you
Man, I went through 5 youtube videos and finally understand how to implement it from yours. You da best!
thanks
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
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
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.
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
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
Teaching is an art and you have mastered it . Oh captain , my captain . It is just pure joy learning from you.
I wrote my code based on this method all by myself. Pretty proud of the baby steps. Thank you!
great
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!
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
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
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!
One of the better explanations of the solution to this problem. Well done.
ye
This channel is one of the best about computer science
It is ok - can be better
After literally months of trying to figure out DP, after this video I finally got it!
nice
I struggled so much and your videos have really guided and helped me to clarity!
nice
first min in and was amazed by the way of explanation . Truly Respectable!
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
The way you explain things is so easy to understand. Thanks for doing this.
sure
Thanks for the Amazon Falcon for posting video and save students' lives while working in Advengers.
Thank you for being so clear, specific and for explaining everything slowly. You're way better than my teacher!
sure
You are a life saver! I cannot thank you enough for posting these!! Bless you!
sure
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
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.
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
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?
what an amazing way to build intuition for such problems! thank you!!
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
you are really a miracle teacher, thank you, professor.
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
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.
I could grab the solution straight away, very well explained, thanks!!
great.
Remember guys, when the problem says largest subsequence, it means the largest subsequence size. Both are slightly different things, hence why the shown approach may look a bit confusing at first.
The intuition here is not that we are trying to find the largest subsequence size among all subsequences till a given element, no, instead we are trying to find all the subsequences including (or rather ending at) the given element while remembering which subsequence size was the largest, then doing it for the next element and so on. And finally, the largest subsequence size of an entire array is just the largest subsequence among all the largest subsequences. This is the reason why you may think that for an element at index i, the largest subsequence till it should simply be the largest of all subsequence sizes behind it, but with this approach, we are not trying to find the largest subsequence size till the element at index i, instead we are simply trying to find the largest subsequence that includes the element at index i and then storing the size of this subsequence.
This could be bit confusing but once you understand it, you'll get why largest subsequence size and largest subsequence are slightly different and how you can subproblem it by looking at the question a little bit differently.
I just have started learn DP. But after see your video, I now comprehend how it work. Thanks for awesome explainning 😎
nice
wow finally got it your explanation is crystal clearr....keep up the good energy!
nice
So much passion and enthusiasm in your style of explaining things. Thanks, man! Was really helpful.
sure
"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
Much obliged but if you could take that drill sergeant tone down a notch next time, that would be even more fantastic .
Love your lectures and love your energy, thanks so much for making these!
thanks
Your videos are amazing, i love that you explain beyond just solving the problem. You're an amazing teacher
thx
Nice. Thank you for going through the entire thing, and cutting out the non-important clips.
sure
you and Abdul Bahri are carrying me through CS
Hey I am new to programming I watch your videos to learn about such topics, I approached the problem in a bit different way what I did was made use of another temporary space and to store the given array in it but in sorted form. So now basically we can have two arrays(one given array and other sorted given array), we can find LCS (longest common sub sequence). I know the LCS is applied to strings but the idea here is pretty same. However your solution is anyways space efficient than mine.
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
You are like a missionary urging us to learn DP.
Yes
Back To Back SWE keep up the good stuff!
Wonderful sir...ur explanation, is a concept building solution for many people.
thanks
Thanks a lot, buddy you not only cleared the concept of this problem but also the core of DP. Appreciate your efforts :D
sure
Great video! Thanks for taking the time to make this!
love.
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
Man, thanks God I have found your channel, this is so easy to understand now.
nice
Excellent explanation, better than mind numbing reccurrence relations.
nice.
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/
this guy shouted knowledge to my brain.and my brain accepted it.thank you bro
lmao - sorry old video - had no mic
all your videos make the solution click, keep going!
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
와씨ㅋㅋㅋㅋㅋㅋㅋㅋ 이거 한글자막 번역하고 싶너... 개좋다 진짜... 한국피플은 이런거 하시는분 어디 없남 ㅠㅠ 이래서 영어공부를 엸심히 해야된다니깐ㅋㅋㅋㅋㅋㅋ 개좋앙!! f*cking awesome bro!! thanks a lot
Oh yeah we wanted to do subtitles but never got around to it. And 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!
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.
I saw this problem as a graph problem and did a DFS. Sort of worked out for me. Still watching this video to get better insights though. Need help with the time complexity?
After watching this video, it took me just 10 min to arrive at a solution for box stacking problem. **sentimental sobs**
great
i wish you could teach me every one of my classes! great teacher greeat structure , great video overall !
lol
Your videos are awesome, you explain beyond just solving the problem. It's really good.
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.
The best I have come across. Good work guys. Thank you for this
sure
Dude, just keep it up.. Awesome explaining
I am absolutely sure that ur channel will explode
thanks
Thank you for putting so much effort into your explanations
You deserve more subscribers dude
thanks.
You are really amazing at explaining reasoning behind the solution. Thank you so much for your work.
sure
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
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.
Any Suggestions on how to be good at dynamic programming.? Thanks for the amazing content.
You just have to do many problems and identify the patterns.
Thank you so much for this video , I was stuck to solve this problem ,but after watching your video the problem seems easy now for me
that's great to hear! There are other questions at - backtobackswe.com/ - Would love some feedback
i like the way you end the lecture
and obivously your explanation.
please make some more video on DP problems
ok
best way to make us understand. Keep going . Luv ur videos
thanks
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
Thank you Benyam.. Like the previous videos, explained the concept really well...Thank you very much.
sure and sure
Thank you so much for uploading this video.
This helps me a lot, cuz I'm not good at dp.
sure
Well done! Quite a mouthful to handle at times, you did it well!