Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals

[@BackToBackSWE]

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.

[@deepakpaliwal2200]

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

[@akhilesh_singla]

@@deepakpaliwal2200 He has a playlist for DP.

[@akhilesh_singla]

Could you please sort the videos in DP playlist from easy to hard questions? It would be of great help!

[@BackToBackSWE]

The book "Algorithm Design" by Kleinberg and Tardos is really good if you want a very deep understanding

[@BackToBackSWE]

I wanted to but never ended up doing it :(

[@tianxiaowang3771]

"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

[@BackToBackSWE]

hahahaha sure.

[@yueli2146]

You must be a fan of Barack Obama then lol

[@keeplearning5707]

the high spirit in your voice and the medium pace is really motivating and keeps our brain focused. thanks buddy for your favor.

[@BackToBackSWE]

hahahaha, I'm just shouting...didn't have a mic

[@irvinge4641]

@@BackToBackSWE was playing lofi in spotify and your loud voice sounded like its in syhnc with the beats

[@maythecodesbewithyou29]

Learning from him :p

[@BlokeBritish]

@@TejasM14 true

[@mokim8435]

Love how this dude always answers the why questions to the small things compared to other people on youtube

[@BackToBackSWE]

hey haha

[@helloiam2mas]

Amen to this

[@awesomeps10]

Not all heroes wear capes, some wear glasses and a amazon tshirt too :D

[@BackToBackSWE]

lol

[@utkarsh_goel]

True :D

[@user-zc8sq3wr9f]

@@BackToBackSWE Down with Amazon!!! j.k.

[@dangidelta]

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 !

[@BackToBackSWE]

haha nice, if you like this check out our coding interview class, I'm posting video like this frequently there

[@debrc]

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!

[@BackToBackSWE]

thx

[@sar6575]

o

[@puperhacker2150]

The more I watch your videos, the more I think that this channel deserves to grow.

[@BackToBackSWE]

Hahahahaha, thanks and I know right? This isn't the most scalable content...I'm cooking up somethin'....just wait.

[@raghavendraPi]

One of the most energetic guys I found explaining DP. Thank you.

[@BackToBackSWE]

lol, old video, sorry

[@dcodernz]

I like how consistent you go through the whole run of the algorithm. It really helps understand it.

[@jonathanfoster5106]

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

[@BackToBackSWE]

nice

[@kiweilau7191]

bro you are really a good teacher who tech something more essential rather than just the solution

[@BackToBackSWE]

ye

[@armaanpathan1856]

Someone give this man a noble price...🙌❤

[@BackToBackSWE]

haha thanks mate! subscribe to our DSA course with a flat 30% discount for some amazing content b2bswe.co/3HhvIlV

[@ameynaik2743]

The amount of patience you have to explain this is commendable! Thanks!

[@micmicmw]

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.

[@BackToBackSWE]

great lol

[@jjlian1670]

Man, I went through 5 youtube videos and finally understand how to implement it from yours. You da best!

[@BackToBackSWE]

thanks

[@frozen_tortus]

You are absolute mad-man by repeating those things. Thank you man, I can't believe you made me understund those things. Never stop!

[@BackToBackSWE]

nice

[@marcossneijder]

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

[@therawbean69]

You are better than 3/4th of the teachers I have studied from and one of the bests on online platforms! Keep going :)

[@BackToBackSWE]

thanks and tahnks

[@hackytech7494]

You are the best. There is no one on KZbin who teaches fantastic as you

[@adhamsalama4336]

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.

[@wesiegel]

You did great. You did not mess up. You exhibited passion, which is very engaging to those in your audience. Great presentation.

[@BackToBackSWE]

thanks

[@MrQuaex]

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!

[@BackToBackSWE]

great

[@smallcreativecorner5930]

Wow. THE BEST explanation of dynamic programming approach for this problem. Good teaching skills are rare and you've got them. Thanks for this!

[@BackToBackSWE]

thanks!

[@endle_ss]

Teaching is an art and you have mastered it . Oh captain , my captain . It is just pure joy learning from you.

[@ChandraShekhar-by3cd]

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

[@BackToBackSWE]

thanks

[@MaxVinstappen]

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.

[@BackToBackSWE]

nice

[@MoaazAhmad]

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.

[@BackToBackSWE]

thanks! and nah u good, just get the job

[@zm5431]

After literally months of trying to figure out DP, after this video I finally got it!

[@BackToBackSWE]

nice

[@daleprather3026]

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.

[@foobar527]

One of the better explanations of the solution to this problem. Well done.

[@BackToBackSWE]

ye

[@neosapien247]

I wrote my code based on this method all by myself. Pretty proud of the baby steps. Thank you!

[@BackToBackSWE]

great

[@gergeerew6811]

This channel is one of the best about computer science

[@BackToBackSWE]

It is ok - can be better

[@munna0808]

