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

Подписаться 156 тыс.

Просмотров 10 тыс.

50% 1

🚀 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

Опубликовано:

30 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 31

@NeetCodeIO Год назад

A Medium LC question that is VERY similar to this one (explaining Union-Find): ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-FXWRE67PLL0.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 4 месяца назад

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 29 дней назад

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

@sharathkumar8338 Год назад

please keep uploading hard problems as well. Thank you

@StellasAdi18 Год назад

Amazing. Thanks for great solution.

@EasterBunnyGaming 29 дней назад

also works with minimum spanning tree approach

@FlickeringFly Год назад

keep up the good work!

@siddheshb.kukade4685 Год назад

thanks

@lvisbl__ 23 дня назад

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.

@OneDerscoreOneder Год назад

missed you

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

@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 29 дней назад

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.

@GameFlife Год назад

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

@BurhanAijaz Год назад

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

@BurhanAijaz Год назад

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

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