Programming Interview Question: Longest Increasing Subsequence nlogn

Given an array of integers, find the longest increasing subsequence in O(nlogn) time
Example:- {3,1,5,2,6,4,9}
Answer:- {1,2,4,9}
Source code: -
github.com/IDeserve/learn/blo...
Longest Increasing Subsequence Algorithm is explained with examples and visualizations.
Website: www.ideserve.co.in
Facebook: / ideserve.co.in

[@IDeserve]

Dear Friends, If you like our content and would like us to continue making great content for you, please spread the word about IDeserve. A share/appreciation from you on social network would mean the world to us! Also, do like our Facebook page: facebook.com/IDeserve.co.in :) Thanks, -Team IDeserve.

[@talk2patel]

you videos are awesome. thanks you so much for your time and effort. I request you to create some videos around design questions. below are some questions: 1. Design a website like foodpanda. 2. how wound you design a search enginer like google. Thanks

[@saijayavinothtvs2588]

for some problems, some teach the concept exceptionally,,,for this you did that...thank you

[@kingshukjana7070]

best video i have seen for the problem, compared to any other website.

[@IDeserve]

Thanks KINGSHUK for your kind words :) If you would like to request a new video, here is the process: kzbin.info/www/bejne/aZe0fYKcqrKZopI We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Thanks, -Team IDeserve.

[@piyush12121]

I found your videos better and succinct than other videos present on youtube. You guys have taken it to the next level !

[@IDeserve]

+Piyush Chaudhary Thanks a lot for your words :) We are striving hard to make understanding algorithms easier. We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like algorithm visualizations, learn together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@LokendrarewapatiRewapati]

First of all want to say you thank you very much for explaining such a difficult concept in a easy way. Very nice KD.

[@IDeserve]

Thanks a lot for your words Lokendra :) We are striving hard to make understanding algorithms easier. We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@shanmukhchandrayama8508]

This channel has the elegant solutions , I am really awestruck after watching few videos. This guy thinking out of box and coming with impressive solutions.

[@IDeserve]

Thanks Shanmukh!

[@FabianLandwehr]

Excellent video, thank you!

[@SphurtiDance]

amazing insights provided!! loved it!!

[@IDeserve]

Thanks for your kind words :) We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@sarwarjahan05]

Great explanation. I've gone through many videos & blogs. But this one is the easiest to understand.

[@IDeserve]

Thanks Sarwar!

[@sulekhakumari-hs4gy]

best video for LIS . thanks man. Please do keep posting such videos.

[@IDeserve]

Thanks Sulekha!

[@falakk22]

astounding explanation, Thanks Fella !

[@IDeserve]

Astounding comment once again!

[@dparthade]

Dear iDeserve Team, This is a great video. But I want to make a point that the increasingSub [] is actually holding the index of the element in the original array. It is not holding the actual element( as shown in the illustration). Otherwise it will be impossible to find the parent of a particular element. The code given also supports my statement :-) If possible please give a correction note. :-)

[@IDeserve]

Thank you Partha De for your suggestion. We will review the video and add a correction note if required. Thank you, Team IDeserve

[@AbhijeetGopalraoKandalkar]

I also got confused after going through code. Please do it.

[@vm1662]

Thank you so much! Excellent video.

[@IDeserve]

Thanks Aishwarya!

[@whatidashdashdash8866]

Thanks I watched the first graph explanation

[@vidhishah9154]

Thank you for this explanation. . You made it really easy. Can you please share link of patience sort explanation for this problem as you mentioned in video ?

[@palakkharbanda330]

ThankYou.Great Job bro

[@ankitiiita]

Hey , How will this work for {1,2,3,0,1,2,3,4,5,6} plz explain

[@randeepsingh6457]

Nice, thanks !

[@siddhartha19891]

Awesome Explanation !!

[@IDeserve]

Thank you so much Siddhartha for your kind words :)

[@trankhoinguyen7968]

very easy to understand , tks u so much

[@IDeserve]

❤️

[@cl1987]

That's amazing. Thank you soooooooooooooooooo much

[@IDeserve]

Thank you so much for your kind words Lilian!

[@venkatagopikolla636]

When you say there are to sequences under consideration, how do you track the number of sequences in consideration in code?

[@tranha2986]

Best video for LIS!

[@IDeserve]

Thanks Tran!

[@rishabhdhiman9422]

How is the method you described any different than the patience sort variant?

[@liveon7400]

Well explained!

[@IDeserve]

Thanks!

[@shantanukumar7061]

Hey, Please share the link of the video for finding Longest Increasing Sub-sequence using patience sorting

[@mohit4231]

Awesome explaination :)

[@IDeserve]

