Longest Increasing Subsequence O(n log n) dynamic programming Java source code

[@ericfricke4512]

1:22 "To understand how it works, let's develop our intuition..." Man, I wish more math and computer science teachers would be better at this.

[@stablesort]

I hear you. Thanks for leaving a few good words.

[@spencerkhalid4579]

I know Im asking randomly but does someone know of a way to get back into an instagram account? I somehow forgot the login password. I appreciate any tricks you can give me!

[@dashdoom8452]

so true, this is the most important part to understanding and it is usually completely skipped over for some reason

[@maridavies3425]

Awesome. That’s the best explanation of finding the longest increasing subsequence I’ve seen. Thanks for the video!

[@madhivarman508]

The demo with the card is where exactly I understood "How the algorithm works?". Before watching this video, went through various other videos but couldn't understand the pointer concept correctly. A little graphical content makes learning better. Thanks for this video

[@stablesort]

Awesome, thanks for the good words!

[@mr.curious1537]

Such a wonderful explanation in such less time, I have already wasted 20 min of reading in order to understand this, but understood it, in just 5 min.

[@annas8308]

There are only 2 KZbin videos explaining the problem in O(nlogn) time. Your explanation is very clear and you are awesome!

[@stablesort]

Thanks! Believe it or not, I started this channel because I could not find a tutorial on how to solve the Longest Increasing Sequence in O(n log n). This was the very first video. Now I am just exploring subjects that I find neat, or I am simply curious about. Stay tuned and I hope you'd find other episodes interesting as well!

[@aditya234567]

@@stablesort THANK YOU SOO MUCH!!!!!!!!!

[@rhutshab]

this channel is so underrated

[@narihanellaithy7726]

Simple, concise and the best explanation of longest increasing subsequence! Subscribed :) We need more of this!

[@stablesort]

Thank you for the compliment! One thing I forgot to mention in the video is that a complete implementation of it using Java is linked in the description.

[@Yo-gh1cx]

I like how 100th of club is designed

[@stablesort]

I am more of a software engineer and not much of a graphics designer so I am happy to hear that the image made sense =)

[@mayankagrawal809]

I cam here from other channel's comment section, Not going back now...

[@stablesort]

I am glad to hear that you found this video useful =)

[@mindyourbusiness46]

Lol. Let me guess... Tushar Roy??

[@daniekpo]

@@mindyourbusiness46 😂

[@siddharthmagadum16]

@Hank Hudson Okay stop sending this same message to every educational video. or are u a bot.

[@uddeshyaagrawal2182]

I can't believe 23 people have disliked this video. In my opinion, this is the best possible explanation for this solution. Thanks for the video !!

[@stablesort]

Glad you liked it!

[@playerunknown1117]

I have much appreciation for the one making this video. The algorithm is very simple with image illustration making things easy to understand. Even though, I think there is a problem in your proof. The main thing needs to be hold is "the longest increasing subsequence." "Card n+1 must go into some pile on the right" doesn’t lead to anything

[@anandsrikumar007]

I solved it. I understood the problem after looking at your cards example, the example made this algorithm clear for me.

[@stablesort]

Glad to hear that it was helpful!

[@chelseali9725]

Really good explanation! Watched twice and finally understand the concept. I like your example and pace of talk (very calm, clear but also cheerful, and the pauses is neat). Subscribed!

[@stablesort]

Sweet! Thanks for the feedback and thanks for subscribing!

[@benmontgomery1111]

Hands down, the best explanation I've seen on KZbin

[@vineetbhargava4141]

the best explanation so far for longest increasing subsequence problem in nlgn time.

[@stablesort]

I do appreciate your good words! Cheers!

[@adrijachakraborty2316]

Phenomenal explanation of LIS! I couldn't find any video describing why patience sort actually works for LIS! Amazing work sir! Thank you for your time and contribution for spreading the knowledge.

[@stablesort]

