Longest increasing subsequence

This video explains how to find both the longest increasing subsequence length along with the subsequence itself. This is the simplest explanation along with logic. This is a very frequently asked programming interview question. The code for reference is present in the description section below, so please check it out. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: drive.google.com/open?id=1Oks...

[@mrinalraj7166]

You must be very proud of yourself for creating such great contents. Thanks. You are a big help. Keep up the good work. Our community needs you.

[@techdose4u]

Thanks :)

[@amanrai8010]

You are very interactive with us despite having a good number of views you make sure to clear each and everyone's doubt. Thank you.

[@techdose4u]

Welcome

[@dev-skills]

Great to see you also covered the variation of this problem where we need to return the subsequence itself instead of longest subsequence length.

[@rishabhshukla5199]

What to say this series is just amazing ❤️

[@jaswantrohila3776]

CZcamsrs have made soo much buildup for this problem 😂.....but you killed it man...🔥🔥 Thanks

[@techdose4u]

Thanks

[@fanigo138]

Great explanation! Please upload the o(N*logN) approach.

[@prodiptamondal1758]

Recursion with Memoization time complexity is also O(n^2)

[@sandeeprajurs1994]

Nice Explanation! I think its very difficult to solve this problem in interview with out prior knowledge of this approach.

[@dev-skills]

Solution to this problem and its limitations using Backtracking approach very well explained and was also very to the point.

[@samlinus836]

Others explained how.....
You explained how + why - That's great

[@amandarash135]

Thank bro. I was just worried about the length of video. But now it doesn't matter.

[@techdose4u]

👍

[@gouthamreddy5713]

is there any video of you eplaining lis in recursive manner though it is not optimal but recursion is important to do dp??

[@rishabhkumar8115]

nice explanation. Thankx a lot for this.
KEEP IT UP!!.

[@techdose4u]

Welcome :)

[@RomanUnreal]

Thanks! I understand !

[@karansagar7870]

how does dp improve solution we can iterate from right to left use stack and push in stack if num is less than top of stack store size of stack in max ,run loop each time 1 less than previous to 0 .

[@creatorstudio5945]

Thank you sir for creating such great content and helping us building our concepts.

[@Sweety-rx8zq]

can someone please explain that LIS comes under overlapping subproblems or optimal substructure?

[@ranjanreddy623]

Explanation is clear as a crystal ⭐⭐

[@vijayakumareyunni6010]

at 7:16, "If you think about it, you will get it yourself". Instead of calling out names of variables, arrays and reading out every number in the array, time should be spent wisely to explain the "intuition" behind the logic - That's more important than syntax.

[@PankajKumar-ft7lc]

second part(finding the sub sequence) is wrong.
what if the arr is [99,100,1,2,101,3]
then lis array will be [1,2,1,2,3,3]
now according to you LIS should be 1,2,3 or 99,2,3 or 99,100,3 or 1,2,101 or 99,2,101 or 99,100,101.
and many of these are wrong.
Please correct me if I am wrong or I miss understood anything.

[@techdose4u]

Well, the thing which i did not tell is, you will keep comparing corresponding values in your original array before making a concrete decision of choosing a lower value as a LIS subsequence. If you don't compare corresponding elements in original array then there is no way to know the correct answer. Thanks for highlighting this imp point.

[@anantjain1263]

How to write logic for it , can u explain?

[@Shakib.Siddiqui]

Great what a good explanation and solution

[@AhamedKabeer-wn1jb]

Amazing Sir..superb Explanation..

[@meghanachandrayama3103]

Hey can u please explain the method for calculating the subsequence itself more precise in a more general way. I guess we should start from the index max value of LIS array and traverse back for finding the index with 1less than the max value and along with that we even have to ensure that arr[i]

[@yitingg7942]

I got up at 5:30 to watch your videos lol... I love it, you explained it so well, I don't think I will ever forget about this solution. I didn't get it out myself cause I was stuck trying to get it in constant time and then I couldn't. Some DP can be done using linear some has to use N^2. So sometimes I got stuck not knowing how to think of the best solution. There's a follow up question to prove it to O(n log(n)) time as well. ehhh, binary search again.

[@techdose4u]

