Remove Max Number of Edges to Keep Graph Fully Traversable - Leetcode 1579 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Solving Leetcode 1579 - Remove Max Number of Edges to Keep Graph Fully Traversable, todays daily leetcode problem on April 29.
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/remove-...
0:00 - Read the problem
2:00 - Drawing Explanation
13:00 - Coding Explanation
leetcode 1579
#neetcode #leetcode #python

[@NeetCodeIO]

A Medium LC question that is VERY similar to this one (explaining Union-Find): ua-cam.com/video/FXWRE67PLL0/v-deo.html
Looking forward to next month btw - hopefully not a Hard problem every f*cking day xD

[@uptwist2260]

At least they aren't hard DPs like previously lol. Thanks for the vid

[@lincolnabraham4695]

🐐

[@aadil4236]

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.

[@def__init]

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

[@nirmalgurjar8181]

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.

[@aniketmahangare8333]

Thanks man. I was able to solve the question on my own this time but it wouldn’t have been possible without your content.

[@hemanth052]

you are confused with both green and blue edges throughout the video but no worries i got the point man 👍

[@ouchlock]

Thanks. With these hard tasks I often need your clean explanations.

[@YouTube_Staff]

I feel you, these union find dailies are brutal, I haven't had to do one in a long while.

[@krateskim4169]

Neetcode to the rescue, awesome explanation

[@StellasAdi18]

Amazing. Thanks for great solution.

[@EasterBunnyGaming]

also works with minimum spanning tree approach

[@sharathkumar8338]

please keep uploading hard problems as well. Thank you

[@FlickeringFly]

keep up the good work!

[@OneDerscoreOneder]

missed you

[@siddheshb.kukade4685]

thanks

[@parashararamesh4252]

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]

It's done inside find method
Self.par[x]=self.par[self.par[x]]

[@parashararamesh4252]

​@@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

[@israaezzat2353]

incredible👌

[@lvisbl__]

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.

[@GameFlife]

funny how my algorithm teacher doesnt tell us to code but draw the edge but now when i do leetcode it show up...

[@Rancha51]

16:09 Solution is not working unless I do bit wise or operation, this does not make any sense. Can anyone explain please ?

[@nirmalgurjar8181]

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.

[@BurhanAijaz]

you werent uploading for so many days , everything alright ??

[@qulinxao]

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]

[@BurhanAijaz]

please code like you usually do, dont write the code before, that way we are more involved

[@hypermeero4782]

Neetcode can you explain Checking Existence of Edge Length Limited Paths problem 🥹, it's 1697 on leetcode