Man, honestly it is one of the underrated channel. Your explanation is crystal clear, easy to understand. I had difficulty in understanding complex problem's solutions, but your videos really helped me. Thanks a lot :)
The two pointer approach took me a while to understand but I think this rephrasing might help a few people. As mentioned in the video, P_copy takes 3 steps and Q_copy takes 2 steps. This results in a difference of 1 step which is not what we want. What we need to do is essentially make them do the same amount of work so we arrive at the same node. What we can do is combine them, so P_copy and Q_copy do the same amount of work So if we do the 'reset' as mentioned in the video: P_Copy does 3 + 2 steps and Q_Copy does 2 + 3 steps. This results in the difference being 0 so no matter where they are in the tree they will always end up at the same place!
Brilliant explanation! I got quite confused when I was browsing through the discussion sessions and saw these 5 lines of magic Lol... but your video just made it so clear!
This is such an excellent solution. I had to watch it twice though because it wasn't clear you would be swapping the pointers so I was wondering but once I figured that out I was like wow. One other thing is maybe calling them q_ptr and p_ptr would have been better and its odd that the examples require us to return values yet we return nodes
I believe the time complexity of the first solution is actually 2log(N). 2N indicates you would traverse every node when you are only traversing at most log(N) nodes for each given node.
Nope. It's actually 2*O(h) where h=height of the tree. In the best case, the height of the tree would be log(n), i.e., when it is balanced. In the worst case, it would be N which is when the tree is highly skewed. Hope that helps!
If runner A has track of size E and runner B has track of size 2E where E= 1 edge distance, then they both will meet at time T = 2. When the tracks distance aren't divisible by each other for example let's say A has 7E and B has 8E, in this case the time taken will be LCM(8,7) = 56. So at T = 56 they both will meet. This is not an O(H) solution but rather O(H) ^ 2
how about this solution- measure depths , the pointer which is at lower depth will be moved up until the depths are same, and then move p and q simultaneously to and retunr when p == q
Everything is amazing in this video! With your explanation the second solution clicks pretty easily. But what's IQ one should have to be able to solve it at an interview, within 15-20 minutes and without seeing the solution before, it's probably around 160.
You don't need a high IQ lol. You just need to have seen the question before and basically memorized the solution. Just the nature of the game unfortunately
You said the time complexity of naive solution is O(2N), but I just think it's O(N). Even the traverse is twice which is by p and also by q, total sum of them won't be greater than N.
Great explanation. The two pointer solution is exactly similar to Intersection of two linked lists problem. In an interview, would we be expected to come up with such a solution or will the set solution suffice?
This is good! Thanks for the post. can you post a variation of this for other 2 LCA problems the other ones doesnt have reference to its parent 1644 1676
alternative naive solution: class Solution: def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node': seen = set() while p: seen.add(p) p = p.parent
question: if a node is LCA of itself (descendant) meaning it is the parent of itself so do we have to add the same node as parent of itself instead of Null
I am hard time understand why the last solution is linear time. Suppose we have a tree with one left branch of length n-1 and one right branch of length n. Then in order to level the paths you need to run the loop n times, and path length is n. Shouldn't this be O(n^2)?
The loop wouldn't run N times, but abs(depth of p - depth of q). I do agree that this solution doesn't seem very good. Imagine you have the same example you mentioned but one node is at depth 1e4, the other one at 1e6. You would need to repeat this loop abs(1e4 - 1e6) times, which is awful.
![DOT PRODUCT OF TWO SPARSE VECTORS - 3 SOLUTIONS EXPLAINED [PYTHON]](http://i.ytimg.com/vi/sQNN4xKC1mA/mqdefault.jpg)
![Kth LARGEST ELEMENT IN AN ARRAY - SOLUTION EXPLAINED [PYTHON]](/img/n.gif)
Man, honestly it is one of the underrated channel. Your explanation is crystal clear, easy to understand. I had difficulty in understanding complex problem's solutions, but your videos really helped me. Thanks a lot :)
The two pointer approach took me a while to understand but I think this rephrasing might help a few people. As mentioned in the video, P_copy takes 3 steps and Q_copy takes 2 steps. This results in a difference of 1 step which is not what we want. What we need to do is essentially make them do the same amount of work so we arrive at the same node. What we can do is combine them, so P_copy and Q_copy do the same amount of work
So if we do the 'reset' as mentioned in the video:
P_Copy does 3 + 2 steps and
Q_Copy does 2 + 3 steps.
This results in the difference being 0 so no matter where they are in the tree they will always end up at the same place!
This makes so much sense
The solution sounds like fast slow pointers technique and it is brilliant. Thanks a lot, ser.
Yea it’s super cool. Though a bit hard to come up with if you haven’t seen it before. My mind was blown when I saw the solution for the first time
Brilliant explanation! I got quite confused when I was browsing through the discussion sessions and saw these 5 lines of magic Lol... but your video just made it so clear!
Thanks for the kind words and glad you found value from the video explanation. Make sure to subscribe so you don’t miss future videos!
This channel is underrated!
Great work. Keep the good work! :)
Thank you for the kind words! I'll keep uploading, make sure you're subscribed so you don't miss future uploads :)
in this case, "n" (for the runtime complexity) is the height of the tree, not the number of nodes, correct?
This is such an excellent solution. I had to watch it twice though because it wasn't clear you would be swapping the pointers so I was wondering but once I figured that out I was like wow. One other thing is maybe calling them q_ptr and p_ptr would have been better and its odd that the examples require us to return values yet we return nodes
I believe the time complexity of the first solution is actually 2log(N). 2N indicates you would traverse every node when you are only traversing at most log(N) nodes for each given node.
Nope. It's actually 2*O(h) where h=height of the tree. In the best case, the height of the tree would be log(n), i.e., when it is balanced. In the worst case, it would be N which is when the tree is highly skewed. Hope that helps!
@@amvi659 hmm makes sense! thought it was log(n) in the worst case too!
If runner A has track of size E and runner B has track of size 2E where E= 1 edge distance, then they both will meet at time T = 2.
When the tracks distance aren't divisible by each other for example let's say A has 7E and B has 8E, in this case the time taken will be LCM(8,7) = 56. So at T = 56 they both will meet. This is not an O(H) solution but rather O(H) ^ 2
Thanks man, Now Understand similar question of finding intersection of two linked list.
how about this solution-
measure depths , the pointer which is at lower depth will be moved up until the depths are same, and then move p and q simultaneously to and retunr when p == q
Basically same "ah-ha" trick as Leetcode 160 -- Intersection of Two Linked Lists
Yup!
Thank you, that explanation is very clear.
Amazing explanation! Thank you!
Highly appreciated! Bind blowing solution
Thanks, bro, really good explanation, love it!
this channel is real af,
Everything is amazing in this video! With your explanation the second solution clicks pretty easily. But what's IQ one should have to be able to solve it at an interview, within 15-20 minutes and without seeing the solution before, it's probably around 160.
You don't need a high IQ lol. You just need to have seen the question before and basically memorized the solution. Just the nature of the game unfortunately
You said the time complexity of naive solution is O(2N), but I just think it's O(N). Even the traverse is twice which is by p and also by q, total sum of them won't be greater than N.
Well done mate! Appreciate the thoughtful explanation!
Thanks and make sure to subscribe!
So clear. Thank you very much
Great explanation. The two pointer solution is exactly similar to Intersection of two linked lists problem. In an interview, would we be expected to come up with such a solution or will the set solution suffice?
This is good! Thanks for the post. can you post a variation of this for other 2 LCA problems the other ones doesnt have reference to its parent 1644 1676
No problem my friend. If you subscribe I will make these two videos, just for you ;)
@@crackfaang subscribed!
alternative naive solution:
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
seen = set()
while p:
seen.add(p)
p = p.parent
while q not in seen:
q = q.parent
return q
question: if a node is LCA of itself (descendant) meaning it is the parent of itself so do we have to add the same node as parent of itself instead of Null
Awesome! Thank you!
No way someone figures this out, but it makes so much sense lol
At 3:39, shouldn't the time complexity be 2*log(n) instead of 2N?
We're only looking at the height of the tree in each case
It's not a balanced tree, as far as I understand
@@adiesha_ yeah, you're right. we could get a 'linked list' in the worst case
I am hard time understand why the last solution is linear time. Suppose we have a tree with one left branch of length n-1 and one right branch of length n. Then in order to level the paths you need to run the loop n times, and path length is n. Shouldn't this be O(n^2)?
The loop wouldn't run N times, but abs(depth of p - depth of q). I do agree that this solution doesn't seem very good. Imagine you have the same example you mentioned but one node is at depth 1e4, the other one at 1e6. You would need to repeat this loop abs(1e4 - 1e6) times, which is awful.
amazing work!! :)
Thank you
Thanks. bro next time use different colors for the drawing.
is it |b-a| = |a-b|?
Love from India
Thank you for your support! Make sure to subscribe so you don’t miss future videos
thanks
This is same intuition as slow fast pointers
Tortoise hare strikes again
You need to work on your rationale. Yes you reach the answer but it's not clear why.