5:30! ❤️ Please explain me NlogN solution. Wanna learn it from you :)

[@yitingg7942]

@@techdose4u Let me try to figure it out and I will teach you 🤣🤣

[@techdose4u]

@@yitingg7942 Thanks ❤️ I am waiting for it 😀

[@yitingg7942]

@@techdose4u I tried Surya, I just couldn't understand the binary search solution nor the binary search code itself.

[@techdose4u]

Okay. Then I will try to explain you now :)

[@oreoshake5951]

For the variation. If we have array as 10, 5, 11, 6, 9
Here the lis array would look like: 1, 1, 2, 2, 3
But when we trace back for string of longest increasing subsequence then as said the array would go by taking 9 , then we could either take up 6 or 11, but taking 11 would be wrong subsequence.
I dont know if I am missing something. Though thanks for the explanation.

[@karthiknayak828]

We can probably add a condition where arr[i] < top of the stack if we are storing the values of the subsequence in the stack. Hope this helps

[@kavinraj1543]

That's a really clear explanation ...Great

[@techdose4u]

Thanks

[@spetsnaz_2]

never thought that you would make this problem soooooo ezzzzzyyyyy.....😍😍😍

[@techdose4u]

XD

[@sonal9kothari]

I came across a question, which I feel is similar to LIS. Problem statement : find the longest subsequence, such that the XOR of adjacent elements in the subsequence is equal to a given ‘k’ value. Please throw some light on this problem statement.

[@9-1939]

💯 superb explanation

[@prakharagarwal6237]

Amazing Explanation!

[@reallydarkmatter]

You are really amazing, the best video for this question

[@techdose4u]

Thanks

[@mandeep2192]

very beautifully explained..the hardest concept

[@techdose4u]

Thanks :)

[@ris_colid325]

Nice explanation. Can you please make an explanation video for the optimal method using DP with binary search as well? It has n Log n time complexity. Also ,came across another problem asking us to find number of longest increasing subsequences. If you could explain on that ,it will be a great help as well .

[@testbot6899]

class Solution:
def lis(self, A):
res = [A[0]]
n = len(A)

for num in A[1:]:
if num>res[-1]:
res.append(num)
else:
res[bisect_left(res,num)] = num
return len(res)

[@techamet428]

really good explanation..but it would be more helpful if you also start with recursive approach and slowly convert it into a dp..if video length if the problem you can make it in parts..it would be more helpful for beginners like me to solve dp problems.... Overall a very good explanation..

[@techdose4u]

Yep. I will make that from further videos :)

[@ANKURSingh-yl2lj]

can u make a video for this problem in O(nlogn) complexity by using dp+binarysearch by the way ur explanation is brilliant ur voice quality and picture quality is great thanx fr this type of help

[@techdose4u]

Welcome. I will try in future as I get time.

[@275phuongvy]

@@techdose4u still waiting for this video =]]

[@ganeshkamath89]

When I paused to think, I solved it differently. I sorted the elements, then applied uncrossed line (LCS). It is giving same answer.

[@hitengoyal5457]

There is a binary search approach also which is O(nlogn)

[@techdose4u]

👍🏼

[@Live-hh6li]

Thanks
Just understood that

[@ajaywadhwa3398]

Wow !! Really Awesome Dude.

[@techdose4u]

Thanks

[@dhanashreegodase4445]

Thanks again.....

[@AmanKumar-ht8xi]

please make videos on some of the questions of "must do interview preparation" from geeksforgeeks.. because it has quality questions and solution is not available on youtube.. by the way your explanation is just awesome.. thank you for the videos

[@techdose4u]

That's my objective too. I will be covering the most important questions in coming 6 months.

[@divasbhadani9225]

@@techdose4u Thanks.
Your videos are really soo helpful.

[@mrinalraj7166]

@@techdose4u Yes please do that. You are helping the community.

[@jvmilgrau5793]

Nice job @TECH DOSE

[@salmaharb4588]

great video.

[@pawanlok1776]

thank you ...

[@MohitKumar-ub2td]

One of the best explanation of this topic i have seen on CZcams.
Keep going man and your way of teaching the concept is too good and also you make it easy to understand...

[@techdose4u]