You are very welcome! Thank you for such a wonderful compliment!

[@mike-yj5mm]

I keep coming back to watch this again time over time. The best explanation of the algorithm of all time.

[@stablesort]

Thanks, I do appreciate your feedback!

[@HetThakkar809]

Thank you for including proof of correctness in your video. It really helped convince my stupid little brain

[@nobsreviews8814]

I really appreciate the graphics, and your calm voice. You are very relaxed for someone whose last name is VIOLENTey

[@stablesort]

Haha, thanks for the compliment! Yeah, the last name is a bit of a spelling conundrum... It should have been spelled "Veeolentyev", but I guess when my family was immigrating, no one knew enough English to crosscheck for possible word/meaning collisions =)

[@nobsreviews8814]

Haha that sounds like an algorithm problem in itself!

[@stablesort]

@@nobsreviews8814 True! 8-P

[@SeyhunSaryldz]

This video is the best explanation for the longest increasing subsequence I have seen. Thank you a lot for it, I enjoyed a lot, and we hope we can see more videos from you.

[@stablesort]

Thanks for the compliment! I am working on the next one as we speak. By the, if you have suggestions for video topics, please do let me know. Cheers!

[@SeyhunSaryldz]

​Thank you​. I am looking for an explanation for "splitting non-negative integer array to m subarray while minimizing the largest sum among this m subarray".

[@SeyhunSaryldz]

@@stablesort The DP solution, there are not enough contents only for the DP solution.

[@stablesort]

@@SeyhunSaryldz Roger that. Thank you for the suggestion (as well the one about DP content).

[@ale9507]

Brilliant explanation. Getting to understand the intuition behind algorithms is what gets me to truly appreciate computational thinking. These videos are orders of magnitude more beneficial than explanations of only the implementation. Thank you.

[@stablesort]

Glad to hear it and thanks for the compliment!

[@ayyubshaffy3612]

I watched it 3 times and finally understood!! This video was awesome :) (u earned a sub!)

[@stablesort]

Great!

[@dorondavid4698]

Damn, that's impressive. Most dp algorithms are n*m, so n log n is a nice improvement!

[@rihamkatout2679]

Wow !! A lot of thanks, I've been searching for 2 hours, your explanation is short and so clear. You are amazing !

[@PhoenixRisingFromAshes471]

WOw sir,you made my day.I came to your video after the lonegest sub sequence problem

[@stablesort]

Thanks! Your comment gives me inspiration to make more videos! By the way, any suggestions as to what topic to cover next?

[@PhoenixRisingFromAshes471]

@@stablesort you should make more videos on other algorithmic paradigns like greedy,dynamic programming (mainly cause i sucks at dp)

[@stablesort]

@@PhoenixRisingFromAshes471 I hear you. There are definitely a few DP algorithms that are on my to-do list. I try to prioritize those for which I could not find a good, succinct tutorial. And especially the topics that people asked for specifically.

[@ShabnamKhan-cj4zc]

Awesome explanation.. Even a laymen can understand the logic thats what a good teachers does.. Thanks a lot for explaning in Easy way and with game

[@stablesort]

Thanks for the compliment! Glad to hear that you enjoyed the video =)

[@GubenkovED]

the best explanation i've seen so far, very good job!

[@stablesort]

Thanks for the compliment!

[@mrmrigank7154]

awesome explanation to give the intuition, now I just have to think about finding the right pile in logn for each card, and nice shirt btw!

[@oscarmvl]

Great explanation! Thanks for demonstrating why the algorithm provides the optimal solution.

[@rohitashwanigam]

Nice explanation. Thanks. For the case where an element is equal to previous, we can just point to the same place where the previous element had pointed to. Ofcourse, this is when you want longest increasing subsequence. If you are looking for longest non-decreasing subsequence, just point to the equal element itself.

[@stablesort]

Good point!

[@GreenMarkoulis13]

Great video. U should do more, their quality is ideal and very much needed

