DM ME YOUR FAVORITE VEGETABLE ON INSTAGRAM OR LEAVE IT IN THE COMMENTS BELOW 10% OFF ROOFTOP SLUSHIE: bit.ly/kevinnaughton instagram: instagram.com/kevinnaughtonjr/ twitter: twitter.com/kevinnaughtonjr patreon: www.patreon.com/KevinNaughtonJr merch: teespring.com/stores/kevin-naughton-jrs-store
I'm a visual learner so you drawing out how we should go about solving a problem on the iPad helps. I can really picture it in my mind now. Ty for always improving for content for us =)
Off the top of my head: Traverse both trees and values in two different strings respectively in preorder then Check if t string is substring of s string boom
Hey Kevin, so glad you're still uploading during the quarantine and I hope you're doing fine. I've been working on leetcode problems and studying your solutions. I was wondering if you could suggest resources to learn traversing graphs and trees, as I feel my data structures & algorithms class did a subpar job in teaching me these fundamentals. Thank you!
It's failing for this test case, which must be added recently, could you please check once? [1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2] [1,null,1,null,1,null,1,null,1,null,1,2]
I love popping the problem into search and finding that you made a video on it already. I know I'm in good hands at that point. These are really helpful--thanks and keep it up!
Hi , I tried the same code and it is failing under one of the test cases of the leetcode ->[1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2] [1,null,1,null,1,null,1,null,1,null,1,2] . you might want to take a look .
@@indiansoftwareengineer4899 I assume this code worked previously when the test cases were different. But this code is not supposed to work. He checks first if the root == subRoot and if its not then he checks root.left or root.right. That is all he does, he never checks anything beyond that point, so if the subRoot is equal to something deeper in the root then it wont find it, hence the error you get. A easy way to complete the solution would be to do a BFS in the Tree first and store it in an ArrayList. Then make a for loop and check for every node in the arraylist that has same value as subRoot.val, on that node try your recusrive method to compare the nodes.
You are given a two-dimensional matrix with N rows and M columns. Each cell (i, j) of the matrix has some value denoted by Ai,j. You can do some operations on the matrix (possibly many or zero). In a single operation, you can choose any two adjacent cells and increment the value of each of them by 1. Find the minimum number of operations to make the values of all the cells of the matrix equal. If it's not possible to make all cells equal print -1. Input The first line contains two space-separated integers N and M - denoting the size of the matrix. Each of the next N lines contains M space-separated integers representing the values of the matrix, where the jth integer on ith line denotes the value of cell (i, j) - Ai,j.
bro which one is better in ur opinion Ipad pro or macbook air ? all I want is a long battery duration and lightweight and portable and powerful ,fast and great Retinadisplay 😊
What I tried to do here is I broke the problem into two parts, the first part would find me the root of the subtree from our original tree, then from that new root I called isSame function and did the sameTrees code but it failed at testcase 158/182, I think it was because due to node values were same so my code's first part would've return me the root node instead [1,1] [1] of its left child.
Actually this can be improved by using a hashset. What you need to do is to serialise every subtree of S (including S itself)and store it in the hashset. Now all you need to do is to serialise T and check whether it exists in the hashset. Time complexity hence becomes O(|S|+|T|) with space complexity of O(|S|*|S|).
Not optimal since it has to look through every possible path. A more optimal approach would be a preorder traversal comparison at the occurrence of the target node. In this case, the program terminates at first success.
it's of the order O(n^2). Wanted to know of order O(n) solution. Title says amazon coding interview question , definitely they will ask you to optimize it.
I'm surprised that doing an iterative Preorder of both Trees, and then search if one of them is contained in the other is actually faster. But of course it consumes more space.
If we stored the inorder traversal of Tree S as a string and Tree T as a string and see if the patters of T exists within S then we can return true, this would be of time complexity O(M) right?
iPad is awesome Kevin, also you should try with apple pencil you will not be disappointed i promise. Note : you can use quicktime player on Mac to project ipad screen on mac , so u don't have to record separately and also u can explain any concept while writing the code side by side
The same problem is in cracking the coding interview and it says that the space complexity is O(log (n)+ log (m)), but it doesn't tell us why. It was solved the same why as you did, but with slightly different code.
Thanks Kevin! Really happy to see you uploading videos and doing well :) I'm going to have my final interview next week in a faang company, if i get the job i'd love to support your work :) Cheers!
I am considering an extension of this question. How about if we expect Example 2 to return true? Which means we want to find out if a tree t is a piece of tree s. What would be the algorithm?
Hi Kevin, I really like your videos! Thank you! Although I think you wrong in the space complexity cause in the second function is like you said min(m, n), but in your first recursion you go trow all the tree S so I think the answer is O(m). If you think I'm wrong, I hope you can help me understand why Thank you
Awesome video!! Kevin what's the best way for me to level up my Java skills? I can solve Leetcode medium's in JS but I'm feeling a bit lost when it comes to Java best-practices, even on Leetcode easy's.
Hey Kevin, Why you are not travelling complete s tree , you are just checking for s,s.left,s.right node. subtree t can need not be only at s,s.right and s.left, it can be anywhere
Thought the same, but then I noticed he used "isSubtree" in the last return statement of "isSubtree" (line 17), which is actually traversing the whole tree "s".
Hi Kevin, I really enjoy your vids and learn a lot and I strongly believe you give a better explanation of the problems compared to others on internet. I was wondering if you can help me prepare for my Amazon interview (virtual/phone interview with an engineer) which is scheduled in a week! Kindly let me know. Thanks.
A less efficient but more simpler method would be to traverse both the trees individually and append each node's value to a string. That way we'll have two strings for two trees and we can just check if one string is the "substring" of another string.
I was given this testcase and it failed: [1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2] [1,null,1,null,1,null,1,null,1,null,1,2] output: false, expected: true. Heres my code. I watched some of the video and had it a little different but using your approach, then i just straight up copied your solution and it still failed... I would like some help as to why this has happened. Thanks for the great content! class Solution { public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null) { return false; } else if(equalTree(s,t)) { return true; } else { return equalTree(s.left, t) || equalTree(s.right, t); } } public boolean equalTree(TreeNode s, TreeNode t) { if (s == null || t == null) { return s == null && t == null; } else if (s.val == t.val) { return equalTree(s.left, t.left) && equalTree(s.right, t.right); } else { return false; } } }
DM ME YOUR FAVORITE VEGETABLE ON INSTAGRAM OR LEAVE IT IN THE COMMENTS BELOW
10% OFF ROOFTOP SLUSHIE: bit.ly/kevinnaughton
instagram: instagram.com/kevinnaughtonjr/
twitter: twitter.com/kevinnaughtonjr
patreon: www.patreon.com/KevinNaughtonJr
merch: teespring.com/stores/kevin-naughton-jrs-store
Potato?
Why cant we solve it using preorder
I'm a visual learner so you drawing out how we should go about solving a problem on the iPad helps. I can really picture it in my mind now. Ty for always improving for content for us =)
Off the top of my head: Traverse both trees and values in two different strings respectively in preorder then Check if t string is substring of s string boom
Pre-order traversal would not identify the tree uniquely. we would need inorder+(preorder/postorder)
Hey Kevin, so glad you're still uploading during the quarantine and I hope you're doing fine. I've been working on leetcode problems and studying your solutions. I was wondering if you could suggest resources to learn traversing graphs and trees, as I feel my data structures & algorithms class did a subpar job in teaching me these fundamentals. Thank you!
Here you go -
th-cam.com/play/PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P.html
Great to have you back. I can't thank you enough. Your videos helped me a lot to land up in a tech job in a fairly reputable Indian startup.
You're really natural at explaining this Kevin! Thank you for all the content you put out. This is amazing!
Thanks Kevin! I'm glad you are uploading videos regularly
thanks for the support!
It's failing for this test case, which must be added recently, could you please check once?
[1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2]
[1,null,1,null,1,null,1,null,1,null,1,2]
See the code carefully, in the else block ita subtree()||subtree. I was writing isSame in place of that
I love popping the problem into search and finding that you made a video on it already. I know I'm in good hands at that point. These are really helpful--thanks and keep it up!
what if we store inorder+(postorder/preorder) traversal of s and t in a string and check if substr(). That would be O(m)+O(N) right?
Hi , I tried the same code and it is failing under one of the test cases of the leetcode ->[1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2]
[1,null,1,null,1,null,1,null,1,null,1,2] . you might want to take a look .
did you find the fix?
I am getting the same but not able to figure it out.
@@indiansoftwareengineer4899 I assume this code worked previously when the test cases were different. But this code is not supposed to work.
He checks first if the root == subRoot and if its not then he checks root.left or root.right. That is all he does, he never checks anything beyond that point, so if the subRoot is equal to something deeper in the root then it wont find it, hence the error you get.
A easy way to complete the solution would be to do a BFS in the Tree first and store it in an ArrayList. Then make a for loop and check for every node in the arraylist that has same value as subRoot.val, on that node try your recusrive method to compare the nodes.
That case:
[1,1]
[1]
Completely broke me and I need a therapist
same bro
Love the new iPad layout ! Keep doin what your doin💯
Using iPad is great for visualizing the algorithm. It is helpful. Keep using it in the future videos. Keep posting more videos. Thank you.
I loved iPad explanations
You are given a two-dimensional matrix with N rows and M columns. Each cell (i, j) of the matrix has some value denoted by Ai,j.
You can do some operations on the matrix (possibly many or zero). In a single operation, you can choose any two adjacent cells and increment the value of each of them by 1. Find the minimum number of operations to make the values of all the cells of the matrix equal. If it's not possible to make all cells equal print -1.
Input
The first line contains two space-separated integers N and M - denoting the size of the matrix.
Each of the next N lines contains M space-separated integers representing the values of the matrix, where the jth integer on ith line denotes the value of cell (i, j) - Ai,j.
please elaborate first base case ,if(s is null) return false. why u r directly returning false . may be t is also null then its true isnt it?
Pre order traversal can solve this, check if traversal of s contains traversal of t. Time and space complexity O(N + M).
it would fail for the second example
bro which one is better in ur opinion Ipad pro or macbook air ?
all I want is a long battery duration and lightweight and portable and powerful ,fast and great Retinadisplay 😊
What I tried to do here is I broke the problem into two parts, the first part would find me the root of the subtree from our original tree, then from that new root I called isSame function and did the sameTrees code but it failed at testcase 158/182, I think it was because due to node values were same so my code's first part would've return me the root node instead
[1,1]
[1]
of its left child.
Actually this can be improved by using a hashset. What you need to do is to serialise every subtree of S (including S itself)and store it in the hashset. Now all you need to do is to serialise T and check whether it exists in the hashset. Time complexity hence becomes O(|S|+|T|) with space complexity of O(|S|*|S|).
Not optimal since it has to look through every possible path.
A more optimal approach would be a preorder traversal comparison at the occurrence of the target node. In this case, the program terminates at first success.
That Ipad explanation was really helpful!!!
I keep overthinking these recursion and tree problems. thank you.
it's of the order O(n^2). Wanted to know of order O(n) solution. Title says amazon coding interview question , definitely they will ask you to optimize it.
Wouldn't it actually be O(nm) n being the original tree and m being the subtree?
Bro search root node in main tree and from there compare two 🎄🌴
I'm surprised that doing an iterative Preorder of both Trees, and then search if one of them is contained in the other is actually faster. But of course it consumes more space.
If we stored the inorder traversal of Tree S as a string and Tree T as a string and see if the patters of T exists within S then we can return true, this would be of time complexity O(M) right?
iPad is awesome Kevin, also you should try with apple pencil you will not be disappointed i promise. Note : you can use quicktime player on Mac to project ipad screen on mac , so u don't have to record separately and also u can explain any concept while writing the code side by side
Double recursion reminds me of double rainbow lol
The same problem is in cracking the coding interview and it says that the space complexity is O(log (n)+ log (m)), but it doesn't tell us why. It was solved the same why as you did, but with slightly different code.
Because it takes log(n) times to look for 1 node in a tree. so when you are at any point of the tree, your call stack is of size of n.
Thanks Kevin! Really happy to see you uploading videos and doing well :) I'm going to have my final interview next week in a faang company, if i get the job i'd love to support your work :)
Cheers!
btw: The iPad use improves a lot the learning process!
Thank you for such awesome video. Very well explained and easy to understand.
Simplicity in explanation is forcing me to like and comment.
Haha anytime!
I am considering an extension of this question. How about if we expect Example 2 to return true? Which means we want to find out if a tree t is a piece of tree s. What would be the algorithm?
Can we bring that complexity down to O(n) ?
There is no fucking way I can come up with this on the spot!
2 recursive functions, one to iterate one tree, other to compare subtree
*Lovely Explanation* I was wondering if having two functions _findNode()_ and _isSame()_ improve the performance by reducing recursion stack calls?
Hi Kevin,
I really like your videos! Thank you!
Although I think you wrong in the space complexity cause in the second function is like you said min(m, n), but in your first recursion you go trow all the tree S so I think the answer is O(m).
If you think I'm wrong, I hope you can help me understand why
Thank you
The recursion stops when any node is null. The tree with less nodes will become null first, so min(m,n)
thanks
Awesome video!! Kevin what's the best way for me to level up my Java skills? I can solve Leetcode medium's in JS but I'm feeling a bit lost when it comes to Java best-practices, even on Leetcode easy's.
Nice explanation sir
amazing explanation Kevin , thanks !
Amazing , please continue
Is it possible that Amazon asks its O(n) version too
haha same doubt here
they've asked in some interviews
Can we do inorder traversal of both and store it and then check for matching subset of elemts
no. two trees can have same inorder traversal but diff structure
Thanks a lot
Hello Kevin, so glad to see your amazing content, can you pleaseeeee make a video series on bottom up (iterative) dynamic programming?
dude you're awesome. What are some resources that you've used to get better at recursion?
Update your Amazon Playlist man!! I solved every one of the questions feeling accomplished just to see "rotting oranges" suggested://
What is time complexity?
Why is one call isSubTree and the other one isSameTree?
whats the time complexity?
After video problem do look easy
Hey Kevin, Why you are not travelling complete s tree , you are just checking for s,s.left,s.right node.
subtree t can need not be only at s,s.right and s.left, it can be anywhere
Thought the same, but then I noticed he used "isSubtree" in the last return statement of "isSubtree" (line 17), which is actually traversing the whole tree "s".
Which monitor do you have on the side?
did you cry before making this video ? haha btw, great video thank you
You prove geeks can be cool too
I liked your Ipad 4 air.
I definitely wanted to buy that.
Hi Kevin, I really enjoy your vids and learn a lot and I strongly believe you give a better explanation of the problems compared to others on internet.
I was wondering if you can help me prepare for my Amazon interview (virtual/phone interview with an engineer) which is scheduled in a week! Kindly let me know. Thanks.
Why wouldn’t you be trying to find the root of the sub-tree first?
When Kevin said space complexity is O(min(m, n)), does he mean the call stack space? Cause I don't see any new data structure created in the code.
hes referring to the recursive stack
Thanks, man!
who in the world will put this in easy
you're a lifesaver man!
A less efficient but more simpler method would be to traverse both the trees individually and append each node's value to a string. That way we'll have two strings for two trees and we can just check if one string is the "substring" of another string.
Thank you Kevin 🤗
you got it! :)
Kevin Naughton Jr. it’s me Surendra 😁
great way to explain keep going :)
I dont get why leetcode thinks this should be False:
[4,null,2]
[3,4,5,null,2,null,2]
Clearly the answer to above should be True?
Coz in the second tree ,node 2 have a child node
bruh... that's a nice Explaination.... Use I pad every fukin time !
this came in my interview ...so pissed
Where did you get your hoodie?
Shrimat Kapoor teespring.com/stores/kevin-naughton-jrs-store
Thank you always ! :D it's so much helpful
Nuri Jeon anytime! :)
iPad is a dope idea!
loving the ipad, btw can you do question 207 course scheduler plz. thanks
In isSame function , if one of s,t is NULL then in isSame function it will give runtime error. I m not satisfied with this solution
Thank for sharing! I guess this approach can also be applied to 617. Merge Two Binary Trees.
Liked the IPad :)
Beautifulll
is java the language you have the most proficiency, experience with? what are your other languages
SubTree method and sameTree method are managed with video editing.. but nice vid though...
like the ipad！
👌👌 For the IPad
I was given this testcase and it failed:
[1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2]
[1,null,1,null,1,null,1,null,1,null,1,2]
output: false, expected: true.
Heres my code. I watched some of the video and had it a little different but using your approach, then i just straight up copied your solution and it still failed... I would like some help as to why this has happened. Thanks for the great content!
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) {
return false;
} else if(equalTree(s,t)) {
return true;
} else {
return equalTree(s.left, t) || equalTree(s.right, t);
}
}
public boolean equalTree(TreeNode s, TreeNode t) {
if (s == null || t == null) {
return s == null && t == null;
} else if (s.val == t.val) {
return equalTree(s.left, t.left) && equalTree(s.right, t.right);
} else {
return false;
}
}
}
In else part you need to call isSubtree function rather than equalTrre
the same code is going to give runtime error on geeksforgeeks,although explanation was very awesome
What is time complexity?