If someone has difficulty in understanding the code then follow these steps : 1. dry run on paper with start =1 and end =1 2. dry run on paper with start=1 and end =2 Now finally, 3. dry run on paper with start =1 and end =3 You will definitely understand the concept and code after these 3 steps.
We MUST use DP or Memoization in such kind of problems. 1) DP approach for catalan Numbers :- int catalan(int n){ int dp[n+1]; dp[0] = 1; dp[1] = 1; for(int i=2;idata += s; inOrderChange(root->right,s); } Node* copyNode(Node* root,int s){ if(!root)return NULL; Node* n = new Node(root->data+s); n->left = copyNode(root->left,s); n->right = copyNode(root->right,s); return n; } vector possibleBST(int N,unordered_map &memo){ if(memo.find(N)!=memo.end()){ return memo[N]; } vector bsts; for(int i=0;ileft = j?copyNode(j,0):NULL; n->right = k?copyNode(k,(i+1)):NULL; bsts.push_back(n); } } } memo[N] = bsts; return memo[N]; } vector allPossibleBST(int start,int end){ unordered_map memo; vector v; v.push_back(NULL); memo[0] = v; vector vv; vv.push_back(new Node(0)); memo[1] = vv; vector bsts = possibleBST(end-start+1,memo); for(auto i:bsts){ inOrderChange(i,start); } return bsts; } Note That We cant use 2D array as memo because memo[0][2] or memo[5][7] have same BST with just different numbers, besides no overlapping is occurred for any start and end numbers, only their differences are overlapped. So we will use 1D array / map for memo and change BSTs numbers with inOrderChange() function. Happy Learning ...... :)
my code for the catalan sequence looks like this and is better in some way as the values are not getting calculated individually every time but using that same values we already calculated in previous iteration space complexity increased in my code : int catalanUtil(int arr[], int i, int n) { if(i < 0) { return 0; } int ans = arr[i]* arr[n] ; n++; i--; ans += catalanUtil(arr, i, n); return ans; } void catalanNum(int n) {
int c0 = 1; int c1 = 1; int arr[n]; arr[0] = 1; arr[1] = 1; for( int i=2; i
The formula of Catalan Number is (Ci-1)*1*(Cn-i) when i goes from 1 to n. and The formula of Catalan Number when i goes from 0 to n-1 as in this video is (Ci)*1*(Cn-i-1).
Sir mene B.A programme kar rakhi h but mujhe web development me interest h kya mujhe bhi amazon jesi company me job mil sakti h. Plzz video on this topic bahot saare students h jo non technical se but une web creation or web development aati h or usi me career banana chahte plzz sir es par jarur video banao
@@jiosim1377 no, i didn't understand last program so I skipped it. Also it is better to use dynamic programming in such questions which we will study at a later stage
@@adityabhandari6688 bro btw how has your progress been so far with this course? R u practicing questions side by side or only doing the questions from this course?
I tried to optimise this method now loops runs from 0 to (n/2) [so i think]. and it is giving right ans too. can someone tell me is optimized or not? int catalan(int n){ if(n
If someone has difficulty in understanding the code then follow these steps :
1. dry run on paper with start =1 and end =1
2. dry run on paper with start=1 and end =2
Now finally,
3. dry run on paper with start =1 and end =3
You will definitely understand the concept and code after these 3 steps.
*Correction at 13:36 - the 2ndTree is not a valid BST and the correct version of this will be simply :
1
\
3
/
2
just came to the comments to see someone clarify this thing only 😂
@@schrodingerscat6189 +1
thanks bro
Respect +1
i was thinking that too!
One line python code to generate Catalan numbers,
catalan = lambda n: 1 if n==0 or n==1 else sum(catalan(n-1-i)*catalan(i) for i in range(n))
We MUST use DP or Memoization in such kind of problems.
1) DP approach for catalan Numbers :-
int catalan(int n){
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;idata += s;
inOrderChange(root->right,s);
}
Node* copyNode(Node* root,int s){
if(!root)return NULL;
Node* n = new Node(root->data+s);
n->left = copyNode(root->left,s);
n->right = copyNode(root->right,s);
return n;
}
vector possibleBST(int N,unordered_map &memo){
if(memo.find(N)!=memo.end()){
return memo[N];
}
vector bsts;
for(int i=0;ileft = j?copyNode(j,0):NULL;
n->right = k?copyNode(k,(i+1)):NULL;
bsts.push_back(n);
}
}
}
memo[N] = bsts;
return memo[N];
}
vector allPossibleBST(int start,int end){
unordered_map memo;
vector v;
v.push_back(NULL);
memo[0] = v;
vector vv;
vv.push_back(new Node(0));
memo[1] = vv;
vector bsts = possibleBST(end-start+1,memo);
for(auto i:bsts){
inOrderChange(i,start);
}
return bsts;
}
Note That We cant use 2D array as memo because memo[0][2] or memo[5][7] have same BST with just different numbers, besides no overlapping is occurred for any start and end numbers, only their differences are overlapped. So we will use 1D array / map for memo and change BSTs numbers with inOrderChange() function.
Happy Learning ...... :)
thks for sharing this
thanks
Sir your videos are a real help sir you are doing a great job.
Lots of love and blessing for what you are doing.Cant wait for your job
Sir nhi ma'am.....😂
Both Aman bhaiya and Ma'am.
*Much love and Respect to whole Apna College team for providing this content on UA-cam.* ♥️
Keep Hustling 🔥
at 13:48 2nd one is not a BST
Thank you so much Aman bhaiya and team!!
my code for the catalan sequence looks like this and is better in some way as the values are not getting calculated individually every time
but using that same values we already calculated in previous iteration
space complexity increased in my code :
int catalanUtil(int arr[], int i, int n) {
if(i < 0) {
return 0;
}
int ans = arr[i]* arr[n] ;
n++;
i--;
ans += catalanUtil(arr, i, n);
return ans;
}
void catalanNum(int n) {
int c0 = 1;
int c1 = 1;
int arr[n];
arr[0] = 1;
arr[1] = 1;
for( int i=2; i
the formula of catalan numbers is wrong, it should be Cn+1 = Σ(CiCn-1) or Cn = Σ(CiCn-i-1)
pin this comment
Yes that's why I was not getting c2 value correct .
Cn+1= sigma CiCn-i hona chaheye shayad 1 ki jagah i hoga bro
this code is very complex to understand.
true, I am skipping this
Very good explanation di👍👍✨✨
How many times are you going to repeat preorder ? It's okay to copy paste.
Video ki length jitni jada ho utne jada pese milte h neha didi ko
hello to people waiting
Students k liy Aman Dhattarwal se best koi nhi 😍
13:53 possible BSTs 2nd BST is wrong
At 16:05 why the possible BST are two only, 3 can be connected in the term 1 in more 2 possible ways......
constructTrees was complicated. I don't understand the explanation 😥
Thank you 🙏🙏
Bhaiya notes kab milege
Thank You Apna College For This Amazing Lecture :)
if u r seeing this for the first time, then rewatch this, u probably won't get this fully in 1st watch
Did u understand in second watch?
@@jiosim1377 Nice Question!!
Notes Please
**The formulae of Catalan number was incorrect.Cn-i-1 should be there instead of Cn-i.
The formula of Catalan Number is (Ci-1)*1*(Cn-i) when i goes from 1 to n.
and
The formula of Catalan Number when i goes from 0 to n-1 as in this video is (Ci)*1*(Cn-i-1).
I think the recursive sequence for Catalan number is wrong at 1:32
What is the correct one then?
C2 or C3 upper jo mathematical definition btai h usse satisfy nhi kr rha...kya h ye
the second figure is wrong in 13:54 how can be 3 left child of 2
Very nice 👍👍
Guyzzz how willl we get the notes ...🙄
Pls somebody help me My VS-code is not running in the terminal it's showing that final link failed:No space left on device .
there are many errors and problems to be faced in VS-code , i would suggest u to use GDB online compiler
space compkexity zayada hoga(memory leak hona ka karan) ya harddisk tumhara full hogaya ha
Koi last code ko samjha do pls
bhai kaafi logo ko samajh nhi aaya last wala, mujhe bhi nahi aaya
Sir mene B.A programme kar rakhi h but mujhe web development me interest h kya mujhe bhi amazon jesi company me job mil sakti h. Plzz video on this topic bahot saare students h jo non technical se but une web creation or web development aati h or usi me career banana chahte plzz sir es par jarur video banao
Mam please upload notes
Why am i not able to understand the logic of the last code written? Is it only me?
me too
what is the name of the instructor?
Shraddha Didi
N=3 then only 4 BST Tree make
anyone continue this series please comment ...
yes, what do you want?
@@adityabhandari6688 bro are you able to understand the last code if yes can u explain?
@@jiosim1377 no, i didn't understand last program so I skipped it. Also it is better to use dynamic programming in such questions which we will study at a later stage
@@adityabhandari6688 bro btw how has your progress been so far with this course? R u practicing questions side by side or only doing the questions from this course?
@@adityabhandari6688 bhai mujah bhi samaj nahi aaya :( ........mere kuch oor print ho raha ha
I tried to optimise this method
now loops runs from 0 to (n/2) [so i think].
and it is giving right ans too.
can someone tell me is optimized or not?
int catalan(int n){
if(n
It is not optimised it's the same
I think this video suppose to be possible binary trees, not BST
Ia this course good or does the content become worser as we proceed??
yeah it is good, but you have to practice questions sideways as well
please make python lectures too...
oye i am ritwik ran hope i get placed to product based scene
code ka dry run to karado
Formula to calculate the next Catalan Number is wrong #correction at 1:15.
What is the correct one then?
*999k*
very difficult to understand
In 2nd example at 13:45 shouldn't it be
1
\
3
/
2
?
pehle khud samjhiye uske baad dusre ko samjhaiye...(BST)
After 19:00 khucch samaj nahi aaya :(
vector to dhang se padha do
Worst Explanation, after watching this i am more confused now :)
Dtcj
pehle khud samjhiye uske baad dusre ko samjhaiye...(BST)