"Oooo, Amazon shirt, he must be good at computer science" lmaooo

[@BackToBackSWE]

my bad - old video, no one watched then

[@callanambulancebutnotforme5702]

first min in and was amazed by the way of explanation . Truly Respectable!

[@siddharthkhandelwal933]

Only because of you i can understand dynamic Programming. Your one video explanation is sufficient to solve multiple other problems.

[@BackToBackSWE]

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

[@ahmedyassien4695]

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

[@demagab]

Thank you for being so clear, specific and for explaining everything slowly. You're way better than my teacher!

[@BackToBackSWE]

sure

[@hansyu1688]

Thanks for the Amazon Falcon for posting video and save students' lives while working in Advengers.

[@jayantakumarroy543]

this guy shouted knowledge to my brain.and my brain accepted it.thank you bro

[@BackToBackSWE]

lmao - sorry old video - had no mic

[@catherines4884]

You are a life saver! I cannot thank you enough for posting these!! Bless you!

[@BackToBackSWE]

sure

[@nandakumar1422]

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

[@BackToBackSWE]

thanks

[@yicai7]

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

[@BackToBackSWE]

ye

[@samriniqbal5096]

The way you explain things is so easy to understand. Thanks for doing this.

[@BackToBackSWE]

sure

[@chaitanyakulkarni6012]

dude ur energy is superb that helps understanding better

[@BackToBackSWE]

ha ok

[@anonsurf6640]

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!

[@BackToBackSWE]

nice!

[@DennisSmdFreefightTrainer]

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!

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now

[@jinggong2503]

You are like a missionary urging us to learn DP.

[@BackToBackSWE]

Yes

[@jinggong2503]

Back To Back SWE keep up the good stuff!

[@MeizeT]

I struggled so much and your videos have really guided and helped me to clarity!

[@BackToBackSWE]

nice

[@akankshajain3997]

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]

great

[@akankshajain3997]

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

[@BackToBackSWE]

@@akankshajain3997 I can look into that but not sure I'll ever get to it

[@amrithagopakumar]

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.

[@wagishagupta162]

what an amazing way to build intuition for such problems! thank you!!

[@nirajchowdhary7372]

Thanks a lot, buddy you not only cleared the concept of this problem but also the core of DP. Appreciate your efforts :D

[@BackToBackSWE]

sure

[@zirkphoto]

all your videos make the solution click, keep going!

[@Maximosnol]

you and Abdul Bahri are carrying me through CS

[@Hav0c1000]

I wish I watched this before my Amazon interview today. Although, they took it even further, and asked for longest geometric subsequence. Soul crushed...

[@BackToBackSWE]

ur good - you'll make it

[@KaiBeatbox0803]

Did you get your amazon shirt?

[@foreverursabhi]

Let's test you on random sh*t you'll never rarely come across in your day job, how about that?

[@wh264]

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!

[@sourenasahraian2055]

Much obliged but if you could take that drill sergeant tone down a notch next time, that would be even more fantastic .

[@riyastk1]

I could grab the solution straight away, very well explained, thanks!!

[@BackToBackSWE]

great.

[@helloiam2mas]

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

[@BackToBackSWE]

thanks and haha nice

[@jerrywu5797]

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!

[@BackToBackSWE]

hahahahaha, I want it to grow faster. Too slow for me. Thanks.

[@mohammedmarhnine8194]

you are really a miracle teacher, thank you, professor.

[@vivek_onl]

You just took 20 Minutes to explain what could be done in 4 minutes. Felt like i am in a TeleShow Advertisement.

[@BackToBackSWE]

leave

[@shashwatagrawal8412]

You are awesome dude ! I always felt DP was too complex but watching your vids have greatly simplified it !! Keep making more videos ! :)

[@BackToBackSWE]

no ur awesome

[@thankgoditsover]

So much passion and enthusiasm in your style of explaining things. Thanks, man! Was really helpful.

[@BackToBackSWE]

sure

[@fernandomederos6689]

wow finally got it your explanation is crystal clearr....keep up the good energy!

[@BackToBackSWE]

nice

[@jdavis6355]

*When you take too much preworkout before teaching plebs dynamic programming.* Good vid lol, need to learn more of this stuff

[@BackToBackSWE]

lol sorry - old video

[@jdavis6355]

@@BackToBackSWE Honestly if you did a mini series of tutorials that were over the top extreme like those old school monster truck commercials... That would be legendary... would have to have visual effects!

[@howlowl7866]

Man, thanks God I have found your channel, this is so easy to understand now.

[@BackToBackSWE]

nice

[@enjili6062]

I really enjoy this guy yelling at me lol. Thanks dude for this video!

[@BackToBackSWE]

sorry, older videos had no microphone

[@JustSkillGG]

Dude, just keep it up.. Awesome explaining I am absolutely sure that ur channel will explode

