I have never seen such an amazing explanation of Lis in nlogn. Other YT videos just explain that you have to make an array and make an upper bound and replace, and the size of the vector will be lis. But the thinking behind it, that it will (Len,last) is something that I can remember and even if I don't remember the algo, just this idea of (Len,last) will be enough to write entire code. Thanks a lot Vivek.
i feel good someone actually teaching , not spoon feeding , not teaching as it a trick and we need to mug that up. Every other even big channel teaching tricks to solve qn. thank for high quality education .
Thanks for the great explanation, I earlier read several blogs regarding printing in O(NlogN), but none of them I was able to understand completely. You made it looked so simple. Thanks a lot.
Also we can observe that when we print the partial solution, the first solution for a particular length is the actual lis of the length. We can see 1, 5, 6, 7, 9 printed in the partial solutions also thats the first time 9 was inserted and after that we were not able to increase the lis, so the sequence in which 9 was inserted at the end is the lis.
I think it is wrong.Consider a 10 at the last element of the example which Vivek took. Clearly first partial solution of length 6 is 1 2 3 7 9 10 which is not actual LIS
Sir the backpointers you keep mentioning any hope that we will get to see what that actually is ? Thanks a lot for this wonderful lecture!!! Always a blessing to watch your lectures
@@charlesdingus9662 this is already that one u r talking about , as we are traversing from back and picking the last element at that length , it's already the smallest updated one ...7
my idea for bitonic is that we keep 2 vector which holds the BEST LIS at each index and the other vector holds the best LDS at each index and we will sum the corresponding indexes together but decrease 1 to not over count. maybe we don't need function LDS we can use the same LIS but we need to reverse it and we need to keep track of each element original index which is (N - new_index_after_reverse) Is this right ? I did try it and it seems correct
I think there's still a caveat, suppose best possible length till index x = 6, and its ending element is 7, and the best possible length of LDS till x is 8 but it last ending eleemnt is 8, in that case we simply add the lengths,we only do -1,if both of them have same last ending element.
Thanks for the explanation, I own figured out another way to print LIS from the observation in this video. What I did, I stored the first vector formed with x length and returned the vector corresponding to vec.size() after the iteration using map. I know the space is much higher than the explanation in the video but still it's another way to print LIS. 🙂🙂
Help!! Finding the longest bitonic sequence in n^2 complexity is easy we can do dp1[i] + dp2[i] - 1, where dp1 is LIS and dp2 is the longest decreasing subsequence. I cannot understand how to achieve this in O(nlogn) complexity. Do we have to increase the number of states in order to achieve this? Thanks in advance
@@vivekgupta3484 The insertedAt array although stores the size at which every element was inserted but also stores the best possible answer for every index i, which is basically the same as dp. Is this correct?
I print the LIS using the upper_bound, it is giving the right answer but please check whether it is valid here lastIndex is the index in arr of last element in the lis vector(here last element is 9, so lastIndex is 7) for(int i=lastIndex;i>=0;i--){ if(finalLIS.empty() || finalLIS.back()>arr[i]){ finalLIS.push_back(arr[i]); } else{ auto it=upper_bound(finalLIS.begin(), finalLIS.end(),arr[i]); } } reverse(finalLIS.begin(),finalLIS.end());
I have never seen such an amazing explanation of Lis in nlogn.
Other YT videos just explain that you have to make an array and make an upper bound and replace, and the size of the vector will be lis.
But the thinking behind it, that it will (Len,last) is something that I can remember and even if I don't remember the algo, just this idea of (Len,last) will be enough to write entire code.
Thanks a lot Vivek.
True
The world need educators like you
i feel good someone actually teaching , not spoon feeding , not teaching as it a trick and we need to mug that up. Every other even big channel teaching tricks to solve qn. thank for high quality education .
This is such a great explanation for such a complex thing, you are doing a great job man, please keep helping us!
First time completely understood lis in nlogn! Although randomly opened the video, planning to watch all the DP
Thanks for the great explanation, I earlier read several blogs regarding printing in O(NlogN), but none of them I was able to understand completely. You made it looked so simple.
Thanks a lot.
never seen printing lis in nlogn. such a unique idea. thank you vivek bhaiya.
the best explanation for LIS over the whole internet
The best DSA /CP teacher , period.
No words to describe! Just thank you very much.
Wao 🔥
It is an amazing explanation for printing LIS in NlogN.
What is form of optimised one? Not looking like Form 2 na
its form 2 only … but the saved value is different… its lowest value ending with length x.
Also we can observe that when we print the partial solution, the first solution for a particular length is the actual lis of the length. We can see 1, 5, 6, 7, 9 printed in the partial solutions also thats the first time 9 was inserted and after that we were not able to increase the lis, so the sequence in which 9 was inserted at the end is the lis.
I think it is wrong.Consider a 10 at the last element of the example which Vivek took. Clearly first partial solution of length 6 is 1 2 3 7 9 10 which is not actual LIS
Thank you for the way you have explained the solution..
Beautiful idea and beautiful explanation too... 🔥🔥🔥
Really good explanation
Thank you!! Very helful
A stressed day today. But finally watched it.
At 13:30, I think for length 4 the best will be ending at 8 instead of 9 because last is smaller in case of 8 (1,5,7,8)
Till that time we have not seen the 8... and its the older 9.
Simple is hard--Martin scorcese...outstanding explanation
Sir the backpointers you keep mentioning any hope that we will get to see what that actually is ? Thanks a lot for this wonderful lecture!!! Always a blessing to watch your lectures
🛐
🔥🔥
wow great algorithm 🙂
Like this..also make a workshop on graph and trees..as there are very less quality content available regarding it.
Tanks for amazing explanation. When you are going to upload day-6 videos. Waiting for it .
sir if we get configuration like this in insertedat array - 1 2 3 4 3 5, then we also we will have same answer with just different elements, isn't it?
cool :)
👑 orz
what if we have to print the lexicographically smallest LIS
Hi Vivek, can the lexographically smallest LIS be printed in O(NlogN)?
Yes. Thats another beautiful problem in itself.
@@vivekgupta3484 can you give a little hint on how to approach it.
@@charlesdingus9662 this is already that one u r talking about , as we are traversing from back and picking the last element at that length , it's already the smallest updated one ...7
my idea for bitonic is that we keep 2 vector which holds the BEST LIS at each index and the other vector holds the best LDS at each index and we will sum the corresponding indexes together but decrease 1 to not over count. maybe we don't need function LDS we can use the same LIS but we need to reverse it and we need to keep track of each element original index which is (N - new_index_after_reverse) Is this right ? I did try it and it seems correct
Yup thats correct.
I think there's still a caveat, suppose best possible length till index x = 6, and its ending element is 7, and the best possible length of LDS till x is 8 but it last ending eleemnt is 8, in that case we simply add the lengths,we only do -1,if both of them have same last ending element.
@@dank7044lis we are keeping from beginning and lds from last and also they are ending at same position so how can their values be different?
🔥🔥🔥🔥🎇🎇❤️
Have anyone taken yesterday doubt session
It is not in videos of this channel
He didnt took that yesterday. Maybe something imp. came up.
@@priyanshsinghal9977 Thanks for the clarification Brother.
@@priyanshsinghal9977 Not in my best health.. Will try to take it today.
@@vivekgupta3484 Take care. I wish you a healthy life.
Thanks for the explanation, I own figured out another way to print LIS from the observation in this video.
What I did, I stored the first vector formed with x length and returned the vector corresponding to vec.size() after the iteration using map.
I know the space is much higher than the explanation in the video but still it's another way to print LIS.
🙂🙂
can you please do it in java too?
i think most of the code portions are same.
@@vivekgupta3484that lower_bound i cant see in java
Can you please solve the Maximum Square Matrix (Day3 Question 3) using recursion and memoisation
Insertion sort 😮
Help!!
Finding the longest bitonic sequence in n^2 complexity is easy we can do dp1[i] + dp2[i] - 1, where dp1 is LIS and dp2 is the longest decreasing subsequence. I cannot understand how to achieve this in O(nlogn) complexity. Do we have to increase the number of states in order to achieve this? Thanks in advance
calculate dp1 and dp2 in nlogn maybe?
@@vivekgupta3484 The insertedAt array although stores the size at which every element was inserted but also stores the best possible answer for every index i, which is basically the same as dp. Is this correct?
@@sanketpoojari6057 the index where ith element gets inserted is dp[i].
@@vivekgupta3484 Thanks, that was very helpful. Btw, this series is very good❤
attendance ++
I print the LIS using the upper_bound, it is giving the right answer but please check whether it is valid
here lastIndex is the index in arr of last element in the lis vector(here last element is 9, so lastIndex is 7)
for(int i=lastIndex;i>=0;i--){
if(finalLIS.empty() || finalLIS.back()>arr[i]){
finalLIS.push_back(arr[i]);
}
else{
auto it=upper_bound(finalLIS.begin(), finalLIS.end(),arr[i]);
}
}
reverse(finalLIS.begin(),finalLIS.end());
*it = arr[i] ??
+1
Watch twice if u don't get at once...
🤔🥴😵💫Printing part is hard to get
True... try to take a input and run the idea on it.
@@vivekgupta3484 Yes will do that, thanks for your efforts 👍
Great!!!