Union Find Code

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

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

50% 1

Related Videos:
Union find intro: • Union Find Introduction
Union find kruskal's algorithm: • Union Find Kruskal's A...
Union find union and find: • Union Find - Union and...
Union find path compression: • Union Find Path Compre...
Union find code: • Union Find Code
Data Structures Source Code:
github.com/wil...
My website: www.williamfise... ===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

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

10 сен 2024

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист

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

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

@relishxylitol 7 лет назад

William, this is very helpful. You are such a great instructor. :)

@hamoodhabibi7026 Год назад

the bijection part of converting it to numbers based made everything so much more simpler thank u

@anuchan-l7y 2 месяца назад

as we do more and more union-find operations, the path gets even more compressed making it efficient . such a wonderful concept .

@frostbite585 6 лет назад

Will: really enjoy the videos, hope you'll continue to make them. I understood the concept of Kruskal's fine but sometimes its a challenge to translate algorithms to code. I appreciate the help.

@sannge6471 4 года назад

very well explained. I looked at a bunch of union find explanation videos on youtube, and couldnt understand it until I found yours.

@klarareichard6222 3 года назад

Great explanation! Could you also make a video about explaining the armotized runtime? That would be amazing

@Hateusernamearentu 4 года назад

Finally understood compression algorithm. Your way of naming is very helpful. Thanks

@sgdfdsgs 2 года назад

William, thank you so much for the videos, you do an amazing job explaining both the algorithms / data structures and how to implement them.

@AbishekTAmeb Год назад

Clear, conceptual and intutive you are a legend man!

@californiaflying6637 Год назад

Thanks for demystifying the UF data structure!

@soumyaporel6955 4 года назад

Thanks a lot William. I cant express how much grateful I am. U are awesome!

@tomislavzoricic5656 3 года назад

iterative path compression is much easier to grasp and remember, thanks!

@AurelianoShowsTheWorld Год назад

Thank you for your series of vides, it's very helpful and easy to understand!

@darthvader_ 3 года назад

Ignorance is not bliss ~Suzy Kassem Thanks for the series

@MaciejJankowskiPL 2 года назад

Nice code. Very good explanation. You are good teacher. I understood. It's helpful. Thank you.

@shobankumar6418 3 года назад

Hi William, i was following your DS video and could able to understand the progress of each Data structure as well as their ADT. Now i was learning with Union Find, Interesting thing is that i started with java background and now working on C#. Still i could able to replicate the same code functionality in C# which u have written in java. Thanks for the works. Really helpful in understanding.

@rob6129 4 года назад

Amazingly simple datastructure with a nice application, also great and clear code

@KananMammadli 3 года назад

I would slightly modify path compression to avoid unnecessary iteration. Suggestion described in github.

@FrazerKirkman Год назад

I love your classes.

@ArielVolovik 2 года назад

This is incredibly clear, thanks so much for creating these videos!

@saltyreese1398 6 лет назад

Quite fabulous implementation william

@MrZloopz 5 лет назад

Robert says "The 05:32 remark on smaller to larger tree by convention is not correct, it is by necessity to get the logarithmic factor in log*(n) " , consider.

@JavierArtiles 5 лет назад

Excellent explanation and clean code! Thank you for sharing.

@kirtanitaliya7631 4 года назад

absolutely loved it. Very neat and clean. Keep up the divine work.

@oybekkhakimjanov5944 3 года назад

William, thank you very much!

@linshengred Год назад

thank you!!! you are a true life saver!

@adeyemi9860 2 года назад

Is there a reason why we don't reset the submerged size to 0, in the unify function? i.e. sz[root1] = 0, after we add its component size to sz[root2]? Looks like a necessary cleanup to satisfy some invariant given root1 has become a part of root2's component

@WilliamFiset-videos 2 года назад

Yes, that would be good to add for consistency. However, since you'll never directly access sz[root1], it's not really an issue if that's not cleaned up. In the component size method you would always access the size as sz[find(root1)] which is really sz[root2] -- just make sure sz is private so you don't accidentally access it directly.

@WilliamFiset-videos 2 года назад

FYI, the latest code on Github does set sz[root1] = 0 when a union happens, see: github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/datastructures/unionfind/UnionFind.java

@BlauerTeeLp 4 года назад

You seem to be doing union by size, in my algorithms class we do union by rank. Have these optimizations any different implications?

@Lan-so5gv 2 года назад

Excellent

@madanrajvenkatesan518 4 года назад

Very Nice Explanation, thanks again !!!

@juneoh626 5 лет назад

thank you so much for sharing your knowledge!

@a55tech 2 года назад

Can u link to some LC problems about this, the tagged ones there are not clear. Would just like to see the most directly related, simple problems that have you use this.

@DaudZaidi 3 года назад

William, why can't we do path compression as we are unifying instead of finding ?

@andrewbarros5521 Год назад

William, can you make video of a percolation implementation?

@esophagoose 2 года назад

You’re the 🐐 fr

@alexpeak1008 Год назад

This is amazing, thank you very much. I have a question, how did you learn about data structures and algorithms, and what books did you base your knowledge on? (if any)

@sayannag268 4 года назад

Hi William great video.Really liked it.I have a small doubt should not unify method have a check at the start numComponents >0

@EugeniyNizhinskiy 3 года назад

is this path compression depend on the order of the edges? e.g. A->B B->C C->D D->E vs D->E C->D B->C A->B

@kirkwatson2234 3 года назад