Thanks :)

[@MohitKumar-ub2td]

You deserve it, honestly speaking i merely write anything but when someone makes such content then i can't stop myself because my inner soul says that this man has putting lots of hard work for making such content and futher it helps a lots of students.....

[@MohitKumar-ub2td]

Also please make more and more videos...

[@techdose4u]

I do take out time on weekend for teaching. That's my hobby :)

[@bharatiyadharohar]

Best explanation from basic to very next level. Awesome 👌👌🔥🔥

[@techdose4u]

Thanks :)

[@kishanmishra9802]

Nice explanation

[@renon3359]

Thank you Surya, was finally able to understand this.

[@techdose4u]

Great 😀

[@aradhayaarora6155]

Can you please make a video on this problem with binary search and dp and O(nlogn) complexity with c++ code? Thank you :)

[@techdose4u]

I will make it later. Currently doing heap.

[@sunneykumar4560]

what is the time complexity of that code ? is it o(nlog(n))?

[@techdose4u]

Should be N2.

[@JangBahadur3028]

code of Above logic : LEETCODE 300
public static int lengthOfLIS(int[] nums) {
int[] lis = new int[nums.length];
// each element itself is an increasing sub sequence
for (int i = 0; i < lis.length; i++) {
lis[i] = 1;
}
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j nums[j] && lis[i] max) {
max = Math.max(max, lis[i]);
}
}
return max;
}

[@ServingTech]

We can sort the sequence and find lcs of the sorted and original array.. i guess it will also work here...

[@barathkumar7940]

Why can't we move from left to right to find the sub-sequence?

[@dev-skills]

1:45 subarray (not substring as we have integers not characters)

[@astitvasrivastav9484]

is it bad if i m not able to think for the algo myself ?

[@techdose4u]

I was not able to do it myself. People can't do without having any practice. You will need to practice. Practice more and your intuition for it will increase. It works with everyone. Someone catches faster and someone late, but the point is, everyone catches. So try harder :)

[@astitvasrivastav9484]

@@techdose4u thanks a lot and continue your work becoz i know your views are going to rise exponentially they are too good!!

[@piyushigarg8688]

can you make a video on increasing decreasing and then increasing subsequence . fir e.x = a subsequence like ( 5 , 4, 19 )

[@prateeksrivastava9]

Great Job!!!!Make More videos on DP.

[@techdose4u]

Yea sure :)

[@santasingh9045]

great explanation sir!

[@techdose4u]

Thanks for your motivation :)

[@rajeshpanwar6796]

thanks bro

[@b.sainathreddy4567]

Ur vedioes are just awesome

[@techdose4u]

Thanks

[@rohandevaki4349]

sir, do you have any frequently asked interview questions list??

[@nabidulalam6956]

clearly explained. thanks.
btw one suggestion, if you could explain the memoization technique after the recursion it would be great lesson.
recursion -> recursion + memoization -> DP -> DP(nlogn version) in that order would be a great help for the learners to catch the intuition behind every way to solve the problem.

[@techdose4u]

Yea right

[@ganganagarimahender3187]

Why u use two for loops

[@1989ashok]

Which graphic tablet u r using to make this video ?

[@techdose4u]

Huion 1060 plus

[@willturner3440]

Please also upload video on binary search approach

[@AnjaliKumari-zm9zo]

really nice video. but can you please upload a video for time complexity nlogn?

[@techdose4u]

Yea sure :) Will take your advice in consideration as well.

[@pranjalgupta9427]

Thanks surya 😃😃

[@techdose4u]

Welcome

[@devendunegi247]

would have been great if you deduced this from the memoized solution of LIS

[@srinivasgangaraju2998]

16:39 for getting the subsequence array

[@288Somaanil]

Can you cover the solution with n(log n) complexity?

[@techdose4u]

Yea why not

[@akshatjain6854]

Bro you are superb. Apart from uploading coding videos. Please try to make videos on general topics while preparing for interviews like how to dry run the code effectively etc.

[@techdose4u]

Good idea....but this can only be done from the next month as I am busy with leetcod this month.

[@akshatjain6854]

@@techdose4u okay bro

[@akshatjain6854]