[@stablesort]

Thanks for the words of encouragement!

[@shourabhpayal1198]

Please keep posting more videos. Every video is top quality.

[@stablesort]

Thank you, will do!

[@ShaunYCheng]

Appreciate the brief video. Action packed!

[@stablesort]

Thanks, I appreciate your compliment!

[@wh264]

probably the clearest explanation I've seen. Thanks!

[@stablesort]

Thanks for the compliment!

[@zhambyl1454]

Please, keep making videos. Your explanations are the best

[@puneetkumarsingh1484]

Extremely Clear Explanation! Please upload lots of these.

[@stablesort]

Thanks for the compliment! By the way, if you have suggestions as to what other comp. sci. topics you'd like to view, please do let me know. Cheers!

[@puneetkumarsingh1484]

@@stablesort Sir, videos on the following topics will be very helpful. 1.Optimal Binary Search Tree. 2.Huffman Decoding and encoding 3.Assembly Line Scheduling 4.Maximum Bipartite Matching 5.Push Relabel Algorithm(Related to flow algorithms) 6. Johnson's Algorithm(Shortest Path) I hope its not too much!

[@stablesort]

@@puneetkumarsingh1484 This is perfect, thank you. Some of these I only have a vague recollection of so it'll be fun for me to research into. By the way, as far as Optimal Binary Search Tree topic, one of the ways to achieve this is via "Treap" data structure - you may be interested in viewing this video I made a while back: kzbin.info/www/bejne/q6i6gIh3mbSHn8k

[@puneetkumarsingh1484]

@@stablesort Thanks I will surely watch it. Other than this, I know that it is also solved using Dynamic Programming.

[@weizhou8888]

Never got disappointed whenever I spent n minutes of time on this channel where 0

[@stablesort]

Glad to hear that there was at least 1 minute that was worthwhile =)

[@PallNPrash]

I love this channel and how complex algorithms are explained so clearly....Thank you SO much!! And please keep adding more videos.

[@stablesort]

Thank you! Will do!

[@highruler2786]

Brilliant! The way you illustrated the problem with cards, piles and pointers in such a neat and timely matter finally made me understand the logic needed to find the Longest Increasing Subsequence! I struggled a bit to actually implement the algorithm, but now that I have I feel like I've gained the mastery needed to explain this to others if need be. Well done! As for suggestions, what about the Partition problem where the goal is to divide an array of integers in two such that the sums of the two array parts are as equal as possible? I would love an explanation of that!

[@stablesort]

I am glad to hear it =). And thanks for the suggestion about the partition problem. I haven't heard it before and it sounds interesting. I'll give it a shot!

[@stablesort]

Here you go, as promised: kzbin.info/www/bejne/bXPcn4ivatKfZqs

[@highruler2786]

@@stablesort That's awsome! I'm glad you also found the easies hard problem interesting :) Great video!

[@stablesort]

@@highruler2786 Yeah, it's fascinating stuff. I am currently playing around with algorithms for partitioning into not just 2, but M number of partitions. And this turns out to be also a very interesting topic. It has practical implications, such as operating system handing out tasks to M number of CPUs on a computer, with each task having some specific cost. Thanks again for suggesting the topic!

[@highruler2786]

@@stablesort That's very cool! I'll be sure to see what you come up with in your next episode. And you're very welcome. Is so nice to see your explanation of a problem I've struggled with.

[@abdulkk49]

Crisp, Clear & Brilliant!

[@stablesort]

Glad you enjoyed it!

[@navidr2811]

best explanation of this problem so far I came across

[@stablesort]

Thanks for the compliment!

[@abhinavraut3099]

Came here from the comment section, a short tour of code would've been better. Loved the video thanks

[@stablesort]

Agreed and thanks for the feedback. This was my very first video. Most episodes that followed do have a code walk through. By the way, there is a source code linked in the description.

[@semajxocliw]