You mentioned there is a more efficient way to merge the components using the unify function. How would you do this?

@imbesrs 2 года назад

Really late comment, but in this cose you have the private int[] id; There should be a hash table that links the id to the actual nodes right?

@DeepakVadgama 5 лет назад

You have too few subscribers for the value of your videos. Please keep posting regularly, I am sure they will increase quick.

@Snehilw 2 года назад

What is the time and space complexity of this solution?

@divyeshgaur 6 лет назад

helpful video! thanks. now find the number of island problem looks easier. :)

@midhurammanoj931 2 года назад

Thanks!

@MrOsumGuy 6 лет назад

You are awesome. Thank you so much.

@dhruvdre2620 2 года назад

I was unable to understand the code of "Find function" could you explain in a basic text if possible, rest all your videos and sessions are amazing!!!!

@rahulsriram6295 4 года назад

Why don't we do a lazy update on source compression? Like, we update the parent node of a node only when find is called.

@patrickaero1767 4 года назад

Hello William, I just wanted to find out "why there no main class?" and "do we hard code the values or just pick them at random?". I still need more clarification wih the questions stated.

@michaeljiang1002 4 года назад

Hey will, in your github repo, you don't have a way to break ties if the sz is the same. Also, i don't think the sz is suppose to go up when the sz of one is smaller than the other, the sz should only go up by 1 if they have the same sz

@lolololololololol11 6 лет назад

Very good videos, but can you do one on the Tarjan Lowest Common Ancestor algorithm? Still struggling to understand applying the union-find data structure to it.

@frostbite585 6 лет назад

Will: does the 'connected' boolean method check if a specified edge forms a cycle? I needed a method that will do that so I know whether or not to add it to the final MST output. Thanks so much.

@WilliamFiset-videos 6 лет назад

The input graph is assumed to be an undirected graph with bidirectional edges so checking if two nodes are connected will not tell you if they're in a cycle. For undirected graphs we are usually only interested in whether or not nodes are part of different components. If you have a graph with directed edges I would look into Tarjans algorithm on strongly connected components I have a video you can watch.

@revanthmadasu244 4 года назад

what happens if the path compression logic is applied in the union method instead of find method @WilliamFiset ?

@WilliamFiset-videos 4 года назад

The union method calls the find method, so path compression is happening in both instances.

@toshinakaokubo1111 4 года назад

you are the best

@oasdfe1691 5 лет назад

in the time of cryptocurrencies and clustering, you are saving us valuable time.

@eddiej5974 5 лет назад

William, thanks for this video and all the others. Question though, what if you don't know the number of components or regions ahead of time?

@WilliamFiset-videos 4 года назад

This is a really good question. You can efficiently add additional elements by growing the internal storage arrays, but I don't think you can remove elements efficiently without a high overhead cost.

@pictassistant1591 5 лет назад

Bro your website doesn't seem to exist! It would be great to have it!

@mohammedjulfikaralimahbub3501 6 лет назад

I have understand the concept quite clearly but having problem with understanding the code. What shall I do to understand it better. Any tips?

@WilliamFiset-videos 6 лет назад

What in particular? Maybe I can clarify something.

@mohammedjulfikaralimahbub3501 6 лет назад

The whole coding concept is not getting into my head normally. I made the union find algorithm but without the compressing method which is actually very non-efficient so I want to know the compression algorithm. Here is my code: pasteboard.co/HD8W24y.png

@RAHULKUMAR-ip4ds 7 лет назад

Is this algorithm provides union-find operations in minimum time complexity?

@WilliamFiset-videos 7 лет назад

RAHUL KUMAR Indeed!

@RAHULKUMAR-ip4ds 7 лет назад

that's great,thanks

@MaherTurifi 7 лет назад

Hi William, it is clear and very helpful. I'm trying to use this for finding connected components in large graph, is it the best option, and what is the time complexity in that case, thanks

@WilliamFiset-videos 7 лет назад

The union find is appropriate for such a task, but I would recommend a DFS to find connected components on an undirected graph.

@Lan-so5gv 2 года назад

I think in the case of leet code 684. Redundant Connection, the best solution is definitely Union Find.

@_suri_99 3 года назад

Hey William, Amazing video! I have one question - How would Kruskal's Algo work with Path Compress? Aren't we change the actual path of the graph because of the compress?

@damanpreetsinghpunjabi 3 года назад

You are not changing the graph at all. You are using bijection and assigning nodes to integers and then sending those into unionfind data structure. Graph remains as it is.

@erggish 7 лет назад

One thing that is unclear to me throughout this section: you began the section with Kruskal's algo, which looked like finding the optimal path to merge the nodes of your graph... is this a better approach than tree searching algorithms?

@WilliamFiset-videos 7 лет назад

Hey Chris, Kruskal's algorithm is one of many Minimum Spanning Tree (MST) algorithms. It runs in a time complexity of O(ElogE) (where E is the number of edges) which can be good for sparse graphs. Other minimum spanning tree algorithms like Prims MST runs in O(ElogV) with a binary heap (where V is the number of vertices) which is theoretically faster since V ≤ E in graphs we care about. Personally, I use both in competitive programming depending on the situation.

@erggish 7 лет назад

Thanks for the input. I also wanted to ask, how far do you plan these series to go? [if you can and want to answer]

@WilliamFiset-videos 7 лет назад

Hard to say, but ideally far enough to cover two university courses worth of material and more depending on how motivated I am to explain some advanced data structures.