LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]

Рет қаралды 12,595

Күн бұрын

Пікірлер: 52

@veluchamy-zt7gd 7 ай бұрын

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 :)

@hemmy123 6 ай бұрын

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!

@biavechiato 21 күн бұрын

This makes so much sense

@eddiej204 2 жыл бұрын

The solution sounds like fast slow pointers technique and it is brilliant. Thanks a lot, ser.

@crackfaang 2 жыл бұрын

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

@steveroberts1045 Ай бұрын

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.

@amvi659 Ай бұрын

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!

@MnumzanaMoyo 18 күн бұрын

@@amvi659 hmm makes sense! thought it was log(n) in the worst case too!

@cheekyjay7800 2 жыл бұрын

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!

@crackfaang 2 жыл бұрын

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!

@rdnetala Ай бұрын

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

@sami9323 Ай бұрын

in this case, "n" (for the runtime complexity) is the height of the tree, not the number of nodes, correct?

@louie0187 8 ай бұрын

Basically same "ah-ha" trick as Leetcode 160 -- Intersection of Two Linked Lists

@crackfaang 8 ай бұрын

Yup!

@bhaveshvarma4313 2 жыл бұрын

Thanks man, Now Understand similar question of finding intersection of two linked list.

@rsKayiira 2 жыл бұрын

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

@Ryan-g7h 2 ай бұрын

this channel is real af,

@zhengyuzhou2288 7 ай бұрын

Thank you, that explanation is very clear.

@MrDoubleWhy 9 ай бұрын

Amazing explanation! Thank you!

@Rutik9999 3 күн бұрын

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

@Mo.Abufouda 2 жыл бұрын

This channel is underrated! Great work. Keep the good work! :)

@crackfaang 2 жыл бұрын

Thank you for the kind words! I'll keep uploading, make sure you're subscribed so you don't miss future uploads :)

@ebenezeracquah478 Жыл бұрын

Highly appreciated! Bind blowing solution

@JRivero 5 ай бұрын

So clear. Thank you very much

@АльбусДамблодр 4 ай бұрын

Thanks, bro, really good explanation, love it!

@sunwoodad 4 ай бұрын

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.

@usrenaem 7 ай бұрын

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.

@crackfaang 7 ай бұрын

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

@markvaldez8602 4 ай бұрын

Awesome! Thank you!

@swapnanilgupta3046 4 ай бұрын

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?

@preityhansaa9150 2 жыл бұрын

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

@crackfaang 2 жыл бұрын

No problem my friend. If you subscribe I will make these two videos, just for you ;)

@preityhansaa9150 2 жыл бұрын

@@crackfaang subscribed!

@MinhNguyen-lz1pg 2 жыл бұрын

Well done mate! Appreciate the thoughtful explanation!

@crackfaang 2 жыл бұрын

Thanks and make sure to subscribe!

@fallencheeto4762 8 ай бұрын

No way someone figures this out, but it makes so much sense lol

@preityhansaa9150 2 жыл бұрын

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

@jacquesasinyo5560 3 ай бұрын

Thanks. bro next time use different colors for the drawing.

@sarayarmohammadi3376 5 ай бұрын

Thank you

@whiteboycarl1234 12 күн бұрын

This is same intuition as slow fast pointers

@shraddhabarke1750 9 ай бұрын

amazing work!! :)

@adiesha_ 8 ай бұрын

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)?

@Krankschwester 6 ай бұрын

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.