A Medium LC question that is VERY similar to this one (explaining Union-Find): th-cam.com/video/FXWRE67PLL0/w-d-xo.html Looking forward to next month btw - hopefully not a Hard problem every f*cking day xD
9:56 You misspoke here. It's not the green edges that are traversable for both Alice and Bob but the blue one. Leaving the comment so other people don't get confused.
15:58 "we want to increment count by 1 pretty much every time" -- obvs this is hyperbole, but for anyone actually curious you do still need to check the union result of type 3 edges for alice and bob, so if you don't like bitwise OR operator you could do: cnt += max(alice.union(src,dst), bob.union(src,dst)) for same effect, or have your union return True/False, etc
In simple words, we can not increment count by 1 every time, we need to check before we increment, if union on type 3 was a success. Think of a case where current edges were already connected in prev union operation on type 3. ie. {3,1,2}, {3,2,3},{3,1,3} > first 2 will be a success, 3rd will be failed.
Pretty neat solution. Also point to note, it doesnt look like your union find class implements path compression. It only looks like it does union find with rank
@@m.kamalali gotcha, thanks for pointing it out 👍. Once we do path compression should we also update the ranks? Because rank essentially means the max height of its child nodes right? So once we do path compression all heights become one... So doesn't seem like there is any point to rank here... We could very well do path compression in the union method itself and leave out rank all together imo
I understand why we need to choose edges of type 3 first, but do the order type 3 edges is matter? For example we have 10 type 3 edges, we need to figure which type 3 edges to choose first to maximize the number of type 3 edges chosen.
Yes, it will fail for some cases, if any edge doesnt return success for type 3, because may be both nodes are already connected in earlier union operations. so better to check union of type 3 if its success then only increment count else not. you can do it in many ways ie. bitwise or , return true/false and counting.
class Solution: def maxNumEdgesToRemove(self, n: int, e: List[List[int]]) -> int: def h(z): while (n:=u[z])!=z:u[z]=u[n];z=u[z] return z b=[list(range(n+1)),[],[]] for t in range(3): u=b[t]=b[0][:] for v,w in ((v,w)for s,v,w in e if t+s==3): u[v:=h(v)]=(w:=h(w)) u[0]+=(v!=w) if t and u[0]!=n-1:return -1 return len(e)-2*(n-1)+b[0][0]
A Medium LC question that is VERY similar to this one (explaining Union-Find): th-cam.com/video/FXWRE67PLL0/w-d-xo.html
Looking forward to next month btw - hopefully not a Hard problem every f*cking day xD
At least they aren't hard DPs like previously lol. Thanks for the vid
🐐
9:56 You misspoke here. It's not the green edges that are traversable for both Alice and Bob but the blue one. Leaving the comment so other people don't get confused.
15:58 "we want to increment count by 1 pretty much every time" -- obvs this is hyperbole, but for anyone actually curious you do still need to check the union result of type 3 edges for alice and bob, so if you don't like bitwise OR operator you could do:
cnt += max(alice.union(src,dst), bob.union(src,dst)) for same effect, or have your union return True/False, etc
In simple words, we can not increment count by 1 every time, we need to check before we increment, if union on type 3 was a success. Think of a case where current edges were already connected in prev union operation on type 3. ie. {3,1,2}, {3,2,3},{3,1,3} > first 2 will be a success, 3rd will be failed.
Thanks man. I was able to solve the question on my own this time but it wouldn’t have been possible without your content.
you are confused with both green and blue edges throughout the video but no worries i got the point man 👍
I feel you, these union find dailies are brutal, I haven't had to do one in a long while.
Thanks. With these hard tasks I often need your clean explanations.
Neetcode to the rescue, awesome explanation
also works with minimum spanning tree approach
Pretty neat solution. Also point to note, it doesnt look like your union find class implements path compression. It only looks like it does union find with rank
It's done inside find method
Self.par[x]=self.par[self.par[x]]
@@m.kamalali gotcha, thanks for pointing it out 👍.
Once we do path compression should we also update the ranks? Because rank essentially means the max height of its child nodes right? So once we do path compression all heights become one... So doesn't seem like there is any point to rank here...
We could very well do path compression in the union method itself and leave out rank all together imo
please keep uploading hard problems as well. Thank you
Amazing. Thanks for great solution.
I understand why we need to choose edges of type 3 first, but do the order type 3 edges is matter? For example we have 10 type 3 edges, we need to figure which type 3 edges to choose first to maximize the number of type 3 edges chosen.
thanks
missed you
funny how my algorithm teacher doesnt tell us to code but draw the edge but now when i do leetcode it show up...
keep up the good work!
16:09 Solution is not working unless I do bit wise or operation, this does not make any sense. Can anyone explain please ?
Yes, it will fail for some cases, if any edge doesnt return success for type 3, because may be both nodes are already connected in earlier union operations. so better to check union of type 3 if its success then only increment count else not. you can do it in many ways ie. bitwise or , return true/false and counting.
incredible👌
you werent uploading for so many days , everything alright ??
class Solution:
def maxNumEdgesToRemove(self, n: int, e: List[List[int]]) -> int:
def h(z):
while (n:=u[z])!=z:u[z]=u[n];z=u[z]
return z
b=[list(range(n+1)),[],[]]
for t in range(3):
u=b[t]=b[0][:]
for v,w in ((v,w)for s,v,w in e if t+s==3):
u[v:=h(v)]=(w:=h(w))
u[0]+=(v!=w)
if t and u[0]!=n-1:return -1
return len(e)-2*(n-1)+b[0][0]
please code like you usually do, dont write the code before, that way we are more involved
Neetcode can you explain Checking Existence of Edge Length Limited Paths problem 🥹, it's 1697 on leetcode