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

Longest Increasing Subsequence Algorithm is explained with examples and visualizations.

[kingshukjana]

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

[piyush]

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

[saijayavinothtvs]

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

[shanmukhchandrayama]

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.

[sarwarjahan]

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

[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!


Thanks,
-Team IDeserve.

[ankitiiita]

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

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

[sulekhakumari-hsgy]

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

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

[shivamgarg]

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.

[izzyzhao]

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.

[vidhishah]

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 ?

[mahadeiv]

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 ?

[anish]

Consider the following example {8, 3, 4, 2, 5, 6}. As per the algorithm when we pick up 2 we have to replace 3<-4 with 2. So the output it gives is 2<-5<6. But LIS is 3, 4, 5, 6. Am I doing anything wrong?

[oceanbhardwaj]

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

[ぶらえんぴん]

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?

[vinayaksangar]

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<-2<-57<-58<-100 ryt?
Now in case 1
when arr1[] = {1, 2, 57, 58, 100, 4, 101}
At i = 5 we search for position of 4 in LIS 1<-2<-57<-58<-100 using binary search which came out to be after 2 forming new LIS to be 1<-2<-4 .So after that when we will take 101 .The final LIS would be 1<-2<-4 <- 101 but the longest LIS is 1<-2<-57<-58<-100<-101
Now in case 2
when arr1[] = {1, 2, 57, 58, 100, 4, 5, 7, 8, 9}
At i = 5 we search for position of 4 in LIS
1<-2<-57<-58<-100 using binary search which came out to be
after 2 forming new LIS to be 1<-2<-4 .So after that when we will
take 5 .The final LIS would be 1<-2<-4 <- 5 resulting to
1<-2<-4 <- 5 <-7<8<-9 which infact is the longest
I am confused how these two cases are managed in your code

[priyamraj]

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