I think there is a mistake with the last value at 7:45...it should be numTree[3]* numTree[0]..not numTree[3]*numTree[1]... it won't make difference to the answer but it might confuse some people.
Thanks for posting it! Java version in case anyone's interested class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int nodeCount = 2; nodeCount
For this particular problem, if you see the pattern it's following catalan number which can be solved in O(n) time & O(1) space, just mentioning it here for future readers to go and check that out too. Nice initiative, keep up the good work! :)
Had no idea how to approach this problem after reading the problem statement. Not sure when will get over this. As always best and savior for us. Thanks a ton bro.
Question: at 7:40 you said that when you get to the last value (the node being 4). You'd have one node in your right subtree. Wouldn't it be zero values in your subtree when 4 is the root, since all other nodes would be smaller?
My recursive solution with memoization: def numTrees(self, n: int) -> int:
self.trees = {} self.trees[0] = 1 self.trees[1] = 1 self.trees[2] = 2 return self.getTrees(n) def getTrees(self, n): if n in self.trees: return self.trees[n] l,r = 0,n-1 res = 0 while r>=0: res += ( self.getTrees(l) * self.getTrees(r) ) l += 1 r -= 1 self.trees[n] = res return res
When you change variable i, j from Leetcode's solution to something descriptive, like this video does, suddenly the underlying thinking comes through, and the code makes sense.
thanks! for line #13 - I would have think - root should go from 0 to node +1 ( even if left is None for root = 0 - there our some combinations that will result from the right side ?). what am i missing pls ?
DOUBT: line 6, numTrees[3]*numTree[1]. When we pick the last node as the root node we would have 3 values in the left subtree and 1 value in the right subtree. Why? Should we have 0 values in the right subtree? As we selected the last value as root then there will be no choices to make for the right subtree it would be just a null.
I understand everything in the solution, except for the thing that why do we just multiply the values, I mean there can be other cases as well right? Let me elaborate, If you draw the diagram for 5 nodes solution, for f(5) we have f(3)*f(1) is good, but the three on the left also have 4C3 choices right?
yeah the code based on the combinatorics seems to work but i dont get what the fuck is combinatorics doing here at all. i wonder if youve figured it out?
ok now i got why we multiply them. firslty, a small correction for f (5) we have f(3) on the left and f(1) on the right subtree only for root node 4. {1, 2, 3} --- 4 --- {5 } now {1, 2, 3} can be arranged in how many unique trees is calculated by f(3) and so is {5} calculated. we get f(3) = 5, f(1) = 1. good. this is a simple case to explain where we have unique three things of one kind and 1 thing of another kind. so there's only three ways to arrange these two togetehr wohtout reptions such that they both get exist at the same time. if we take a case like f(3) on the left and f(2) on the right: we have three blue balls and 2 red balls. how would you arrange 3 blue balls with 2 red balls wihtout reptitions? 3 * 2 = 6 is the way to do it.
Let's say the the left side the tree has 3 combinations makes as A, B, C and the right side has two combinations D, E. So, the possible trees are A-root-D, A-root-E, B-root-D, B-root-E, C-root-D, C-root-E. Hence, 6 combinations or 3*2 in this case.
Are you using the Bottom-up approach for this problem? Because I think you had the two base value from which u can work your way up to adding those to n 😂
How do you decide on Memo dimensions? That is always where I go wrong. I'll try to use a 2d memo or 1d memo when the opposite is needed and I get nowhere.
That's a great question because figuring out the dimensions is usually the key in DP problems. Whenever i make a mistake in difficult problems I usually look for slightly easier problems in the same category. I solve these before repeating the difficult problem. Even with practice i still occassionally make mistakes, but I hope this helps!
Hey @patthiccc, I hope that you would know better than me right now, but to add my 2 cents... What I have noticed from my practice is that the dimension of the dp depends on the number of variables that are changing. In cases like the knapsack where the index and the target changes, we use 2d array to store the index and the respective target. Hope it helps.
suppose n=3 so nodes would be 1,2,3 for us to return the final answer we need to find number of unique bsts we can make with all nodes (1,2,3) as root nodes for each root node we'll have to compute the left and right child from the nodes which makes it O(n^2)
Dynamic Programming Playlist: ruclips.net/video/73r3KWiEvyk/видео.html
I think there is a mistake with the last value at 7:45...it should be numTree[3]* numTree[0]..not numTree[3]*numTree[1]... it won't make difference to the answer but it might confuse some people.
No one can beat you in giving such a clear explanation even to complex topics! Way to go!
fr dawg, neetcode is the only person that drove me solve(watch) 10+ medium+ problems in one day
Thanks for posting it! Java version in case anyone's interested
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int nodeCount = 2; nodeCount
For this particular problem, if you see the pattern it's following catalan number which can be solved in O(n) time & O(1) space, just mentioning it here for future readers to go and check that out too. Nice initiative, keep up the good work! :)
Very helpful, thank you!
Had no idea how to approach this problem after reading the problem statement. Not sure when will get over this. As always best and savior for us. Thanks a ton bro.
Question: at 7:40 you said that when you get to the last value (the node being 4). You'd have one node in your right subtree. Wouldn't it be zero values in your subtree when 4 is the root, since all other nodes would be smaller?
Yeah
@@anthonysummit3098 yeh
I was wondering the same thing, makes sense
If I got this problem in an interview, I would cry. But not anymore..
My recursive solution with memoization:
def numTrees(self, n: int) -> int:
self.trees = {}
self.trees[0] = 1
self.trees[1] = 1
self.trees[2] = 2
return self.getTrees(n)
def getTrees(self, n):
if n in self.trees:
return self.trees[n]
l,r = 0,n-1
res = 0
while r>=0:
res += ( self.getTrees(l) * self.getTrees(r) )
l += 1
r -= 1
self.trees[n] = res
return res
When you change variable i, j from Leetcode's solution to something descriptive, like this video does, suddenly the underlying thinking comes through, and the code makes sense.
Glad it was helpful!
was struglling for one day and then i found this helpful video , very well done
Thanks! This was sweet. Easy to understand. Other videos are complicating stuff 😶 Subscribed.
thanks! for line #13 - I would have think - root should go from 0 to node +1 ( even if left is None for root = 0 - there our some combinations that will result from the right side ?). what am i missing pls ?
Got it. 1: n + 1 is n nodes. if I had done 0: n, it would have been n nodes too (plus I would have to worry about left = root - 1 out of bound error.
crisp explanation
Why did you n+1 in the memo table? Just to capture numTree[0]? Great vid!
The explainnation is so good ! you're an absolute legend
Even though the top down dynamic programming approach works, leetcode timeout for it.
Brilliant solution. Thank you!
The best explanation I've ever seen.
DOUBT: line 6, numTrees[3]*numTree[1]. When we pick the last node as the root node we would have 3 values in the left subtree and 1 value in the right subtree. Why? Should we have 0 values in the right subtree? As we selected the last value as root then there will be no choices to make for the right subtree it would be just a null.
I understand everything in the solution, except for the thing that why do we just multiply the values, I mean there can be other cases as well right?
Let me elaborate,
If you draw the diagram for 5 nodes solution, for f(5) we have f(3)*f(1) is good, but the three on the left also have 4C3 choices right?
yeah the code based on the combinatorics seems to work but i dont get what the fuck is combinatorics doing here at all. i wonder if youve figured it out?
ok now i got why we multiply them. firslty, a small correction for f (5) we have f(3) on the left and f(1) on the right subtree only for root node 4. {1, 2, 3} --- 4 --- {5 }
now {1, 2, 3} can be arranged in how many unique trees is calculated by f(3) and so is {5} calculated. we get f(3) = 5, f(1) = 1. good. this is a simple case to explain where we have unique three things of one kind and 1 thing of another kind. so there's only three ways to arrange these two togetehr wohtout reptions such that they both get exist at the same time.
if we take a case like f(3) on the left and f(2) on the right: we have three blue balls and 2 red balls. how would you arrange 3 blue balls with 2 red balls wihtout reptitions? 3 * 2 = 6 is the way to do it.
Why is num trees 0 equal 1?
Because we only have one option which is NULL.(or None)
I don't understand. Forgive me but this isn't so clear to me.
@7:44 fOR LAST VALUE shouldn't it be NODE[3] in left * and NODE[0] on right
Can you please make another video on unique bst ii I.e listing the possibilities?
I have a question at 4:13 (ruclips.net/video/Ox0TenN3Zpg/видео.html), can you please let me know why we need to multiply for combinations?
Let's say the the left side the tree has 3 combinations makes as A, B, C and the right side has two combinations D, E.
So, the possible trees are A-root-D, A-root-E, B-root-D, B-root-E, C-root-D, C-root-E.
Hence, 6 combinations or 3*2 in this case.
@@somdutroy Thank you for this explanation!
Are you using the Bottom-up approach for this problem? Because I think you had the two base value from which u can work your way up to adding those to n 😂
How do you decide on Memo dimensions? That is always where I go wrong. I'll try to use a 2d memo or 1d memo when the opposite is needed and I get nowhere.
That's a great question because figuring out the dimensions is usually the key in DP problems. Whenever i make a mistake in difficult problems I usually look for slightly easier problems in the same category. I solve these before repeating the difficult problem. Even with practice i still occassionally make mistakes, but I hope this helps!
Hey @patthiccc, I hope that you would know better than me right now, but to add my 2 cents... What I have noticed from my practice is that the dimension of the dp depends on the number of variables that are changing.
In cases like the knapsack where the index and the target changes, we use 2d array to store the index and the respective target.
Hope it helps.
such a clear explanation, wowzers
Thanks!
excellent explaination
I love youi i just love you man you are great at teaching
Thanks a lot, amazing explanation!
But where are we ignoring the similar the structures like 2->1->3 and 3->1->2 have same structures. Aren't we considering both of them?
Crazy how they can give you these type of problems on an interview, I would have failed hard.
But now I wont thanks to you
wow! as always the best explanation.
hmmm, I thought it was n. Calculate once (O(n)) for for recursion and the rest can be accessed in (O(1)) => n. Where am I wrong hmmmm?
Great one
can someone explain how time Complexity is O(n^2) . I think it must be n!
suppose n=3 so nodes would be 1,2,3 for us to return the final answer we need to find number of unique bsts we can make with all nodes (1,2,3) as root nodes for each root node we'll have to compute the left and right child from the nodes which makes it O(n^2)
I am best
Recursion is bad and slow, we have to use dp
There is a mistake at line 6 I think. Thanks for the solution nevertheless
💯
This sounds like a pretty simple problem😐 If it were simple why would i be here.
That's true, the seemingly simple problems are always the most challenging
*click* noice
I think, Im just gonna be confused about this question, cant understand this question at all, watched so many videos about it
sigh... time to move on
im back, still confused, I hope I never cross path with this question in my life
@@RobinHistoryMystery haha