Thank you so much Mohit for your kind words :)

[@gmlmrinalini9794]

can u plz provide the link to same problem solved using patience sorting?

[@shivamgarg3069]

Excellent tutorial but sir where will i get video for patience sorting?

[@VIRAJBHOSLE]

Thank you for the video. One note, the code will work only for strictly increasing sequence. For example for 2, 2, 2, 10, 10, 3, 3, 3, 4, 4 the code will return 2, 3, 4 not 2, 2, 2, 3, 3, 3, 4, 4 For the monotonically increasing/non decreasing sequence we may have to use a Node with current value and previous index/value and link those.

[@noecameron603]

I dont mean to be off topic but does anyone know a way to get back into an Instagram account? I somehow forgot my password. I appreciate any tips you can offer me!

[@dashphillip9704]

@Noe Cameron Instablaster ;)

[@noecameron603]

@Dash Phillip I really appreciate your reply. I found the site through google and im trying it out now. Takes quite some time so I will get back to you later when my account password hopefully is recovered.

[@noecameron603]

@Dash Phillip It worked and I finally got access to my account again. I am so happy! Thanks so much, you saved my ass !

[@dashphillip9704]

@Noe Cameron You are welcome xD

[@jabazindian3957]

Sir you are doing great job.

[@IDeserve]

Thanks for your kind words :) We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@jabazindian3957]

Of course why not for such selfish work you deserve that. I already told many of my friends about your work. Your work is masterpiece. The way you explained manacher algorithm is marvelous. Keep it up that kind of effort sir.

[@IDeserve]

Thanks for your kind words again :)

[@techie773]

can some one explain how he had used binary search to find position

[@izzyzhao8627]

Hi sir, thank you so much for your intuitive explanation. Best I've watched so far. A question around 7:50 regarding why do we replace if smaller. Even if we replace 9 with 7, and an 8 comes after. 8 would still fall under 10. Which does not make LIS any longer.

[@izzyzhao8627]

I think my brain is jammed around this step. I understand why we track parents but still can't get the intuitive idea of why do we replace. Any further explanation would help. Thank you!

[@SV-zi9os]

kzbin.info/www/bejne/aGPWYquuh9usaJo This algorithm is kind of doing patience sort thing, its just that we are keeping only those things that are necessary (only last element of each pile, and pointers)

[@sarwarjahan05]

Imagine we have another 9 after the 8. So, replacing 10 with 8 will help to increase the length. But if we keep 10 we can't increase length by appending 9.

[@spirridd]

Awesome!

[@IDeserve]

Thanks Дмитрий Пухов for your kind words :) We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@ricardosmith3752]

how will it work in case of duplicate numbers

[@geocine]

the parent of 5 is 1 right so should I put 1 for the parent array of 5?

[@priyamraj7548]

Ohh the easiest explanation in the whole fucking Interenet, thank u bro very much !

[@IDeserve]

You are welcome Priyam!

[@vinayaksangar1928]

Hello IDeserve I have a same doubt as Anish Singh Please clarify the doubt Lets suppose take two examles arr1[] = {1,2,57,58,100,4,101} arr1[] = {1,2,57,58,100,4,5,7,8,9} Now these are two examples (indexing from 0) when we apply your algorithm if we reach at i = 5 ie when arr1[i] = 4 and arr2[i] = 4 in both cases LIS till now would be 1

[@vinayaksangar1928]

Extremely sorry Ideserve for asking You mentioned it in the insight section Posting results for those having the same doubt ideone.com/3ux3Sd In case 1 when we came at i = 5 we replaced 4 with 57 in LIS till then which now becomes 1

[@mahadeiv2458]

In your illustration - {3,5,6,9} {1,2,6,9} {1,5,6,9} are also valid, why haven't we considered them as longest sequence ?

[@sahulrajhansa8363]

Well, most of the time you are required to find the length of the longest increasing subsequence rather than finding the actual numbers.

[@ytuser659]

any one answer will work ... you don't have to find out all the combinations

[@suryakantasahoo9935]

why do we have to store the indexes not the elements in the increasingSub array?

[@misteralagiz4003]

good video, thanks mate

[@IDeserve]

+artem alagizov You are most welcome! Please feel free to suggest any feedback you might have. You may also want to checkout our web-portal www.ideserve.co.in which has in-built Code Visualization feature depicting frames and objects of the code being executed. Thanks again. Cheers!

[@misteralagiz4003]

+IDeserve the website looks brilliant, i like the design and the selection of problems covered. i'll definitely give it a go, thanks for your work! are you planning on covering advanced sorting algorithms? maybe it's done already, i didn't spot it yet

[@IDeserve]

