Be insensitive, and keep a lifelong growth mindset.

0%

## 1. Union Find Definition

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. It supports two useful operations:

• Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its “representative”; by comparing the result of two Find operations, one can determine whether two elements are in the same subset.
• Union: Join two subsets into a single subset.

## 2. Union Find Implementation

### 2. 1. Quick-find apporach

Time Complexity:

• Find: O(1)
• Unite: O(N)

Quick-find algorithm is too slow, it may take ~MN steps to process M union commands on N objects.

### 2.2. Quick-union approach

Quick-find defect

• Union too expensive (N steps)
• Trees are flat, but too expensive to keep then flat

Quick-union defect

• Trees can get tall
• Find too expensive (could be N steps)
• Need to do find to do union

Quick-union is also too slow

### 2.3. Weighted quick-union with path compression

Improvement 1: Weighting

• Modify quick-union to avoid tall trees.
• Keep track of size of each component.
• Balance by linking small tree below larget one.

Analysis:

• Find: takes time proportional to depth of p and q.
• Union: takes constant time, given roots.
• Fact: depth is at most lg N. [needs proof, remember it here.]

Improvement 2: Path compression

• Just after computing the root of i, set the id of each examined node to root(i).

## 3. Union Find Problems

### 3.1. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Example 2:

Solution 1: Depth First Search
This problem can be solved with both depth-frist search and breath-first search, the following code is an example of depth-first search.

Solution 2: Union Find

### 3.2. Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

We return the result as an array: [1, 1, 2, 3]

Challenge
Can you do it in time complexity O(k log mn), where k is the length of the positions?

Solution
The most straightforward solution is to put all positions into the map, and use the same approach as the 3.1. Number of Islands. However, since it requires solving the problem in O(k logmn) time complexity, the union find approach becomes the only option.

### 3.3. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
For example,

After running your function, the board should be:

Solution1: Breath First Search
Use BFS to find all ‘O’ positions that are not surrounded by ‘X’, and change them to ‘.’ from ‘O’, then replace all remaing ‘O’ to ‘X’, and ‘.’ to ‘O’

Solution2: Union Find

### 3.4. Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Solution: Union Find
Union the two nodes if they are connected by edge, the tree is invalid if a new edge comes to connect two nodes that are already connected.

Question: can union find be applied to solving graph issue? Like finding circle in graph.

### 3.5. Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Solution: