Can you please help me out on this as this question is asked in my interview @takeUforward AMY AND SCHOOL Problem Statement Wizard-Land can be represented as infinite line with coordinates ….., -3, -2, -1, 0, 1, 2, 3 … and so on. Amy teaches in a school with N batches of students. Ai denotes the number of students in the ith batch. Amy has to choose one coordinate as school and one coordinate for each batch of students as their hostel. Students of same batch lives in one hostel. All the N+1, coordinates chosen by her must be distinct. Each morning students walks from their hostel to the school. If the student’s hostel is at coordinate XH and school is at coordinate XS, then he travels | XS - XH | units of distance. She wants to assign these N+1, coordinates such that total distance travelled by each student to reach the school in morning is minimized. Find the minimum total distance. You are given T independent test cases. Constraints 1
Every other UA-camr just speaks the code out, it's only you who focus on explaining the question by manually drawing and dry running it. That's the identity of a real hero. Thanks a lot.
@@dikshasoni52a98 Because If 7 is on left of 4 then 4 will be LCA .So no need to go down as we will either get NULL or p or q or some common node (root) nothing else
Understood!! PS:- You will be given a two nodes and you need to return LCA of those two nodes. Solution approach:- Use DFS traversal(Recursive DFS) first go to left and then go to right. 0) If the root node is only one the node which you are looking for then return root 1) If both left and right returns null then returns null 2) If left returns a node and right returns null then return left and vice versa (Return something which gives u node) 3) If both returns you the nodes then u have found the answer so return root Code:- class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null || root==p || root==q){ return root; } TreeNode left=lowestCommonAncestor(root.left,p,q); TreeNode right=lowestCommonAncestor(root.right,p,q); if(left==null){ return right; } else if(right==null){ return left; } else{ return root; } } }
I could never think, of such a great Idea. I approached this probelm in different way. We can level order traverse each node to find the nodes parent and the level they are in. so, for the given 2 nodes, the node which is higher level can be taken up to the level of node in lower level. After this, in each iteration of leel decrement, keep check if we found a mtach between those 2 node. if yes, return the answer, other wise, keep decrementing level, by moving to the parent node.
In the third case, i guess lca(2,6) would be 1 because the proper ancestor of n is any node y such that node y is an ancestor of node n and y is not the same node as n.
Your explanations are truly remarkable and have greatly helped me in understanding complex concepts more clearly. Your dedication to simplifying intricate topics and your engaging teaching style make learning DSA both enjoyable and enlightening. Take love sir.
Hey striver, Space Complexity of first approach should O(H) for each call because at maximum we can have nodes equal to the height of the tree. Thanks for the lecture.
To save people time, In this video he only explained one case where you will get one element in left side and one in right. but there are also some cases, Consider that we have both the elements in left side of subtree? or there is no element present etc. So this is not the video I was looking for I like to understand every possible case.
The solution was great but I think it wont give right answer if the other node is not in the tree. In that case we have to do brute force only I think. Edit: I just saw the leetcode question of this video and it was mentioned that it is guaranteed that p and q will be present in the tree.
Intuition: Consider a node as a potential answer (LCA). If both left and right subtrees return non-null values, it means both nodes p and q have been found in different subtrees, confirming that this node is indeed the LCA. Now, consider a node that is not the answer. In this case, either the left or right subtree (or both) will return null. However, if one of them is not null, it indicates that one of the nodes (p or q) has been found, and this information will be passed up the tree to potentially contribute to identifying the LCA at a higher level. class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null || root.val==p.val || root.val==q.val){ return root; }
hey striver, I really like ur videos because of the clarity with whick you teach. However, this video lacked clarity, as i wasnt convinced why would that case work where lca(x, y) is x. However it worked, and after doing some dry runs i understood why it worked but you didnt cover this case in the examples. Just a positive feedback 😄
Python code: class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root or root==p or root==q: return root l=self.lowestCommonAncestor(root.left,p,q) r=self.lowestCommonAncestor(root.right,p,q) if not l: return r if not r: return l return root
Looking at comments I think I am the only one who got another idea apart from this recursive approach. The intuition is to use property of BST. the right of node will contains elements > root and left of nodes will contains elements < root. So you can use this to find the solution iteratively.
Thansk a lot for both approaches.............Most of us think that ....what if p and q both on the same path then ?... Like if p and q on the same path then, first whether p or q meet on that path and return that and no need to go further onthat path and all other root will then return null ...SO as Striver said, if either of null then we return value part.. so we got answer in this case too. Can there will be a duplicate node too @striver?
In this question, we are guaranteed to find p and q as per the problem statement. One interesting follow up question is : return null if either p or q or both are not present in the tree. Hint : solve it using a Post Order traversal.
@@renukasubramaniyam754 I think it was mentioned in question that both nodes are present. However, even if it's not mentioned, we can have 2 flags found1 and found2, and iterate once to see if both are present. And if anyone or both are not present, we can return null without performing actual logic.
@@takeUforward hey then if the question comes likes print the path from one node to the other one including the lca (which will be a distinct path) this approach would not work right? then the brute force approach is needed right?
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
Understooooooooooooooood :)
and done everything thank u so much striver :)
Do TreeNode* left and right take space? I mean definitely there's pointer to heap/ dynamically
Will this approach work if numbers are not present in the tree?
done bro
Can you please help me out on this as this question is asked in my interview @takeUforward
AMY AND SCHOOL
Problem Statement
Wizard-Land can be represented as infinite line with coordinates ….., -3, -2, -1, 0, 1, 2, 3 … and so on. Amy teaches in a school with N batches of students. Ai denotes the number of students in the ith batch.
Amy has to choose one coordinate as school and one coordinate for each batch of students as their hostel. Students of same batch lives in one hostel. All the N+1, coordinates chosen by her must be distinct.
Each morning students walks from their hostel to the school. If the student’s hostel is at coordinate XH and school is at coordinate XS, then he travels | XS - XH | units of distance.
She wants to assign these N+1, coordinates such that total distance travelled by each student to reach the school in morning is minimized. Find the minimum total distance.
You are given T independent test cases.
Constraints
1
Every other UA-camr just speaks the code out, it's only you who focus on explaining the question by manually drawing and dry running it. That's the identity of a real hero. Thanks a lot.
I watched about 4 minutes of your video and coded it myself.. Your explanation is just heaven .
but the real part starts after 4minutes😂
@@als_venky7057 😂😂
@@als_venky7057 xD 😂😂😂😂
@@als_venky7057 😅😅
that approach should not be done..
watch the latter half for the optimal approach
Best solution,
After 5 minutes of understanding, I got that why we don't need to go forward after getting anyone of the descendants.
hats off🤠
Can u tell why we don't have to go further ... I didn't get it ........ What if 7 is on left or right of 4 ......
@@dikshasoni52a98 Because If 7 is on left of 4 then 4 will be LCA .So no need to go down as we will either get NULL or p or q or some common node (root) nothing else
Understood!!
PS:- You will be given a two nodes and you need to return LCA of those two nodes.
Solution approach:- Use DFS traversal(Recursive DFS) first go to left and then go to right.
0) If the root node is only one the node which you are looking for then return root
1) If both left and right returns null then returns null
2) If left returns a node and right returns null then return left and vice versa (Return something which gives u node)
3) If both returns you the nodes then u have found the answer so return root
Code:-
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root==p || root==q){
return root;
}
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left==null){
return right;
}
else if(right==null){
return left;
}
else{
return root;
}
}
}
I tried to understand the logic by myself for 2 times and then coded it without seeing anyone's code. Feeling so good💗
heyy same, but why are you here then🤔
@@electronx5594 Just to comment this. 😄
I could never think, of such a great Idea.
I approached this probelm in different way.
We can level order traverse each node to find the nodes parent and the level they are in.
so, for the given 2 nodes, the node which is higher level can be taken up to the level of node in lower level. After this, in each iteration of leel decrement, keep check if we found a mtach between those 2 node.
if yes, return the answer, other wise, keep decrementing level, by moving to the parent node.
what is thought was of do two dfs for each node notice the path of each and then run a check on the path of the string
Striver bhai rocked.. buddy you are helping thousands of folks like me preparing for DSA interview. :)
hey @take U forward, i dont usualy comment here but its really motivating to see you hustle so much. We get to learn a lot from your personality.
Thanks a lot for contributing to the community.
Nicely understood!!!
In the third case, i guess lca(2,6) would be 1 because the proper ancestor of n is any node y such that node y is an ancestor of node n and y is not the same node as n.
Your explanations are truly remarkable and have greatly helped me in understanding complex concepts more clearly. Your dedication to simplifying intricate topics and your engaging teaching style make learning DSA both enjoyable and enlightening. Take love sir.
The best explantion 🔥🔥🔥🏅 really loved it🔥🔥I must say this is your best video
best explanation till date!!Vey very very easily understood as a noob coder.Thanks a lot!!
I never comment on vedio, but this was extremely sweet to go uncommented.
I love how you articulate every step, you are a saviour brother
Never thought that the solution for this question will be so simple and easy to understand.
Bhai ismei simple kya tha 😢
i am solving question by myself without watching lec bcoz of youre awosome lectures thank you keep it up!!
// Code For Naive Solution
class Solution {
bool getPath(TreeNode* root, TreeNode* x, vector &path) {
if (root == NULL) return false;
path.push_back(root);
if(root == x) return true;
if (getPath(root->left, x, path) || getPath(root->right, x, path))
return true;
path.pop_back();
return false;
}
vector getPathtoNode(TreeNode* A, TreeNode* B) {
vector path;
if (A == NULL) return path;
getPath(A, B, path);
return path;
}
TreeNode* findLastCommon(vector a,vector b){
TreeNode *lastCommon=NULL;
for(int i=0;i
Love This solution
Classic binary tree question! Thanks Striver.
Understood,able to solve by brute force and with optimized approach after getting a hint.Thank you striver
Thank you very much! Striver is the best channel! I refer only to striver videos!
Simple and lucid explanation. Thanks, bro.
Amazing man.. the last line was what i was not able to understand, i.e. if both are not null,then return root. Thankyou bro.
Wow I was able to write the code myself just after explanation.
I've watched this video 5 times to understand the concept 😅.
Just want to thank u bhaiya for such an fabulous explanation and amazing content.
Such a cool teaching... and an awesome logic.
Explanation is flawless. keep it up.
Nicely explained and easily underatood
the optimized approach was awesome, loves the intuition !!! easyily understood
Hey striver, Space Complexity of first approach should O(H) for each call because at maximum we can have nodes equal to the height of the tree. Thanks for the lecture.
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Striver ,your videos are perfect.
To save people time, In this video he only explained one case where you will get one element in left side and one in right. but there are also some cases, Consider that we have both the elements in left side of subtree? or there is no element present etc. So this is not the video I was looking for I like to understand every possible case.
The solution was great but I think it wont give right answer if the other node is not in the tree. In that case we have to do brute force only I think.
Edit: I just saw the leetcode question of this video and it was mentioned that it is guaranteed that p and q will be present in the tree.
Commenting to increase count +1 , Nice collection of videos.
Next level explaination💯
u work is really helping us to understand this type of concept. So thank u !!
Completed 28/54 (51%) done!!!
striver sir you are op what is extreme level solution 😍😍😍😍well this is my first comment in your channel because you do a very good job
Thankyou for amazing solution Striver
Thank you so much Striver !
Great Explanation, loving the series so far
tree question are very easy after watching your lecture. thanks bhayia
your on a different level !!! thank you 💎
After so many days....yayyyy I could solve a ques all on my own and on first try...dayumn..Ik it's not a big deal but it's a good milestone for me
Intuition:
Consider a node as a potential answer (LCA). If both left and right subtrees return non-null values, it means both nodes p and q have been found in different subtrees, confirming that this node is indeed the LCA.
Now, consider a node that is not the answer. In this case, either the left or right subtree (or both) will return null. However, if one of them is not null, it indicates that one of the nodes (p or q) has been found, and this information will be passed up the tree to potentially contribute to identifying the LCA at a higher level.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root.val==p.val || root.val==q.val){
return root;
}
TreeNode left= lowestCommonAncestor(root.left,p,q);
TreeNode right= lowestCommonAncestor(root.right,p,q);
if(left != null & right != null){
return root;
}
return left != null?left:right;
}
}
I liked this convention more.
if ( left && right) return root;
else if ( left) return left;
else return right;
Understood ❤
Crystal clear explanation !!
Well illustrated. Thanks
too smooth too good...amazing explanation...thank you STRIVER
superb explanation!!! it made trees very easy for me. Thank you so much.
faadu bhai faadu
now i feel confident in trees by watchng this tree series.
nice bro keep it up you are our motivation😎😎😎
hey striver, I really like ur videos because of the clarity with whick you teach. However, this video lacked clarity, as i wasnt convinced why would that case work where lca(x, y) is x.
However it worked, and after doing some dry runs i understood why it worked but you didnt cover this case in the examples.
Just a positive feedback 😄
Great explanation!
thanks bro, your dry run was great,, was struggling to visualize recurssion
how many more videos left in tree series?
Eagerly waiting for DP series.
great video .... very nicely explained ...... just loved it ❤
Thank you :)))) Was nicely explained.
Beautifully explained!!
One of the best dry run done ever
bhaiya just watching 4 min video i got accepted solution in leetcode simply hatsoff bhaiya i dont even think i can solve this question
Overwhelming explanation 👏👏👏👏 bhaiya 🥳🥳🥳
Python code:
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root==p or root==q:
return root
l=self.lowestCommonAncestor(root.left,p,q)
r=self.lowestCommonAncestor(root.right,p,q)
if not l:
return r
if not r:
return l
return root
very well explained !! Thanks
Understood! Super amazing explanation as always, thank you very much!!
Huge respect...❤👏
this is just perfect
Really loved the explanation!
Very nice explanation. Thank you.
crystal clear sir
You are so good. Thank you!
Looking at comments I think I am the only one who got another idea apart from this recursive approach. The intuition is to use property of BST. the right of node will contains elements > root and left of nodes will contains elements < root. So you can use this to find the solution iteratively.
its no where written in the question that its a binary search tree
very nicely explained
you got new subscriber . outstanding explanation !🙂
Best ever solution for this problem!
beautiful explanation my man.
UNDERSTOOD! THANK YOU🙌
Nice explaination!
Thansk a lot for both approaches.............Most of us think that ....what if p and q both on the same path then ?... Like if p and q on the same path then, first whether p or q meet on that path and return that and no need to go further onthat path and all other root will then return null ...SO as Striver said, if either of null then we return value part.. so we got answer in this case too.
Can there will be a duplicate node too @striver?
Thank you so much! Great explination...
Awesome Explanation! Understood.
ohhh bhaiiiiii, behtreeen solution hai
Just sooo good
Totally clear, loving this series. Thanks a ton for making this.❤️
It feels like I am sitting in my super confident English teacher class.
UNDERSTOOD;
Awesome Explaination..
Excellent
In this question, we are guaranteed to find p and q as per the problem statement.
One interesting follow up question is : return null if either p or q or both are not present in the tree.
Hint : solve it using a Post Order traversal.
Superb explanation!
@10:08 you returned when you found 8, but what if 7 is present in 8's subtree, that is not explored?
Then 8 will only be the lca na even if 7 is under subtree. So why to go deep
What if 7 is not present in the tree at all
@@renukasubramaniyam754 I think it was mentioned in question that both nodes are present. However, even if it's not mentioned, we can have 2 flags found1 and found2, and iterate once to see if both are present. And if anyone or both are not present, we can return null without performing actual logic.
@@takeUforward hey then if the question comes likes print the path from one node to the other one including the lca (which will be a distinct path) this approach would not work right? then the brute force approach is needed right?
We learn from u bhaiya♥️
thanks man .... God bless you
good one
Thank you! 😇
thank you
thank you , you helped a lot