Union Find in 5 minutes — Data Structures & Algorithms

This video covers one of the most popular data structures and algorithms topic "Union Find". This is an instruction showing how to run Union-Find on a graph, with examples and code. Union Find and Disjoint Set are not as difficult as we think! 😊

#graph #data_structures #algorithms #faang #Union-find #disjoint set #data-structures #recursion #leetcode #interview #algo #disjoint-sets #disjoint sets

[potatocoders]

Comment down any questions below! Please give it a like and subscribe to support our channel.

Cheers,
Potato Coders 🙂

[robirahman]

You forgot to mention you have to union the shorter tree into the longer tree! Otherwise the trees in a set of n elements can be up to n elements long (just a straight chain, instead of branching) and you don't get log(n) complexity.

[richtigmann]

This was actually insanely helpful in understanding the concept. Thanks!

[luisgualpa]

This video has saved me many hours of my life. Thank you for this.

[BobTheScience]

To optimize it, the find function should set the parent of it's parent to find(x). (This will probably help a lot)
function find(x):
if Parent[x] != x: parent[x] = find(parent[x])
return parent[x]

If I'm wrong please tell me.

[jakubucinski]

There is a little technicality, that when you do find(x), you want to do path compression, by connecting each vertex on the corresponding branch (the branch where x is) to the root. This results in subsequent find operations being cheaper (and you only double your cost one time).

[Coffeycup]

Awesome video, thank you! Question though; isn't the find operation O(n) time? I'm reading around that it isn't until you use 'Union By Rank' that it becomes O(log(n)).

[pieterjanvandecasteele]

I was always stuck with the implementation of UF, now I finally got it, thanks!

[tenminuteamateurhour]

Correction, this does not run in O(logn), but in O(n). To get O(logn) optimization, you need to use union by rank or by size.

[Anirozannay]

You explained it so well! Thank you for your video!

[jashmerchant]

Solved my hours long quandary in 5 minutes. Thank you!

[danielwang]

Really clear and concise explanation. This video helped a ton.

[Dev_God]

Thanks for sharing! It's very clearly and efficiently explained!

[UsamaAziz-lbky]

Great video, worth adding path compression as well.

[송예은-hb]

So practical and helpful video=) Thanks

[nghiapham]

It so simple and straight forward. Thanks you so much

[chrisdahms]

Bro this topic is confusing AF, but at least this vid makes it somewhat understandable

[kmishy]

Best illustration... please provide more content

[jeresher]

Best video I've found on UF. Thank you!

[Shasol]

How do you select the representative? I struggle to understand that part of it.