thank you kind man for preventing me from failing my final semester of CS

[@stablesort]

Great to hear that my little video made such a good impact! I am also a little surprised that this problem would be on a final exam... This is not an easy problem to figure out in a time frame of an exam... In any case, cheers!

[@oribenez]

One of the best explanation on LIS with time complexity of nlogn. Thanks in advance❤🙏🏼

[@sonalskitchen1320]

Very well explained , and with good examples. Thanks for your effort.

[@stablesort]

Glad to hear it!

[@haaarshiiiit]

Excellent video ! Please keep making more of these.

[@EduardoSernaL]

This is an amazing explanation! Thank you so much for the intuition section!!!!

[@stablesort]

You are very welcome!

[@sagargaddam3445]

This was awesome. Simple and clear explanation. Do more videos plz. Thank you.

[@stablesort]

Thanks, will do! By the way, got any suggestions for a topic? I am always looking for a subject that hasn't been done yet (or done by not well)?

[@yasser_hussain]

I have rarely had this much fun learning a difficult algorithm like this. Hope you expand your operations. 😁

[@stablesort]

Thanks! =)

[@rejetimeghavardhan7805]

Me too

[@manojkvn2632]

Awesome explanation of concept behind algorithm, which helps in coding and remembering algo easily , Please continue the great work

[@stablesort]

Thanks for the compliment. In case you need it, there is also java source code, linked in the description. Cheers!

[@manojkvn2632]

@@stablesort I have checked the algorithm and seems self explanatory , just a suggestion can replace m = l + (r - l) / 2; to m=(l+r)/2 ie., (low+high)/2 since the previous is confusing.

[@stablesort]

@@manojkvn2632 Done, thanks for the suggestion. I like your formulation better =)

[@CrazyDreamer1001]

They both work when l and r are small compared to the range of the data type used, but m=(l+r)/2 will cause overflow for large values while l + (r - l) / 2 will not. That's why that one should be used in real code.

[@stablesort]

@@CrazyDreamer1001 Good point! Perfect example of the need to do peer code reviews and testing. I totally did not think about that scenario. Thanks for pointing this out.

[@AshishRawat-zl6te]

It's a really amazing way to explain. I really loved it. Please keep up this good work.

[@stablesort]

Thank you! I'll do my best as time permits =)

[@tonystarc9567]

What a peaceful explanation.

[@stablesort]

I hope it was useful!

[@vinayjangra1401]

2:45 what if the cards are [100, 10, 5.....] , then choosing left most will not allow the wide range of cards to place?? what to do in that case

[@user-uh3zr7mo4i]

You earned a sub sir :) You have a way of teaching I suggest you to pick difficult/ tricky questions from leetcode and start explaining on your channel. I guarantee you, your channel will explode.

[@stablesort]

That's a great suggestion, thanks! If only I could have more time these days for hobbies =)

[@shahzadqadir5191]

Great video, very helpful to understand the concept of increasing subsequence.

[@joshika5391]

Amazing explanation and insightful illustrations! Thanks a bunch!

[@stablesort]

You're very welcome!

[@dmanrox2]

I know binary search was mentioned at the end but it would have been nice to explain with the visualization that since the top card on the piles are strictly increasing, we can do binary search over them to find the next pile, which is how we can guarantee O(nlogn) time.

[@AL-jr7zu]

Thank you, I loved this video. It was short and simple.

[@RitikKumar-dm7eo]

Greatest Explanation Ever I saw

[@vishalmishra7018]

Beautiful explanation.

[@stablesort]

Thanks for watching and leaving a compliment!

[@ciachn]

This is so cool! I lost an exercise in a contest because I had to use segment trees, and those are awful. - I wish I had known this! 😅😅😅

[@jessiew4271]

Thank you so much!! Such a clear explanation!

[@stablesort]

You are very welcome!

[@chetanraikwar3546]

The name of this channel is vety interesting. . . *Stable Sort* 😀

