Unique Binary Search Trees - Leetcode 96 - Python Dynamic Programming

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: leetcode.com/problems/unique-...
0:00 - Conceptual
6:25 - Coding solution
#amazon #interview #question
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

Dynamic Programming Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@lizziedaffofil6064]

No one can beat you in giving such a clear explanation even to complex topics! Way to go!

[@chaoluncai4300]

fr dawg, neetcode is the only person that drove me solve(watch) 10+ medium+ problems in one day

[@TrollFreeInternet]

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.

[@08JuHan]

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

[@aatishjain9770]

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.

[@AlfranAli]

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! :)

[@RebornAc3]

Very helpful, thank you!

[@uncleroku8962]

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?

[@anthonysummit3098]

Yeah

[@chaoluncai4300]

@@anthonysummit3098 yeh

[@saijannali9725]

I was wondering the same thing, makes sense

[@mayankkhanna9644]

If I got this problem in an interview, I would cry. But not anymore..

[@tripathi5174]

was struglling for one day and then i found this helpful video , very well done

[@pahehepaa4182]

Thanks! This was sweet. Easy to understand. Other videos are complicating stuff 😶 Subscribed.

[@wlcheng]

Brilliant solution. Thank you!

[@KidUnicefalo]

Thanks a lot, amazing explanation!

[@apoorvbedmutha457]

The explainnation is so good ! you're an absolute legend

[@calvincruzada1016]

such a clear explanation, wowzers

[@tanaysingh5348]

crisp explanation

[@chujunlu919]

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.

[@NeetCode]

Glad it was helpful!

[@siningsun4160]

The best explanation I've ever seen.

[@polyrain]

Why did you n+1 in the memo table? Just to capture numTree[0]? Great vid!

[@mashab9129]

wow! as always the best explanation.

[@patthiccc]

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.

[@NeetCode]

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!

[@abhicasm9237]

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.

[@user-ls2tk7mr1m]

excellent explaination

[@ameynaik2743]

Can you please make another video on unique bst ii I.e listing the possibilities?

[@nikhilgoyal007]

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 ?

[@nikhilgoyal007]

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.

[@LaithBasilDotNet]

Even though the top down dynamic programming approach works, leetcode timeout for it.

[@andreytamelo1183]

Thanks!

[@tirupatirao7521]

Great one

[@symbol767]

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

[@arsahilar]

@7:44 fOR LAST VALUE shouldn't it be NODE[3] in left * and NODE[0] on right

[@atanunayak6637]

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?

[@samuraijosh1595]

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?

[@samuraijosh1595]

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.

[@mehulsolanki9435]

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

[@pawankumarmeena6737]

💯

[@tanhnguyen2025]

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 😂

[@Saurabh2816]

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.

[@deidarasenpai3243]

can someone explain how time Complexity is O(n^2) . I think it must be n!

[@hayyan612]

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)

[@monguyen7634]

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?

[@lindama1276]

Why is num trees 0 equal 1?

[@negarvahid]

Because we only have one option which is NULL.(or None)

[@jhonrobaon1669]

I have a question at 4:13 (kzbin.info/www/bejne/hamThZikg5iNpsk), can you please let me know why we need to multiply for combinations?

[@somdutroy]

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.

[@TheAlexanderEdwards]

@@somdutroy Thank you for this explanation!

[@Assta77]

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?

[@arenmkhoyan]

Recursion is bad and slow, we have to use dp

[@fefefefefee32]

I don't understand. Forgive me but this isn't so clear to me.

[@grasstoucher856]

There is a mistake at line 6 I think. Thanks for the solution nevertheless

[@CS_n00b]

*click* noice

[@jay-rathod-01]

This sounds like a pretty simple problem😐 If it were simple why would i be here.

[@NeetCode]

That's true, the seemingly simple problems are always the most challenging

[@aviralarpan7350]

I am best

[@RobinHistoryMystery]

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

[@RobinHistoryMystery]

im back, still confused, I hope I never cross path with this question in my life

[@MishkatMazumder]

@@RobinHistoryMystery haha