Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals
VloĆŸit
- Äas pĆidĂĄn 27. 07. 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
đč Intuitive Video Explanations
đ Run Code As You Learn
đŸ Save Progress
âNew Unseen Questions
đ Get All Solutions
Question: Given an array of all integers that may or may not be sorted, determine the length of the longest subsequence that is strictly non-decreasing.
What Is A Subsequence?
A subsequence of an array is a subset of the array that maintains temporal order.
It does not have to be contiguous but it might turn out to be contiguous by chance.
Problem Name / Variants
This problem also comes in the form of asking for the longest strictly decreasing subsequence.
This is longest non-decreasing subsequence meaning that we will have a non-strictly increasing subsequence (aka we can have deltas of 0 between contiguous elements in the subsequence).
Approach 1 (Brute Force)
We can enumerate all 2^n subsets of the original array and then test them for the non-decreasing property.
The answer will be the longest subset that has the property.
This is too expensive.
Approach 2 (Dynamic Programming)
Do you see the potential for a subproblem here?
If you do, then we have the opportunity to use dynamic programming.
Example
[ -1, 3, 4, 5, 2, 8 ]
At the index 0 I always know that I can have a subsequence of length 1.
In fact, at all positions the longest non-decreasing subsequence can be at least length 1.
We then look at index 1, I need to ask myself if the item at index 1 can lengthen the longest subseqence found at index 0.
We check if 3 is greater than or equal to 1...it is. Great. index 1 can be tacked on but...should I?
The LNDS (longest non-decreasing subsequence) at index 1 is 0.
The LNDS at index 0 is 1.
Yeah...it makes sense because if I tack 3 onto the LNDS I found for the subproblem of just [ -1 ] then at index 1 I will also have a LDNS.
So what we basically do is build a table and ask ourselves these questions all along the way.
EACH CELL REPRESENTS THE ANSWER TO THE SUBPROBLEM ASKED AGAINST the subsequence from index 0 to index i (including the element at index i).
Complexities:
Time: O( n^2 )
n is the length of the array.
For each of the n elements we will solve the LNDS problem which takes O(n) time, therefore we yield a O( n^2 ) runtime complexity.
Space: O( n )
We will store our answers for each of the n LNDS subproblems.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 17.12 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. - VÄda a technologie
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 :(
"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
Not all heroes wear capes, some wear glasses and a amazon tshirt too :D
lol
True :D
@@BackToBackSWE Down with Amazon!!! j.k.
Love how this dude always answers the why questions to the small things compared to other people on youtube
hey haha
Amen to this
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
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.
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
One of the most energetic guys I found explaining DP.
Thank you.
lol, old video, sorry
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.
The amount of patience you have to explain this is commendable! Thanks!
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 absolute mad-man by repeating those things. Thank you man, I can't believe you made me understund those things. Never stop!
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
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
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.
You did great. You did not mess up. You exhibited passion, which is very engaging to those in your audience. Great presentation.
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
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
Love your lectures and love your energy, thanks so much for making these!
thanks
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.
bro you are really a good teacher who tech something more essential rather than just the solution
ye
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
You are a life saver! I cannot thank you enough for posting these!! Bless you!
sure
Thank you for being so clear, specific and for explaining everything slowly. You're way better than my teacher!
sure
After literally months of trying to figure out DP, after this video I finally got it!
nice
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!
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
Teaching is an art and you have mastered it . Oh captain , my captain . It is just pure joy learning from you.
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!
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!
Thanks a lot, buddy you not only cleared the concept of this problem but also the core of DP. Appreciate your efforts :D
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
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 the best. There is no one on CZcams who teaches fantastic as you
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
Thank you so much for uploading this video.
This helps me a lot, cuz I'm not good at dp.
sure
I really enjoy this guy yelling at me lol. Thanks dude for this video!
sorry, older videos had no microphone
I wrote my code based on this method all by myself. Pretty proud of the baby steps. Thank you!
great
Great video! Thanks for taking the time to make this!
love.
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
Man, thanks God I have found your channel, this is so easy to understand now.
nice
Thanks for the Amazon Falcon for posting video and save students' lives while working in Advengers.
"Oooo, Amazon shirt, he must be good at computer science" lmaooo
my bad - old video, no one watched then
i wish you could teach me every one of my classes! great teacher greeat structure , great video overall !
lol
I struggled so much and your videos have really guided and helped me to clarity!
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
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 amazing, i love that you explain beyond just solving the problem. You're an amazing teacher
thx
The best I have come across. Good work guys. Thank you for this
sure
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
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
first min in and was amazed by the way of explanation . Truly Respectable!
I could grab the solution straight away, very well explained, thanks!!
great.
Amazing content. I love the delivery. Keep it up :)
hahaha, I'm screaming but ok haha
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
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.
Love the way you go through explaining why the solution works!!!
Thanks a lot!!
sure
Well done! Quite a mouthful to handle at times, you did it well!
wow finally got it your explanation is crystal clearr....keep up the good energy!
nice
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 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
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 are really amazing at explaining reasoning behind the solution. Thank you so much for your work.
sure
Thanks a lot for the dp videos and all the other videos too :) It helped me a lot.
sure
Thanks Ben, I appreciate your time and efforts.
sure
I just have started learn DP. But after see your video, I now comprehend how it work. Thanks for awesome explainning đ
nice
The way you explain things is so easy to understand. Thanks for doing this.
sure
Thank you for doing these, they are a big help! You might be getting a little "yell-y" with your recent videos :)
Yeah, I know. A friend told me. I need to calm down haha.
Love your style! I feel smarter after watching your videos!
haha nice
best way to make us understand. Keep going . Luv ur videos
thanks
you and Abdul Bahri are carrying me through CS
Your videos are very helpful! Thanks a lot!
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!
what an amazing way to build intuition for such problems! thank you!!
Very clear explanation! Thanks a lot!
sure
Your videos are awesome, you explain beyond just solving the problem. It's really good.
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
dude ur energy is superb that helps understanding better
ha ok
Thank you man!! U really make it so seasy
This vid helped a lot, thanks man
Thank you for putting so much effort into your explanations
This channel is one of the best about computer science
It is ok - can be better
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
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
*When you take too much preworkout before teaching plebs dynamic programming.* Good vid lol, need to learn more of this stuff
lol sorry - old video
@@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!
One of the better explanations of the solution to this problem. Well done.
ye
I FINALLY GET IT!!!!!!! AWESOME EXPLANATION
thanks so much for this clear explanation!
sure
Great explanation!! Very helpful in learning how dynamic programming works.
Nice. Thank you for going through the entire thing, and cutting out the non-important clips.
sure
Amazing man !! thanks a lot
sure
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
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/
Keep up the good work! I
love.
Great explanation! Thanks a lot.
Thanks a lot; very well explained!!!