[@BackToBackSWE]

thanks

[@harshitgupta1951]

Love your energy brother!!

[@BackToBackSWE]

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

[@shafeenmahmud8850]

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

[@BackToBackSWE]

ok

[@MySWESpace]

Your videos are amazing, i love that you explain beyond just solving the problem. You're an amazing teacher

[@BackToBackSWE]

thx

[@scnullois]

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.

[@BackToBackSWE]

thx

[@soz824]

Love your lectures and love your energy, thanks so much for making these!

[@BackToBackSWE]

thanks

[@wombaston]

This is the fastest I have ever been able to understand a DP problem. Usually it takes me forever. Great explanation!

[@BackToBackSWE]

I know. It's because I'm teaching how I wish I learned it. That's why you understood so quickly. It is really key to put oneself in a student's shoes and...a few months ago I was a student to this problem.

[@harifrahman8054]

You deserve more subscribers dude

[@BackToBackSWE]

thanks.

[@iliasp4275]

i wish you could teach me every one of my classes! great teacher greeat structure , great video overall !

[@BackToBackSWE]

lol

[@RandomShowerThoughts]

Now this is a great video, clear when speaking and dividing into very useful portions

[@BackToBackSWE]

Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/

[@DanDan-zs6wg]

Great video! Thanks for taking the time to make this!

[@BackToBackSWE]

love.

[@hbadheka]

Excellent explanation, better than mind numbing reccurrence relations.

[@BackToBackSWE]

nice.

[@priyanshisharma536]

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

[@BackToBackSWE]

great

[@unturned6066]

Nice. Thank you for going through the entire thing, and cutting out the non-important clips.

[@BackToBackSWE]

sure

[@dheerajsharma5492]

how can anybody dislike such a nice explanation?

[@BackToBackSWE]

cuz I'm screaming haha. I have a mic now so it's ok

[@dheerajsharma5492]

🤓

[@BackToBackSWE]

@@dheerajsharma5492 whats up, editing a video rn

[@dheerajsharma5492]

@@BackToBackSWE started learning again after long time. thanks to u

[@BackToBackSWE]

nice

[@graham12345dd]

Well done! Quite a mouthful to handle at times, you did it well!

[@Reubs1]

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.

[@librae-5664]

와씨ㅋㅋㅋㅋㅋㅋㅋㅋ 이거 한글자막 번역하고 싶너... 개좋다 진짜... 한국피플은 이런거 하시는분 어디 없남 ㅠㅠ 이래서 영어공부를 엸심히 해야된다니깐ㅋㅋㅋㅋㅋㅋ 개좋앙!! f*cking awesome bro!! thanks a lot

[@BackToBackSWE]

Oh yeah we wanted to do subtitles but never got around to it. And thanks

[@SR-we1vl]

You put so much hard work to explain the concepts! You're the best!

[@BackToBackSWE]

no u

[@SR-we1vl]

@@BackToBackSWE You always reply! Thanks! You should now remember my name!

[@MotoRider23605]

Wonderful sir...ur explanation, is a concept building solution for many people.

[@BackToBackSWE]

thanks

[@rohitpathak6084]

The best I have come across. Good work guys. Thank you for this

[@BackToBackSWE]

sure

[@minhnhatnguyen8065]

I just have started learn DP. But after see your video, I now comprehend how it work. Thanks for awesome explainning 😎

[@BackToBackSWE]

nice

[@The8merp]

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.

[@BackToBackSWE]

ok

[@chemi590]

Thank you so much for uploading this video. This helps me a lot, cuz I'm not good at dp.

[@BackToBackSWE]

sure

[@AtoZ-jv1py]

thanks for your videos(nice explanation bro.)

[@BackToBackSWE]

sure.

[@anonymousvoid6356]

amazed by his energy !!!!!!

[@BackToBackSWE]

Yess

[@abhimishra2276]

This guy is a genius

[@BackToBackSWE]

im normal

[@abhimishra2276]

@@BackToBackSWE believe me bro you have great teaching skills .

[@AnikG22]

Your videos are awesome, you explain beyond just solving the problem. It's really good.

[@92AkshaySharma]

cheers to you bro, you teach better than my algorithms prof

[@BackToBackSWE]

thx

[@preetkamal7424]

Thanks a lot for the dp videos and all the other videos too :) It helped me a lot.

[@BackToBackSWE]

sure

[@MrVijay8836]

Dude, great man. After watching Your videos, my "BRAIN FOG" is gone. Next time i feel the same i should watch your videos rather than taking medicines.

[@BackToBackSWE]

hahaha

[@MrVijay8836]

@@BackToBackSWE I am actively searching for a new job. So learning all algos and DS. The main thing in Your videos is you are training others minds to think which is like 'walking on water' . I will be in touch with You. Thanks.

[@BackToBackSWE]

@@MrVijay8836 hahaha nice