+artem alagizov For now we have covered topological sorting for graph vertices. Could you please let us know which sorting algorithms you would be most interested in? We will try to create videos for those. Thanks for your inputs :-)

[@misteralagiz4003]

+IDeserve great! i will check the one you mentioned how about smoothsort and polyphase merge for the future? i reckon people as well would appreciate high quality videos on good old heap, merge and so on, and what would be a good choice of a sorting algorithm for a variety of particular cases keep up the good work bruv

[@IDeserve]

+artem alagizov Thanks for the suggestions! All the sorting algorithms are in pipeline including smoothsort, polyphase merge, heap etc. Thank you for appreciating. This encouragement will keep us going!

[@srikantd6054]

Hi , For this Input array {10,9,2,5,3,7,101,18}.The longest increasing subsequence is {2,3,7,101}. But when I ran your code which you shared on github i got the output as {2,3,7,18}.Can you please look into this whenever you get time. Thanks srikant

[@manishchauhan326]

Prabhu charan khan he aapke, Excellent solution

[@IDeserve]

😂 Bhai! Aapko apki dream job bahut jaldi mile 😊

[@manishchauhan326]

@@IDeserve thanks dude

[@palakkharbanda330]

Does this question seem somewhat like Kadane's algorithm?

[@jamesqiu6715]

This is DP solution?

[@anish167]

Consider the following example {8,3,4,2,5,6}. As per the algorithm when we pick up 2 we have to replace 3

[@bobesfanchi]

Did you figure it out?

[@bobesfanchi]

It seems like you only replace the number. So it will become 2,4,5,6 and somehow this produces the correct result. It don't understand why exactly it works at the end.

[@prajaktakarandikar3459]

It goes like 8, then 3, then 3

[@sriramsubramanian1291]

Here's the method. let's say | n1 | n2 | | | | | n3, n4 n5 now only you replace n2 by n3 if n1 < n3 | n3 | n2 | | | | | and continue . Hope, this helps.

[@cskwillreturn2473]

@prajakta karandikar No yu r wrong. It shuld be 3

[@kartikjain7935]

How will it work for {10, 22, 9, 33, 21, 50, 41, 60,80}..Please explain?

[@prithvimonangi5080]

Hi, Is this line increasingSub[pos] = i; correct? Shouldn't it be increasingSub[pos] = X[i]i; ? As we need to append or replace the element at ith index of X to the array increasing Sub, it should be X[i]. please verify. Please check.

[@the_sweet_heaven]

If the sequence is like {3,1,5,2,6,4,0,9} then at i = 6, would you be applying rule 2 ? as 0

[@the_sweet_heaven]

got my answer(yes)

[@runjeethnikam957]

excellent video

[@IDeserve]

Thanks Runjeeth!

[@BipinOli90]

nicely done

[@IDeserve]

Thanks Bipin for your kind words :)

[@ms0372631]

Best explanation so far! Thanks!

[@IDeserve]

Thanks Alan!

[@MadhanAK2010]

{1,2,4,9,10} is also a valid sub sequence whose length is 5. Shouldn't we return the length of the maximum increasing sub sequence as 5 in this case?

[@IDeserve]

Hi Madhan, element 10 is not present in the input array itself therefore the sequence {1,2,4,9,10} cannot be the valid sub-sequence. Please check out our website www.ideserve.co.in for more such questions. Thank you, Team IDeserve

[@dhaval12593]

hello, thank you for the explanation. one doubt in the code, In // replace or append shouldn't it be increasingSub(pos)= X(i) ?? thank you,

[@dhaval12593]

oh I think I got it.. the increasing subseq array is storing the indices from X, but in the video we r actually storing the values. That led to the confusion...

[@IDeserve]

Hey Dhaval, If you would like to request a new video, here is the process: kzbin.info/www/bejne/aZe0fYKcqrKZopI Thanks, -Team IDeserve.

[@er.rohitshende2357]

Thanks

[@IDeserve]

Thanks Rohit for your kind words :) We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@KshitijSharmaMe]

Explaination?

[@oceanbhardwaj5471]

Thanks sir for relating this problem with LCS But while doing with LCS after sorting it will fail for some test case like Arr={2,2,2,2} Here LCS=4 But Lis=1 BTW your way of explaining approaches was good..thanks

[@ujjwalkumar8173]

if we make all the elements distinct in that sorted array and then taking its LCS with given array then I think this problem will be solved.. ??

[@oceanbhardwaj5471]

@@ujjwalkumar8173 yes u are right ,it should work !!!! Thanks a lot😊

[@prajaktakarandikar3459]

What a genius algorithm!!

[@IDeserve]

Thanks prajakta for your kind words :)

[@ytuser659]

