Union Find Data Structure - Number of Connected Components in an Undirected Graph (LeetCode)

►Union Find Video - https://www.youtube.com/watch?v=K5gYn7qL3lE
►Support me on Patreon: https://www.patreon.com/michaelmuinos
Join the Discord channel by becoming a supporter on my Patreon!
In this Discord channel, you will be able to...
1. Contact me directly for interview prep advice, tech questions, project ideas, etc.
2. Discuss interview experiences with other members
3. Discuss technical questions with other members
4. Find mock interview partners & more!

00:00 - intro
00:28 - description
00:42 - Full example walk through
08:03 - Code walk through
13:33 - Time / Space complexity walk through

Number of connected components in an undirected graph is a popular LeetCode question asked at Amazon and Facebook. This graph problem can be solved with Breadth-First Search (BFS), Depth-First Search (DFS), or Union Find. Union Find is a popular data structure for tracking a set of elements in non-overlapping disjoint subsets.

To solve this problem, we must first initialize a 1D array of the size of the number of nodes we have in our graph. Using this array, we are going to track the parents of our subsets. We loop over all edges we are given in the form of an array and perform a merge on each edge. By the end of iterating over our edges, we will have successfully merged all our subsets. Now, we just need to count how many subsets we have.

We count our subsets by looping over our array and tracking down each parent for each node. When we find the parent, we add it inside of a set. By the end of iterating over our array, we will have found all parents which map to each unique subset. Also, we utilize path compression to smooth our connections to our parents for each node.

Using path compression, our time complexity is O(N+M*log(N)). If we did not use path compression, our time complexity would be closer to O(N*M), which is not great. An additional optimization we could do is "Union by Rank" in which our time complexity would become O(N+M*amortized log(N)) where amortized log(N) is essentially constant, thus O(N+M).

Our space complexity is going to be O(N) where N is the number of nodes we have in our graph. We must create a 1D array which is of the size of the number of nodes we have.

►Follow me on Twitter: https://twitter.com/MichaelMuinos
►Follow me on Github: https://github.com/MichaelMuinos

----------------------------------------------------
Hot Coffee by Ghostrifter Official
https://soundcloud.com/ghostrifter-of...
Creative Commons — Attribution-ShareAlike 3.0 Unported — CC BY-SA 3.0
Free Download / Stream: http://bit.ly/2CMqiz0
Music promoted by Audio Library https://youtu.be/Y30VQPGtxOs

Видео Union Find Data Structure - Number of Connected Components in an Undirected Graph (LeetCode) канала Michael Muinos