@@techdose4u Bro if I just practice the most popular 30-40 questions of each topic , will it be enough to crack interviews?

[@techdose4u]

Yes.... That should be enough.... Provided you keep practicing and keep learning

[@akshatjain6854]

@@techdose4u ok bro

[@PritamKumar-mr5dv]

great video.....

[@techdose4u]

Thanks :)

[@rohandevaki4349]

there is no explanation for this algorithm in the description

[@adityadhikle9473]

Great 💯💯💯🙌🙌

[@techdose4u]

Thanks :)

[@parasjain9416]

Dhanyawad

[@techdose4u]

Shukriya :)

[@ayushupadhyaya7656]

Please also cover the O(nlogn) TC approach

[@techdose4u]

👍🏼

[@amarjeetyadav26436]

its not giving correct output for printing lis

[@istvanszabo6875]

Nice explanation!
Could the condition be more restrictive?
Sth like: arr[i] > arr[j] && lis[i] == lis[j]

[@shreyyy_marwaha]

Not very efficient algorithm. Its O(n^2).....can be done in nlogn. But still nice explanation 👍.

[@techdose4u]

👌🏼

[@shreyyy_marwaha]

@@techdose4u can you please make a video on nlogn solution also?

[@techdose4u]

I will make it later. I am trying to cover the topics which are left.

[@devendradahale546]

Just we need to search from 0 to i using binary search

[@komalbhatia8986]

Thank you sir

[@techdose4u]

Welcome

[@gautamgoel2024]

This can be done n*logn time with binary search. that's better with time complexity and easy to understand.

[@jitendarsahani11]

What will you do in element are repeated?

[@techdose4u]

We don't include Repeating elements in LIS.

[@souravdebnath7732]

Sir can share the algorithm pls

[@kpclasses7985]

good explanation

[@techdose4u]

Thanks :)

[@samgedam0]

Can anyone help me to store both the longest subsequences.

[@anonymous-sk2pr]

❤️❤️❤️

[@techdose4u]

❤️

[@mohsinkhan845]

nice explanation

[@techdose4u]

Thanks :)

[@anuragalvala2113]

can we reduce the time complexity to O(nlogn)?

[@techdose4u]

Yes it's possible.

[@anuragalvala2113]

@@techdose4u can you make a video on that approach?

[@vaibhavkumar9192]

@@techdose4usir, please make a video

[@techdose4u]

@@vaibhavkumar9192 I don't really know if people will get it :P But I will try it after completing the basic DSA series for placement :)

[@uditkumar867]

I am so weak in DP .. I attempted 15 questions and never able to think the DP approach by myself always have to look at the solution.

[@techdose4u]

Atleast try to understand from solutions or editorial. As long as you do it, you will be able to solve soon.

[@eastwoodsamuel4]

Solution required with nLogn time complexity

[@SaurabhSuman-wz1ex]

it should be done in nlogn time complexity

[@shivomkumar628]

what do you mean by you will figure it out ? the main condition that need explaining you said you will figure it out. seems like you are just copying the code and saying it will work.

[@hemanthram4369]

pls do a video exclusive for basic code of backtracking

[@techdose4u]

I will do it in recursion series when I start it.

[@rakshith3547]

could you please do even 673. Number of Longest Increasing Subsequence problem ?

[@techdose4u]

I will try once I do DP.

[@samgedam0]

The problem is I want to find greatest sum. So i must get and compare both the longest subsequence .

[@sanjeevayyagari7060]

why should we check lis[ i ]

[@Pooh__7__]

the longest increasing subsequence can also be 5,8,7,9

[@Pooh__7__]

@@harshyadav5162 sorry I posted it when I hadn't learned abt it

[@harshyadav5162]

@@Pooh__7__peace ✌️

[@amizhthanmadan4647]

You should have explained the second part of the if condition, just saying think about it doesnt equate to teaching.

[@Relaxingmusic-tw4qn]

bro your videos are quite awesome you can even charge minimum for its access by making it more orderly,, its pains me to see how shit like white hat jr are charging so much money for the same level contend. education should be free and open to every1

[@techdose4u]

😅

[@abhinavghosh725]

from 14:00 to 14:20 is the main part