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.
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.
One of the best explanation of this topic i have seen on UA-cam. Keep going man and your way of teaching the concept is too good and also you make it easy to understand...
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.....
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..
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.
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
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.
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.
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
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 .
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.
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.
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; }
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.
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]
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 :)
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 .
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.
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.
Thanks :)
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.
Welcome
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.
Others explained how.....
You explained how + why - That's great
Great explanation! Please upload the o(N*logN) approach.
UA-camrs have made soo much buildup for this problem 😂.....but you killed it man...🔥🔥 Thanks
Thanks
Great to see you also covered the variation of this problem where we need to return the subsequence itself instead of longest subsequence length.
What is the title?
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.
5:30! ❤️ Please explain me NlogN solution. Wanna learn it from you :)
@@techdose4u Let me try to figure it out and I will teach you 🤣🤣
@@yitingg7942 Thanks ❤️ I am waiting for it 😀
@@techdose4u I tried Surya, I just couldn't understand the binary search solution nor the binary search code itself.
Okay. Then I will try to explain you now :)
Thank bro. I was just worried about the length of video. But now it doesn't matter.
👍
Recursion with Memoization time complexity is also O(n^2)
One of the best explanation of this topic i have seen on UA-cam.
Keep going man and your way of teaching the concept is too good and also you make it easy to understand...
Thanks :)
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.....
Also please make more and more videos...
I do take out time on weekend for teaching. That's my hobby :)
Nice Explanation! I think its very difficult to solve this problem in interview with out prior knowledge of this approach.
Explanation is clear as a crystal ⭐⭐
What to say this series is just amazing ❤️
never thought that you would make this problem soooooo ezzzzzyyyyy.....😍😍😍
XD
Thank you sir for creating such great content and helping us building our concepts.
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)
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..
Yep. I will make that from further videos :)
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.
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
nice explanation. Thankx a lot for this.
KEEP IT UP!!.
Welcome :)
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
Welcome. I will try in future as I get time.
@@techdose4u still waiting for this video =]]
Best explanation from basic to very next level. Awesome 👌👌🔥🔥
Thanks :)
1:45 subarray (not substring as we have integers not characters)
There is a binary search approach also which is O(nlogn)
👍🏼
Thanks
Just understood that
Solution to this problem and its limitations using Backtracking approach very well explained and was also very to the point.
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.
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.
How to write logic for it , can u explain?
Amazing Sir..superb Explanation..
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
That's my objective too. I will be covering the most important questions in coming 6 months.
@@techdose4u Thanks.
Your videos are really soo helpful.
@@techdose4u Yes please do that. You are helping the community.
💯 superb explanation
When I paused to think, I solved it differently. I sorted the elements, then applied uncrossed line (LCS). It is giving same answer.
That's a really clear explanation ...Great
Thanks
You are really amazing, the best video for this question
Thanks
You nailed it man!!!🥰
thanks :)
Great what a good explanation and solution
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 .
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.
We can sort the sequence and find lcs of the sorted and original array.. i guess it will also work here...
16:39 for getting the subsequence array
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.
Good idea....but this can only be done from the next month as I am busy with leetcod this month.
@@techdose4u okay bro
@@techdose4u Bro if I just practice the most popular 30-40 questions of each topic , will it be enough to crack interviews?
Yes.... That should be enough.... Provided you keep practicing and keep learning
@@techdose4u ok bro
very beautifully explained..the hardest concept
Thanks :)
Please also cover the O(nlogn) TC approach
👍🏼
Wow !! Really Awesome Dude.
Thanks
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;
}
updating of the LIS should be a max of the new value and the current value for example, using Java: LIS[i] = Math.max(LIS[i], LIS[j] + 1);
Can you cover the solution with n(log n) complexity?
Yea why not
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.
Yea right
Thank you Surya, was finally able to understand this.
Great 😀
Amazing Explanation!
Nice job @TECH DOSE
Ur vedioes are just awesome
Thanks
really nice video. but can you please upload a video for time complexity nlogn?
Yea sure :) Will take your advice in consideration as well.
Can you please make a video on this problem with binary search and dp and O(nlogn) complexity with c++ code? Thank you :)
I will make it later. Currently doing heap.
Nice explanation!
Could the condition be more restrictive?
Sth like: arr[i] > arr[j] && lis[i] == lis[j]
would have been great if you deduced this from the memoized solution of LIS
from 14:00 to 14:20 is the main part
sir, do you have any frequently asked interview questions list??
the longest increasing subsequence can also be 5,8,7,9
@@harshyadav5162 sorry I posted it when I hadn't learned abt it
@@Pooh__7__peace ✌️
Not very efficient algorithm. Its O(n^2).....can be done in nlogn. But still nice explanation 👍.
👌🏼
@@techdose4u can you please make a video on nlogn solution also?
I will make it later. I am trying to cover the topics which are left.
Just we need to search from 0 to i using binary search
Please also upload video on binary search approach
This can be done n*logn time with binary search. that's better with time complexity and easy to understand.
Great 💯💯💯🙌🙌
Thanks :)
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]
can we reduce the time complexity to O(nlogn)?
Yes it's possible.
@@techdose4u can you make a video on that approach?
@@techdose4usir, please make a video
@@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 :)
there is no explanation for this algorithm in the description
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.
Atleast try to understand from solutions or editorial. As long as you do it, you will be able to solve soon.
Thanks! I understand !
is it bad if i m not able to think for the algo myself ?
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 :)
@@techdose4u thanks a lot and continue your work becoz i know your views are going to rise exponentially they are too good!!
Great Job!!!!Make More videos on DP.
Yea sure :)
great video.
Solution required with nLogn time complexity
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 .
Thanks surya 😃😃
Welcome
what is the time complexity of that code ? is it o(nlog(n))?
Should be N2.
great explanation sir!
Thanks for your motivation :)
could you please do even 673. Number of Longest Increasing Subsequence problem ?
I will try once I do DP.
Why can't we move from left to right to find the sub-sequence?
pls do a video exclusive for basic code of backtracking
I will do it in recursion series when I start it.
The problem is I want to find greatest sum. So i must get and compare both the longest subsequence .
great video.....
Thanks :)
is there any video of you eplaining lis in recursive manner though it is not optimal but recursion is important to do dp??
can someone please explain that LIS comes under overlapping subproblems or optimal substructure?
good explanation
Thanks :)
Sir can share the algorithm pls
can you make a video on increasing decreasing and then increasing subsequence . fir e.x = a subsequence like ( 5 , 4, 19 )
What will you do in element are repeated?
We don't include Repeating elements in LIS.
Why u use two for loops
it should be done in nlogn time complexity
Thanks again.....
7:50 why lis[i]
o
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.
Which graphic tablet u r using to make this video ?
Huion 1060 plus
why should we check lis[ i ]
Thank you sir
Welcome
Dhanyawad
Shukriya :)
its not giving correct output for printing lis
You should have explained the second part of the if condition, just saying think about it doesnt equate to teaching.
Aree sir phele backtarcking krana tha tabhi smj ata
thanks bro
Can anyone help me to store both the longest subsequences.
if the array is 5 10 7 8 9 11 12 the LIS is 6 but the algorithm will give output of 4...the logic is not correct...