[@stablesort]

Yeah, perhaps I should actually make a video on what it means =)

[@amitbendkhale646]

Really great video, lot of insight provided there!

[@stablesort]

Great to hear!

[@gabhinav001]

Could someone explain how we can retrieve the Longest Increasing Subsequence(LIS) from the piles formed above? I did not understand the pointer concept thoroughly, though I understand that there will be Longest Increasing Subsequence(LIS) in the above decks. To be more precise, how do we determine which card we pick from each pile to be included in the LIS? Thanks in advance!

[@RitikKumar-dm7eo]

Kindly keep uploading more such concept

[@stablesort]

Thanks! By the way, please do let me know if there is a subject that you'd like me to make a video about. I am always looking for new ideas. Cheers!

[@muditsingh2313]

Thanks! This is the best explanation I ever had

[@stablesort]

Glad it helped!

[@arthurd4012]

Great, I just coded this up! :)

[@shikharchaudhary6984]

the explanation was just amazing

[@doppelganger2545]

Great set of videos with clear and succinct explanations. @Andrei, any plan to add more content in the future?

[@stablesort]

I have the plans just haven't had much time lately... But I definitely want to add to the series.

[@raffaelemannarelli1747]

beautiful explanation

[@SevenRedSun_s]

FINALLY,!!!! i understand this :D, this video helpme a lot, thanks : )

[@u2blr]

Thank you so much for making those amazing videos.

[@stablesort]

Thanks for the compliment!

[@ahanapanja3372]

Brilliant!! Thank you.

[@valerak005]

Thans very much for the great explanation!

[@nbenari]

Awesome work. Thanks!

[@stablesort]

Cheers!

[@ValentynPonomarenko-h8k]

Thank you for clear explanation.

[@anonymoussloth6687]

if we wanted to sort using this strategy, it would take nlogn to make the piles plus O(max pile size) to merge the k piles right?

[@waisrainy]

MAKE MORE CONTENT. Great work.

[@stablesort]

Thanks! More episodes are in the making =)

[@kshitijgupta6976]

very good explanation. it will be great if you also show code. find link of this video in leetcode LIS solution discussion

[@stablesort]

Thank you, I do appreciate your feedback. This was my very first video made. Since then pretty much all of the other videos have some code walk through. Cheers!

[@SM-dy9om]

At 03:20 and "still left with only 2 piles". didn't understand the logic.

[@stablesort]

There are a couple of tricky points here to keep in mind. You want to place the card 5 on top of 10 instead of 100 so that if some larger card, for example 50, comes later on, you'd be able to place it on top of 100, ending up with only 2 piles. The top cards of those two piles would be 5 and 50. On the other hand, had you placed the 5 on the 100, then when 50 comes along, you'd be forced to create a new pile. So going with the 1st option minimizes the number of piles. Let me know if this makes sense.

[@SM-dy9om]

@@stablesort got it now, it's perfect and thank you for taking the time to reply! :) I will recommend your channel to my friends, and best wishes!!

[@terencelobo2297]

@@stablesort But does not the patience sort algorithm prevent that by stating that 5 should be on left-most pile. If the order was "100, 10, 5, ..." the leftmost pile would be 100 and 5 would be on top of it. No ?

[@stablesort]

@@terencelobo2297 Thanks for the question. In your scenario when the order is "100, 10, 5, ...", the 10 would be placed on top of 100. So then you just have one pile. Then 5 comes along and is placed on top of the 10. Note that since there is just one pile at this point, the longest possible increasing (or non-decreasing) sub-sequence is of length 1. I hope this helps but let me know if you have more questions. Cheers!

[@HS-dv1fv]

its really nice explanation.but I wanna know how to write a code.so it would be better to show your code examples. Anyway, its the best explanation I've ever watched!!Thank you!!

[@stablesort]

Thanks for the suggestion. Most of my other videos do discuss the specifics of implementations. For this one, however, the source code is linked in the description.

