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 RU-vidr 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.
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; } } }
@@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
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.
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.
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.
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.
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.
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?
@@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?
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 😄
As soon as node 8 is encountered, it returns its value to the parent node and we don't even need to check for 7 bcoz in that case 7 will lie in the subtree rooted at node 8.
hi Striver thanks for the superb explanation as always! what device/tool do you use for your examples? some tips for taking whiteboarding interviews from home would be nice :)
what will happen in the case of skew tree? What if a node doesn't have it's left node and it's right node is the required node and the node itself is the required node. Then how this solution work in that case?