should have used array representation to denote storing of sequences rather than using arrow diagrams (at 3:06). makes it much harder to visualize the arrows into code

[@ぶらえんぴん]

There is a detail I seem not find there in the video. When in last you explain how to get the sequence you said start from 7 or 10. How do you know where the 10 is? Do you have to store another array to help saving the index of 10?

[@IDeserve]

+Brian Pin Sorry for late reply. To find out the actual sequence which ends at 7 or 10, we make use of parent[ ] array which stores the parent index for each element of the array. In this case, to find out the sequence ending at 7, since element 7 is at index 8, we look at parent[8] which is 5, then we look at parent[5] and so on until we hit parent[i] value as -1. Please note that increasingSub[ ] array also stores the indices and not actual elements. These indices are then used for updating parent[ ] array. I hope this helps. Thank you, Team IDeserve

[@jkrw3540]

@@IDeserve I think this is not what he is asking. He wants to ask how to get the last index of the longest subsequence with length 5. How to know what is the last index of the longest increasing subsequence?

[@dikshitbatra]

Can you explain the DP( n square) solution by sorting.

[@rajbohra5148]

watch Bo Quian's video titled "Dynamic Programming #1: Longest Increasing Subsequence"

[@MrAbc20101]

Good

[@backflipinspace]

in your current sequence if i just add one more 3, making it {3,1,5,2,6,4,9,3}, this approach will fail! the final 3 would replace 4 and then the sequence would become [1,2,3,9], which is not a valid sequence!

[@sahulrajhansa8363]

Explanation of the algorithm was good but I wish you could have done the in-depth explanation of the code.

[@sumitgupta1457]

Videos are really good. But I think, proof should be included.

[@nipeshsingh1235]

i still dont understand why the increasingSub array has to be of size [X.length+1]. Wont it still work fine if we make it of size [X.length]???

[@IDeserve]

Hi Nipesh, we think if you work through an example, the overall algorithm would be more clear to you. Thank you, Team IDeserve

[@seenu007]

why isn't 3,5,6,9 a longest increasing subsequence?

[@vivaviiv]

Nice nice nice

[@IDeserve]

+Togrul Karimov Thanks a lot for your words! We are striving hard to make understanding algorithms easier. We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like algorithm visualizations, learn together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@xorenpetrosyan2879]

I think you're doing something wrong, because in the example at the end you've got 1,2,4,7,10, but 7 comes AFTER 10

[@mohit4231]

Yes its failing in this case .

[@anands9407]

noice

[@mannykshatriya]

The increasingSub[] will always have the longest increasing subsequence as we are not deleting from it at any point in code, just replacing and appending. So, if i just want a length of the LIS, then i don't need the parent array, right?

[@sravanthipasumarthi4215]

what about 3,5,6,9? it is also a longest increasing subsequence

[@shamimsarker6230]

Multiple Answer is allowed..

[@shamimsarker6230]

also 1,5,6,9 is an answer.

[@nishantsachdeva580]

If I use 7 4 2 1,then I'll end up replacing the first element itself and will get only, 1 as my ans using this algo.

[@sachin3072004]

Thanks for the video. But I think in case of {10,20,30,5,60,70} your algo will fail. your algo will return 5,60,70 as longest subsequence.

[@IDeserve]

+Sachin Gupta Thanks for watching the video. It works for that case and returns {10,20,30,60,70} as ouput. Did you run the code and check? Here is the link:- github.com/IDeserve/learn/blob/master/LongestIncreasingSubsequence.java. Please refer to the Wikipedia article en.wikipedia.org/wiki/Longest_increasing_subsequence if you have any other doubts.

[@sahithrao2163]

I appreciate the video and your useful links. Could you please make a video on how to track the number of longest increasing subsequence? It would be great.

[@SarathVakacharla]

{3,5,6,9} ?

[@IDeserve]

***** yes, {3,5,6,9} is also the LIS in {3,1,5,2,6,4,9}. But the algorithm discussed here does not give you muliple LISs of same length. It will output only one of them. Please have look at the insights section of the video. There I have discussed why would the algorithm go for LIS starting from {1} instead of {3}. It hopes to find a longer sequence by starting at {1}. Please let me know if you have any more questions. Also refer to this wikipedia article en.wikipedia.org/wiki/Longest_increasing_subsequence

[@manishsat]

Back tracking code is wrong. K = increadingSub{lenght} will be 9 and X[9] is out of Index.... happy coding...

[@IDeserve]

Hi Manish, The backtracking code is not really wrong. We have verified at our end that this code works perfectly fine. We would recommend you to use a Java IDE like eclipse for stepping through the code which would help you understand how increasingSub[length] is being modified. Thank you, Team IDeserve