[@HS-dv1fv]

@@stablesort Oh!Sorrry!I missed it!!Thank you so much!!!

[@HimanshuSharma-tm2ms]

Very well explained , thanks a lot:)

[@stablesort]

Thanks for watching and thanks for leaving a nice comment =)

[@anonk811]

How can we keep a linked list of actually LIC (or any ds) with the simpler solution (7-8 line solution where we just have a piles[])? How to capture the left pile element when a new pile is created? Also, will it ot not break when the first element of a new pile is pointing to the top (at that time) of the left pile and then this current pile has another element later on top which was pointed from yet another new pile top element on its left? e.g. [10, 5] [8] here 8 → 5, but then later the top elements of these two piles are [5] [8] and 6 comes so it becomes [5] [8, 6] i.e [5] [6] as only top element is visible and then 7 comes, so we have third pile now [5] [6] [7] which is pointing to 7→ 6? Do we do linked list insertion now?

[@stablesort]

Thanks for your question. As each card is placed on some pile, you also store a pointer from that card to whatever is the current top most card of the pile immediately on the left. Later on, there may be more cards added to both of those piles but the original pointer is still liking up the original two cards. The source code of a fully functional Java implementation is linked in the description, but here it is again: bitbucket.org/StableSort/play/src/master/src/com/stablesort/challenge/LongestIncreasingSubsequence.java I hope this helps!

[@alexweaver9068]

Very good explanation, thank you.

[@AADIL997]

thanks for such a wonderful explanation

[@stablesort]

I am glad you liked it =)

[@nqz3]

man this solution is so good

[@gagandeepsingh2925]

Nice video

[@stablesort]

Thanks, Gagan!

[@HAL--vf6cg]

If someone's not convinced, think of it this way: You can never include 2 numbers from the same pile in an increasing subsequence. If I take A and B from the same pile (and let's say B came after A), then B

[@ShavkatRakhmonov-nb6su]

Thank you a lot for the video! Why you have stopped posting videos? They are amazing!

[@backistall3452]

Great video. Please upload more videos)

[@egortkachenko]

Very good vieo, thank you for that simple explanation!

[@stablesort]

Спасибо за комплимент!

[@red_and_black_UA]

Nice done!

[@stablesort]

Thanks!

[@iliasp4275]

very nice! thank you!

[@stablesort]

You are very welcome!

[@softwareinterviews2713]

Amazing videos! Can you make one about Manacher's algorithm on longest palindromic substring?

[@stablesort]

Thanks for the suggestion, I'll look into it!

[@1998charan]

Can you explain how pointers to card gives the sequence?

[@stablesort]

Hi Sri, The pointers are an extra piece of information that you keep as you place down cards into piles. A pointer goes from a card that you just put down to the *top* card of the pile on the left, whatever that top card happens to be at that moment in time. Later on, as more and more cards are placed, that pointer may be pointing to the card that's now in the middle of the pile. The example in the video shows this scenario as pointer from card 8 to card 5 - later on, a new card 3 is put on top of 5, but the original pointer still points from 8 to 5. So, at the end of the game, if you start with the pile on the right (any card on the right most pile will do) and follow the pointers to the left, you recover an increasing sequence, but in reverse order. We can then prove that this also happens to be the longest sequence. Does that help?

[@1998charan]

Got it. @@stablesort Thank you so much brother. BTW you did a good job

[@stablesort]

@@1998charan Thank you, I do appreciate the words of encouragement!

[@Omsy828]

@@stablesort This comment is crucial, I was very confused about the pointers when watching. This clears it up

[@jacobkurien]

good one

[@stablesort]

Thanks!

[@vishalsingh118]

perfectttttt.........

[@stablesort]

I am glad to know that the video helped!

[@amogchandrashekar8159]

Subscribed!

[@stablesort]

Welcome aboard!

[@dashdoom8452]

You are the goat