Forgot to mention, time complexity is O(E^2), where E is number of edges since we have nested loops iterating over the edges. The union find operations are practically O(1).
Thank you so much sir for adding this problem in NeetCode All List 🙏 Sir could you please also add last 5 daily problems solved on this channel to the NeetCode All List Rest of all problems are in the List .
In the path compression for the iterative version of find() (of UnionFind), you set parent of each node to be its grand parent as you move up. The recursive version would have set this to the actual root (during unwinding), making it better, right?
If from our initial MST we remove anu edge and put another - it will anyways be worse than original one, because we already in the very beggining used all minimal weights. No? Could not understand it
I think the implementation is very complex just like the one in Leetcode official Solution. It could be simplified to a great extent. Below can help : class UnionFind { public: vector parent; UnionFind(int n){ parent.resize(n); for(int i=0;i
From what I understood a critical edge is one that is vital to obtain the most minimum cost spanning tree. If the edge that is going to be removed causes the cost of the spanning tree to increase then it is a critical edge. So considering the word Critical we can say that this edge is vital to achieve the most minimum cost spanning tree. Whereas when we talk about Pseudo Critical , pseudo means false i.e we are looking for false critical edges meaning we are looking for edges that aren't going cause the cost of the spanning tree to dip, meaning whether or not that edge is there isn't going to affect the cost of the spanning tree. We will always get the minimum cost of the spanning tree if pseudo edges are removed because they are the edges that do not affect the spanning tree from achieving the most minimum possible cost.
@@DJSTEVE42 very nice explanation I was about to most the explanation. In simple terms critical edge removal will result in weight increase larger than minimum spanning tree cost. Whereas removal of pseudo critical node will not cause the weight to increase or dip for mst.
![ประสบการณ์ จ้าง Developer ที่ผมจะไม่มีวันลืม [ภาค1]](http://i.ytimg.com/vi/bzivN4KDg-k/mqdefault.jpg)
Forgot to mention, time complexity is O(E^2), where E is number of edges since we have nested loops iterating over the edges.
The union find operations are practically O(1).
Thank you so much sir for adding this problem in NeetCode All List 🙏
Sir could you please also add last 5 daily problems solved on this channel to the NeetCode All List
Rest of all problems are in the List .
Sir please also add these problems in NeetCode All List
This problem is a really tough one... Great explanation from you sir, thank you very much !
You are awesome, this question broke my streak ...
In the path compression for the iterative version of find() (of UnionFind), you set parent of each node to be its grand parent as you move up. The recursive version would have set this to the actual root (during unwinding), making it better, right?
NeetCode === NeatCode 👍😀
If from our initial MST we remove anu edge and put another - it will anyways be worse than original one, because we already in the very beggining used all minimal weights. No? Could not understand it
I think the implementation is very complex just like the one in Leetcode official Solution.
It could be simplified to a great extent. Below can help :
class UnionFind {
public:
vector parent;
UnionFind(int n){
parent.resize(n);
for(int i=0;i
Hey! I did similar implementation as you except I used a[2]
Thanks for the daily
This is a great explanation. Thanks NeetCode ! 🌟
Great explanation as always. Thank you
@NeetCodeIO can you tell if there is inplace solution for lastIdx 2161? maybe some variation of dutch flag algo?
Time complexity ?
Why we need to mention self in line 13. In that line he write self.find() in the class
that is how python classes are used. self says that your accessing the function inside the class. Much like "this" in java
Bro you should have taken a proper graph to explain,
Using 3 nodes not able to identify what is happening in explanation
I still don’t understand what pseudo critical means. You rushed it a bit.
From what I understood a critical edge is one that is vital to obtain the most minimum cost spanning tree. If the edge that is going to be removed causes the cost of the spanning tree to increase then it is a critical edge. So considering the word Critical we can say that this edge is vital to achieve the most minimum cost spanning tree. Whereas when we talk about Pseudo Critical , pseudo means false i.e we are looking for false critical edges meaning we are looking for edges that aren't going cause the cost of the spanning tree to dip, meaning whether or not that edge is there isn't going to affect the cost of the spanning tree. We will always get the minimum cost of the spanning tree if pseudo edges are removed because they are the edges that do not affect the spanning tree from achieving the most minimum possible cost.
@@DJSTEVE42 very nice explanation I was about to most the explanation. In simple terms critical edge removal will result in weight increase larger than minimum spanning tree cost. Whereas removal of pseudo critical node will not cause the weight to increase or dip for mst.