Will never forget my first day on the job where a customer requested a feature to find the longest increasing sub-sequence. A totally valid way to test someones competency as a developer
It is important to understand the idea of subsequences, use memory efficiently and understand complexities of exponentially increasing subroutines. A good Programmer is not the one who solves it the first time seeing it. A good Programmer is the one who understands all the dimensions of the problem and Learn as much as he can about underlying intuitions. and remember when Tony Hoare first made Quick Sort He didn't say I am not going to face a situation where I sort a customer's Needs. His attitude as any computer scientist when making a helpful research or an idea was If I am able to think How to sort and even invent a sorting algorithm then I am going to be able to satisfy my Customer needs who were Future Generations that used Quick sort in every Customer related Situation . Good bye.
Please keep that tone and speed of voice. It really helps to "understand" the solution. All of us are here to "understand" the solution not just for a solution. You will do great my dude.
You can change the playback speed on TH-cam to make it go faster or slower. In case you find a problem that some other youtuber has solved, that Neetcode hasnt solved yet, use that feature.
"I really doubt your interviewer is going to expect you to get this without a hint; if they do I'd just walk out of the room" Probably worked great up until the layoffs 😥
You're the best at actually explaining the reasoning behind these problems and all your views are so well deserved. I'm absolutely dreadful at these despite being a senior dev but you don't know how much your channel has helped, thank you!!!
This explanation went down so smooth -your voice was very easy to follow and your diagrams weren't sloppy and not complex to understand -this might be the cleanest solution I have seen for this problem for beginners to study!
Thank you for the clear explanation! For those wondering why going backwards in dynamic programming, you can actually solve this in forward dynamic programming, start from the beginning, too.
That was so simple and an epic explanation of how you can start thinking about approaching this problem. Being a beginner at dp, your videos help me understand how to start approaching a problem :) Thankyou!
Superb Explanation.Anyone having doubt in leetcode can refer this channel.Excellent video bro.I was struggling for this problem you made it clear.Thank you.
Thanks for such a great explanation, I searched for it so many places, but I didn't find anything more than the formula. This video should have more likes.
Yeah, I agree that being expected to find the O(nlogn) solution is walkout tier. I came damn close to figuring it out: use an ordered set to keep track of the elements you've inserted so far so that you can easily find the greatest value that's smaller than or equal to your current one. From here, assuming nums[i] is not your maximum thus far, there are two ways, and figuring out either of them is easily upper Hard level: either you actually delete the value you've found (the fact that this works because it means you can just return the size of your set at the end is incredibly unintuitive), or you mess with the way you store everything in the set so that you can still retrieve the index of the value corresponding to your found value (which is awful to implement).
Why would deleting the value you found work? If you have input array [2,3,1,5,6] you cannot delete the value found at 5 when you see the 1, because then you cannot use it for the actual longest subsequence of 2,3,5,6 Tbh the approach of using a heap to store the subsequence length cache is quite reasonable imo… it’s annoying to implement but quite straightforward as an obvious improvement. If you know how to solve heap problems, which are based on the premise that a heap is a priority queue, why not just apply that here when you are searching for the largest element?
@@SunsetofMana Not sure a heap would work, you mean for when you check the max right? You still have to know if nums[i] is less than the value, it's not enough to find the largest subsequence. In that case, it's still O(n^2).
Not sure why, but this one felt much easier than the prior 3-4 problems in the Neetcode Dynamic Programming learning path. Got it on my first try, and solved it exactly the way Neet did. Just goes to show the value of the Neetcode Roadmap, and how the patterns start to solidify in your mind over time.
Thanks for the explanation @neetcode , code in java : class Solution { public int lengthOfLIS(int[] nums) { int dp[] = new int[nums.length]; Arrays.fill(dp, 1); for (int i = nums.length - 1; i >= 0; i--) { for (int j = i-1; j >=0; j--) { if (nums[i] > nums[j]) { dp[j] = Math.max(dp[j], 1 + dp[i]); } } } int maxLIS = 0; for (int i = 0; i < nums.length; i++) { maxLIS = Math.max(maxLIS, dp[i]); }
"I really doubt your interviewer is gonna expect you to get the O(n logn) solution without a hint. If they do, I would personally just walk out of the room." XDDDDD
noticing the subproblem 'is there an increasing subsequence with length m' is O(n), and m is between 1 and n, we can use binary search and get overall complexity O(nlogn). But it is way neater with DP
Great demostration starting from brute force, work way up to memoization and then leads naturally to dp!!! So Nice and easy it becomes with your approach! 1 question though: Why work from end backwords? How did you get the instinct?Could you please share your thougghts?
I'm used to working from the end backwards because it's similar to the recursive approach. But it's possible and maybe more intuitive to start at the beginning. Whatever makes sense for you is the best approach I think.
Example: [1,4,2,3], While computing longest common subsequence starting from index 0, the number at index 2, will be used. While computing longest common subsequence starting from index 1, the number at index 2 will be used. What i mean by "Will be used" is i am asking a question: What is the longest common subsequence starting from index 2. So if we had started computing longest common subsquence from backwards, then when we compute longest common subsquence for index 0 and 1, we already have the answer for longest common subsequence starting from index 2 stored.
No need to complicate it further by doing reverse looping, from 0 to n works just fine with the same function of max(lis[i], 1+lis[j]) for i=0 to n, j=0 to i if nums[j]
When i feel its so hard to learn DSA problem and crack FAANG like companies my mind tells me "neetcode" and after seeing the video explanation i become calm and motivated to proceed further.
Optimal Approach O(nlogn) bisect_left is a python function which gives the lower bound of the element in O(logn) time. bisect_left(array, element, start, end) class Solution: def lengthOfLIS(self, arr: List[int]) -> int: subs = [arr[0]] for i in range(1,len(arr)): if arr[i] > subs[-1]: subs.append(arr[i]) else: subs[bisect_left(subs, arr[i], 0, len(subs))] = arr[i] return len(subs)
@@davidespinosa1910 Yeah, the problem asks for the longest increasing subsequence. So, this will still give you the correct length just not the subsequence itself
11:34 I think using the name LIS[ ] is not a good choice, as you may think the final solution is LIS[0] this way. The strict definition of this lookup table, let's call it lookup[ ] is this: IF YOU TAKE THAT NUMBER nums[i] into the sequence, then what is the longest you can get. So lookup[i] IS IF YOU MUST INCLUDE nums[i] into that sequence. If you write LIS[i], it sounds like it is the max NO MATTER you include nums[i] or not, which is not the case. So that's why in the code that follows, the final result is not LIS[0], but max(LIS)
Great explanation as usual!! A repost(?) of the O(nlong(n)) solution, not that hard and really comes in handy for other problems :) class Solution: def lengthOfLIS(self, nums: List[int]) -> int: indices = [None for _ in range(len(nums)+1)] # Mapping of size to the last indice of the subsequence size = 0 def binary(elem, l, r): # a binary search is possible since the sizes are sorted by definition, even if the values in nums are not while l
Great video, much appreciated. However, I didn't understand the logical jump at @10:40 that suggested we were "starting at 3". I would have preferred to see a solution that proceeded front-to-back, because it seemed to me that is what you were doing in the recursive solution.
leetcode editorial suggests improving time complexity with binary search class Solution: def lengthOfLIS(self, nums: List[int]) -> int: sub = [] for num in nums: i = bisect_left(sub, num) # If num is greater than any element in sub if i == len(sub): sub.append(num) # Otherwise, replace the first element in sub greater than or equal to num else: sub[i] = num return len(sub)
You are solving problems like God would solve, I attempted it and couldn't solve it in my first attempt though I knew what Dynamic programming is. Also, the way you explain choices and recursion is far the best way to start attacking problems like this.
since we have already assigned LIS with value 1 for the length of nums, in the first for loop, we can start from len(nums) - 2 instead of len(nums) -1.
def dfs(i): if i in cache: return cache[i] n = nums[i] result = 1 for j in range(i + 1, L): if n < nums[j]: result = max(dfs(j) + 1, result) cache[i] = result return result
@@DavidDLee, you would need to call dfs on every i in the array, making sure the cache is populated for every i in an array and then finding the max between all possible results. In terms of complexity, at least as far as I've got it's pretty much the same as DP -> Time O(n ^. 2) def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) @cache def dfs(i): curr_max = 1 for j in range(i + 1, n): if nums[j] > nums[i]: curr_max = max(curr_max, 1 + dfs(j)) return curr_max return max(dfs(i) for i in range(n))
how times has changed... competition is so fierce now that people expect you to get the binary search right out of the bat... go this question at Meta interview, the interviewer wanted the binary search solution.
Coding interviews should be 1 hour long. First 30 minutes, the interviewee asked the interviewer to solve a DSA medium/hard problem. If the interviewer finds the optimal answer within 30 minutes, we proceed to the next part where the interviewee finds the optimal solution for the interviewer's DSA problem. If the interviewer fails to answer, the interviewee proceeds to the next step of the recruitment process.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Will never forget my first day on the job where a customer requested a feature to find the longest increasing sub-sequence. A totally valid way to test someones competency as a developer
Your sarcasam is depressive and hence ironic
It is important to understand the idea of subsequences, use memory efficiently and understand complexities of exponentially increasing subroutines.
A good Programmer is not the one who solves it the first time seeing it.
A good Programmer is the one who understands all the dimensions of the problem and Learn as much as he can about underlying intuitions.
and remember
when Tony Hoare first made Quick Sort He didn't say I am not going to face a situation where I sort a customer's Needs.
His attitude as any computer scientist when making a helpful research or an idea was If I am able to think How to sort and even invent a sorting algorithm then I am going to be able to satisfy my Customer needs who were Future Generations that used Quick sort in every Customer related Situation .
Good bye.
@@kotb2000 gg
Which interviewer hurt you bro
@@zweitekonto9654 All of them
Please keep that tone and speed of voice. It really helps to "understand" the solution. All of us are here to "understand" the solution not just for a solution. You will do great my dude.
This how you except a google engineer
You can change the playback speed on TH-cam to make it go faster or slower. In case you find a problem that some other youtuber has solved, that Neetcode hasnt solved yet, use that feature.
You sir. Are the savior. Your made it so simple - some times you make me guilty why I could not think of it. Keep them coming!
why? he is just taking what he learned and regurgitated it to you. He didn't come up with this solution on his own just like you didn't.
"I really doubt your interviewer is going to expect you to get this without a hint; if they do I'd just walk out of the room"
Probably worked great up until the layoffs 😥
yep, now it feels like every other interview problem has been next level. still some easies out there though :(
You're the best at actually explaining the reasoning behind these problems and all your views are so well deserved. I'm absolutely dreadful at these despite being a senior dev but you don't know how much your channel has helped, thank you!!!
Thanks, great explanation as usual, who needs cracking the coding interview when this exists!
This explanation went down so smooth -your voice was very easy to follow and your diagrams weren't sloppy and not complex to understand -this might be the cleanest solution I have seen for this problem for beginners to study!
Thank you for letting us know when we should walk out of the room. And what difficulty to expect in the interview :)
this is brilliant, I wonder who can think of this solution for the first time during the interview
Thank you for the clear explanation! For those wondering why going backwards in dynamic programming, you can actually solve this in forward dynamic programming, start from the beginning, too.
Your explanation is so great. The tone, voice, and the way you say are so clear. Thank you so much
thank you omgosh this really is the best explanation one can find for this question on youtube
That was so simple and an epic explanation of how you can start thinking about approaching this problem.
Being a beginner at dp, your videos help me understand how to start approaching a problem :)
Thankyou!
"I'd just walk outta the room" you solve your own problem Mr interviewer LOL
Easily the best channel for leetcode solutions. So easy to understand and code is always clean and concise. Hats off to you, Neetcode!
Clear explanation! I believe you are the rising star in solving leetcode problem.
haha, thanks I appreciate the kind words
excellent! This taught be how to choose subarrays recursively, and then the problem is trivial. Thanks a bunch.
Superb Explanation.Anyone having doubt in leetcode can refer this channel.Excellent video bro.I was struggling for this problem you made it clear.Thank you.
I got it crystal clear now. You explained it very well. Thanks a lot.
I kinda had half of the intuition but you cemented it for me. Simply lovely as usual!
Thanks for such a great explanation, I searched for it so many places, but I didn't find anything more than the formula. This video should have more likes.
Yeah, I agree that being expected to find the O(nlogn) solution is walkout tier. I came damn close to figuring it out: use an ordered set to keep track of the elements you've inserted so far so that you can easily find the greatest value that's smaller than or equal to your current one. From here, assuming nums[i] is not your maximum thus far, there are two ways, and figuring out either of them is easily upper Hard level: either you actually delete the value you've found (the fact that this works because it means you can just return the size of your set at the end is incredibly unintuitive), or you mess with the way you store everything in the set so that you can still retrieve the index of the value corresponding to your found value (which is awful to implement).
Why would deleting the value you found work? If you have input array [2,3,1,5,6] you cannot delete the value found at 5 when you see the 1, because then you cannot use it for the actual longest subsequence of 2,3,5,6
Tbh the approach of using a heap to store the subsequence length cache is quite reasonable imo… it’s annoying to implement but quite straightforward as an obvious improvement. If you know how to solve heap problems, which are based on the premise that a heap is a priority queue, why not just apply that here when you are searching for the largest element?
@@SunsetofMana Not sure a heap would work, you mean for when you check the max right? You still have to know if nums[i] is less than the value, it's not enough to find the largest subsequence. In that case, it's still O(n^2).
DP always surprises me. What a good approach. Thank you
Absolutely love the last line "I would just walk out of the room"😂
Not sure why, but this one felt much easier than the prior 3-4 problems in the Neetcode Dynamic Programming learning path. Got it on my first try, and solved it exactly the way Neet did. Just goes to show the value of the Neetcode Roadmap, and how the patterns start to solidify in your mind over time.
That's correct, I feel the same way
Thanks for the explanation @neetcode , code in java :
class Solution {
public int lengthOfLIS(int[] nums) {
int dp[] = new int[nums.length];
Arrays.fill(dp, 1);
for (int i = nums.length - 1; i >= 0; i--) {
for (int j = i-1; j >=0; j--) {
if (nums[i] > nums[j]) {
dp[j] = Math.max(dp[j], 1 + dp[i]);
}
}
}
int maxLIS = 0;
for (int i = 0; i < nums.length; i++) {
maxLIS = Math.max(maxLIS, dp[i]);
}
return maxLIS;
}
}
The best explanation video I have watched so far!
even if it's not the best solution, it's the best tutorial for LIS I've ever seen
"I really doubt your interviewer is going to expect you to get this without a hint; if they do I'd just walk out of the room"
LMAO!
Excellent oration of the logic and the ending is at another level.
Was unable to wrap my head around this one. Your explanation was so nice!!
Bravo ! 👏 You need an standing ovation.
last statement : 'walk out of the room' really made me laugh😂😂.. that's the attitude
"I really doubt your interviewer is gonna expect you to get the O(n logn) solution without a hint. If they do, I would personally just walk out of the room." XDDDDD
This happen with me yesterday, he didnt given any hint, result is i failed the interview
I came for that nlogn solution. But again, thanks for the tremendous help as usual
This was a great explanation! I struggled with this, but I'm happy to learn some new techniques!
One of the best solutions ever. thank you.
🎵 this is two,
and this is two,
so it doesn't really matter,
which one we do. 🎵
Music by Neetcode at 13:34
Wow, what a great explanation! Thank you for the detailed step-by-step example.
Agreeing with everything except the walking out part :)
noticing the subproblem 'is there an increasing subsequence with length m' is O(n), and m is between 1 and n, we can use binary search and get overall complexity O(nlogn). But it is way neater with DP
Thanks!
Hey Shannon - thank you so much, I really appreciate it!! 😊
Dynamic programming hurts my brain, but this and a few other videos are helping me out. Thanks muchly!
That sarcasm at the end made me laugh like hell😂😂😂! I'm also walking out from this problem
It is interesting that you calculated DP from right to left. I think it also works if you do from left to right.
Yes it works both directions.
@@briankarcher8338 i thought so.
Oof this is the first DP Problem I solved on my own! Was so happy that mine looked a lot like yours.
Man 8 lines of code is all it takes, grate solution
Great demostration starting from brute force, work way up to memoization and then leads naturally to dp!!! So Nice and easy it becomes with your approach!
1 question though: Why work from end backwords? How did you get the instinct?Could you please share your thougghts?
I'm used to working from the end backwards because it's similar to the recursive approach. But it's possible and maybe more intuitive to start at the beginning. Whatever makes sense for you is the best approach I think.
Example: [1,4,2,3], While computing longest common subsequence starting from index 0, the number at index 2, will be used. While computing longest common subsequence starting from index 1, the number at index 2 will be used. What i mean by "Will be used" is i am asking a question: What is the longest common subsequence starting from index 2. So if we had started computing longest common subsquence from backwards, then when we compute longest common subsquence for index 0 and 1, we already have the answer for longest common subsequence starting from index 2 stored.
Really helped me out to understand this question!
Thanks, I'm glad it was helpful!
The video made it very easy to understand. Thank you for making this video. Keep up the work. I’m looking forward to view yours next videos.
No need to complicate it further by doing reverse looping, from 0 to n works just fine with the same function of max(lis[i], 1+lis[j]) for i=0 to n, j=0 to i if nums[j]
another day watching neetcode to help me with leetcode. Thank you!
Man this is the best video so far on this problem ✊🏻
DFS: O(2^n)
DP: O(n^2)
Binary search: O(n logn)
it would be great to see the n log n approach
was looking for this comment
whether it should be if nums[i] < nums[j] or if nums[j] < nums[i]
IDK why but your voice in this video sounds really calming
Thanks
Hey thank you so much, I appreciate it! =)
"I would personally just walk out the room" LOL
When i feel its so hard to learn DSA problem and crack FAANG like companies my mind tells me "neetcode" and after seeing the video explanation i become calm and motivated to proceed further.
Optimal Approach O(nlogn)
bisect_left is a python function which gives the lower bound of the element in O(logn) time.
bisect_left(array, element, start, end)
class Solution:
def lengthOfLIS(self, arr: List[int]) -> int:
subs = [arr[0]]
for i in range(1,len(arr)):
if arr[i] > subs[-1]: subs.append(arr[i])
else:
subs[bisect_left(subs, arr[i], 0, len(subs))] = arr[i]
return len(subs)
So if arr = [1,3,4,2], then subs = [1,2,4] ?
That's not a subsequence.
And yet it works.
The mystery deepens... :-)
@@davidespinosa1910 Yeah, the problem asks for the longest increasing subsequence. So, this will still give you the correct length just not the subsequence itself
Great explanation, as usual, thank you! :)
11:34 I think using the name LIS[ ] is not a good choice, as you may think the final solution is LIS[0] this way. The strict definition of this lookup table, let's call it lookup[ ] is this: IF YOU TAKE THAT NUMBER nums[i] into the sequence, then what is the longest you can get. So lookup[i] IS IF YOU MUST INCLUDE nums[i] into that sequence. If you write LIS[i], it sounds like it is the max NO MATTER you include nums[i] or not, which is not the case. So that's why in the code that follows, the final result is not LIS[0], but max(LIS)
It’s looks easier after your explanation 👏🏻
Glad it was helpful!
Thank you very easy to understand and follow. I had problem understanding the solution on leetcode :)
Really very helpful, explained in a crystal clear manner👌👌
Great explanation as usual!! A repost(?) of the O(nlong(n)) solution, not that hard and really comes in handy for other problems :)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
indices = [None for _ in range(len(nums)+1)] # Mapping of size to the last indice of the subsequence
size = 0
def binary(elem, l, r): # a binary search is possible since the sizes are sorted by definition, even if the values in nums are not
while l
"I would personally just walk out of the room" I'm dead
Best explanation out there!! Thank you for your efforts.
finally a good explanation and solution for this, thanks!
"I would personally just walk out the room" haha
This is GOLD!
What's the point of the max()? Since we're checking that the subsequence is valid already, wouldn't it always resolve to 1 + dp[i]?
you're dynamic programming videos are all so well explained and helpful
Great Explanation,Thank a lot
Awesome! Very clear and thorough explanation 🙂
Great video, much appreciated. However, I didn't understand the logical jump at @10:40 that suggested we were "starting at 3". I would have preferred to see a solution that proceeded front-to-back, because it seemed to me that is what you were doing in the recursive solution.
O(nlogn) solution
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)
You are great.. you explained it very well. Thank you so much!
This explaination is so so good. Thank you.
leetcode editorial suggests improving time complexity with binary search
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
sub = []
for num in nums:
i = bisect_left(sub, num)
# If num is greater than any element in sub
if i == len(sub):
sub.append(num)
# Otherwise, replace the first element in sub greater than or equal to num
else:
sub[i] = num
return len(sub)
Great explanation, thank you
Great explanation. Curious about nlogn solution now.
Thanks!
Really nice explanation. Your video saved me lot of time.
Thanks!
I got asked to optimize the current dp solution in less than o(n^2)
You are awesome. Please keep it coming.
End was epic 😄.. "I'll probably walk out of interview"🙃
this is amazing, thank you for your hard work
Thank you sir best explanation able to do in other programming language easily and concept is clear
You are solving problems like God would solve, I attempted it and couldn't solve it in my first attempt though I knew what Dynamic programming is. Also, the way you explain choices and recursion is far the best way to start attacking problems like this.
"Personally, I would walk out of the room" - Yeah, man!
since we have already assigned LIS with value 1 for the length of nums, in the first for loop, we can start from len(nums) - 2 instead of len(nums) -1.
lol you kept typing LIST
great explanation, thanks!
do you mind sharing the code for the DFS solution? I just want to practice implementing these ideas.
def lengthOfLIS2(self, nums: List[int]) -> int:
L = len(nums)
cache = {L: 0}
def dfs(i):
if i in cache:
return cache[i]
n = nums[i]
result = 1
for j in range(i + 1, L):
if n < nums[j]:
result = max(dfs(j) + 1, result)
cache[i] = result
return result
return dfs(0)
@@DavidDLee, you would need to call dfs on every i in the array, making sure the cache is populated for every i in an array and then finding the max between all possible results.
In terms of complexity, at least as far as I've got it's pretty much the same as DP -> Time O(n ^. 2)
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
@cache
def dfs(i):
curr_max = 1
for j in range(i + 1, n):
if nums[j] > nums[i]:
curr_max = max(curr_max, 1 + dfs(j))
return curr_max
return max(dfs(i) for i in range(n))
博主讲的真好！
very nicely explained bro
thanks a lot
how times has changed... competition is so fierce now that people expect you to get the binary search right out of the bat... go this question at Meta interview, the interviewer wanted the binary search solution.
amazing explanation
Coding interviews should be 1 hour long. First 30 minutes, the interviewee asked the interviewer to solve a DSA medium/hard problem. If the interviewer finds the optimal answer within 30 minutes, we proceed to the next part where the interviewee finds the optimal solution for the interviewer's DSA problem. If the interviewer fails to answer, the interviewee proceeds to the next step of the recruitment process.