Longest Increasing Subsequence O(n log n) dynamic programming Java source code
Вставка
- Опубліковано 5 жов 2024
- Given an array of random numbers, find a longest increasing subsequence. This subsequence is not necessarily contiguous, or unique.
In this tutorial we illustrate a dynamic programming (DP) solution that runs in O(nlogn). Source code is available in Java. Two proofs are also presented. The first proof is done by induction. The second proof makes use of the fact that Patience Sort algorithm minimizes the number of piles, and since each pile contains cards in decreasing order, any increasing sequence can have at most one card from each pile.
This programming challenge is commonly given during technical/coding interviews at engineering firms such as Google and Microsoft.
Source code, implemented in Java:
bitbucket.org/...
Wikipedia: en.wikipedia.o...
"Patience Sort" is a general purpose sorting algorithm that in the process of sorting also finds a longest increasing subsequence. This video explains how the Patience Sort works by placing numbers (playing cards are used for illustration) into piles of decreasing values. If we also keep a pointer from the placed card to the top of the pile immediately on the left side, chains of pointers get created, leading to the left most pile. So at the end, you can pick any card on the right most pile and follow the pointers to the left most pile, recovering the (or one of the) longest increasing subsequence in reverse order.
Informal proof:
Since the cards within a pile form a decreasing sequence, any increasing sequence can use at most one card from each pile. So regardless of what strategy you use to play the game, the number of piles is always ≥ the length of any increasing sequence.
Since "Patience Sort" greedy strategy minimizes the number of piles and each pile is linked via pointers, following the pointers gives us a longest increasing sequence.
Proof by induction:
The first card, lets call it card-1, is put into pile-1 and obviously creates a subsequence of length 1. That’s our base case.
For the second step, assume that after placing the nth card, card-N, into a pile-K, a subsequence of length K is created. Lets see if this holds true for the next card, cardN+1. If cardN+1 is greater than card-N, it won’t be placed onto any pile to the left of pile-K since "Patience Sort" greedy strategy would have placed the previous card, card-N, into that pile instead of pile-K.
And it won’t be placed into pile-K since the rule for "Patience" game does not allow it.
Thus, cardN+1 is placed into some pile to the right, thereby, increasing the length of the previously calculated subsequence.
Finding the needed pile takes O(log n) time using binary search. This needs to be done for each card, so the overall running time is O(n log n).
leetcode 300 "Given an unsorted array of integers, find the length of longest increasing subsequence"
leetcode.com/p...
Written and narrated by Andre Violentyev
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.
I hear you. Thanks for leaving a few good words.
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!
so true, this is the most important part to understanding and it is usually completely skipped over for some reason
I like how 100th of club is designed
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 =)
Awesome. That’s the best explanation of finding the longest increasing subsequence I’ve seen. Thanks for the video!
I cam here from other channel's comment section,
Not going back now...
I am glad to hear that you found this video useful =)
Lol. Let me guess... Tushar Roy??
@@mindyourbusiness46 😂
@Hank Hudson Okay stop sending this same message to every educational video. or are u a bot.
There are only 2 UA-cam videos explaining the problem in O(nlogn) time. Your explanation is very clear and you are awesome!
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!
@@stablesort THANK YOU SOO MUCH!!!!!!!!!
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
Awesome, thanks for the good words!
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.
Simple, concise and the best explanation of longest increasing subsequence! Subscribed :) We need more of this!
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.
this channel is so underrated
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!
Sweet! Thanks for the feedback and thanks for subscribing!
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.
You are very welcome! Thank you for such a wonderful compliment!
I keep coming back to watch this again time over time. The best explanation of the algorithm of all time.
Thanks, I do appreciate your feedback!
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 !!
Glad you liked it!
the best explanation so far for longest increasing subsequence problem in nlgn time.
I do appreciate your good words! Cheers!
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
Thanks for the compliment! Glad to hear that you enjoyed the video =)
WOw sir,you made my day.I came to your video after the lonegest sub sequence problem
Thanks! Your comment gives me inspiration to make more videos! By the way, any suggestions as to what topic to cover next?
@@stablesort you should make more videos on other algorithmic paradigns like greedy,dynamic programming (mainly cause i sucks at dp)
@@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.
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.
Glad to hear it and thanks for the compliment!
I really appreciate the graphics, and your calm voice. You are very relaxed for someone whose last name is VIOLENTey
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 =)
Haha that sounds like an algorithm problem in itself!
@@nobsreviews8814 True! 8-P
Never got disappointed whenever I spent n minutes of time on this channel where 0
Glad to hear that there was at least 1 minute that was worthwhile =)
thank you kind man for preventing me from failing my final semester of CS
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!
Damn, that's impressive.
Most dp algorithms are n*m, so n log n is a nice improvement!
I watched it 3 times and finally understood!!
This video was awesome :) (u earned a sub!)
Great!
the best explanation i've seen so far, very good job!
Thanks for the compliment!
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.
Good point!
Hands down, the best explanation I've seen on UA-cam
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.
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!
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".
@@stablesort The DP solution, there are not enough contents only for the DP solution.
@@SeyhunSaryldz Roger that. Thank you for the suggestion (as well the one about DP content).
I solved it. I understood the problem after looking at your cards example, the example made this algorithm clear for me.
Glad to hear that it was helpful!
Great explanation! Thanks for demonstrating why the algorithm provides the optimal solution.
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!
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!
Here you go, as promised: ua-cam.com/video/7BynUy5ml0I/v-deo.html
@@stablesort That's awsome! I'm glad you also found the easies hard problem interesting :) Great video!
@@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!
@@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.
probably the clearest explanation I've seen. Thanks!
Thanks for the compliment!
Very well explained , and with good examples. Thanks for your effort.
Glad to hear it!
Please, keep making videos. Your explanations are the best
Great video. U should do more, their quality is ideal and very much needed
Thanks for the words of encouragement!
Thank you for including proof of correctness in your video. It really helped convince my stupid little brain
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
Crisp, Clear & Brilliant!
Glad you enjoyed it!
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.
Please keep posting more videos. Every video is top quality.
Thank you, will do!
Wow !!
A lot of thanks, I've been searching for 2 hours, your explanation is short and so clear.
You are amazing !
best explanation of this problem so far I came across
Thanks for the compliment!
One of the best explanation on LIS with time complexity of nlogn. Thanks in advance❤🙏🏼
I love this channel and how complex algorithms are explained so clearly....Thank you SO much!! And please keep adding more videos.
Thank you! Will do!
Appreciate the brief video. Action packed!
Thanks, I appreciate your compliment!
This was awesome. Simple and clear explanation. Do more videos plz. Thank you.
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)?
What a peaceful explanation.
I hope it was useful!
I have rarely had this much fun learning a difficult algorithm like this. Hope you expand your operations. 😁
Thanks! =)
Me too
This is an amazing explanation! Thank you so much for the intuition section!!!!
You are very welcome!
Excellent video ! Please keep making more of these.
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! 😅😅😅
Extremely Clear Explanation! Please upload lots of these.
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!
@@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!
@@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: ua-cam.com/video/uwWOUAdOTig/v-deo.html
@@stablesort Thanks I will surely watch it. Other than this, I know that it is also solved using Dynamic Programming.
It's a really amazing way to explain. I really loved it. Please keep up this good work.
Thank you! I'll do my best as time permits =)
Thank you so much!! Such a clear explanation!
You are very welcome!
Greatest Explanation Ever I saw
Thank you, I loved this video. It was short and simple.
Came here from the comment section, a short tour of code would've been better. Loved the video thanks
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.
Amazing explanation and insightful illustrations! Thanks a bunch!
You're very welcome!
beautiful explanation
The name of this channel is vety interesting. . . *Stable Sort* 😀
Yeah, perhaps I should actually make a video on what it means =)
Awesome explanation of concept behind algorithm, which helps in coding and remembering algo easily , Please continue the great work
Thanks for the compliment. In case you need it, there is also java source code, linked in the description. Cheers!
@@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.
@@manojkvn2632 Done, thanks for the suggestion. I like your formulation better =)
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.
@@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.
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.
That's a great suggestion, thanks! If only I could have more time these days for hobbies =)
Really great video, lot of insight provided there!
Great to hear!
the explanation was just amazing
Kindly keep uploading more such concept
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!
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
Awesome work. Thanks!
Cheers!
Thank you a lot for the video! Why you have stopped posting videos? They are amazing!
Great video, very helpful to understand the concept of increasing subsequence.
Great set of videos with clear and succinct explanations. @Andrei, any plan to add more content in the future?
I have the plans just haven't had much time lately... But I definitely want to add to the series.
Beautiful explanation.
Thanks for watching and leaving a compliment!
Great, I just coded this up! :)
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!!
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.
@@stablesort Oh!Sorrry!I missed it!!Thank you so much!!!
Brilliant!! Thank you.
Thanks! This is the best explanation I ever had
Glad it helped!
MAKE MORE CONTENT.
Great work.
Thanks! More episodes are in the making =)
thanks for such a wonderful explanation
I am glad you liked it =)
very good explanation.
it will be great if you also show code.
find link of this video in leetcode LIS solution discussion
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!
Very well explained , thanks a lot:)
Thanks for watching and thanks for leaving a nice comment =)
Thank you so much for making those amazing videos.
Thanks for the compliment!
FINALLY,!!!! i understand this :D, this video helpme a lot, thanks : )
Very good explanation, thank you.
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!
Very good vieo, thank you for that simple explanation!
Спасибо за комплимент!
man this solution is so good
Amazing videos! Can you make one about Manacher's algorithm on longest palindromic substring?
Thanks for the suggestion, I'll look into it!
Nice done!
Thanks!
very nice! thank you!
You are very welcome!
Great video. Please upload more videos)
so basically find the lower_bound of all the top of the piles to place a new card
perfectttttt.........
I am glad to know that the video helped!
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
Can you explain how pointers to card gives the sequence?
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?
Got it.
@@stablesort Thank you so much brother.
BTW you did a good job
@@1998charan Thank you, I do appreciate the words of encouragement!
@@stablesort This comment is crucial, I was very confused about the pointers when watching. This clears it up
Subscribed!
Welcome aboard!
Your code gives wrong answer as [5, 3, 4, 12] instead of [5, 8, 9, 12 or 11]
Thanks for pointing that out. There was a bug in the binary search. I fixed it and checked in the updated code. Cheers!
good one
Thanks!
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?
while you are sorting in 10 100 but taking 5 which is less than both is not a good example of patience sorting 5 should start its own set.
Thanks for posting a question. 5 does not start its own set because it is smaller than both 10 and 100, which are showing on the table. The algorithm places smaller cards on top of bigger ones. The question there is, which pile to place it on, the 10 or the 100? I'll let you watch the video to see why it places on the left most pile.
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?
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!
Dope explanation aside, from where I can get that shirt lol?
Haha, I had to travel to Indonesia to get it - it's a 'batik' shirt, a cultural art form of Indonesian people =)
Can I make a request - Dijkstra's algorithM/
Great, I'll add that to my list of topics. Thank you!
Nice video
Thanks, Gagan!