# Posts tagged as “union find”

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"


Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination:
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"



Constraints:

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lower case English letters.

## Solution: Connected Components

Use DFS / Union-Find to find all the connected components of swapable indices. For each connected components (index group), extract the subsequence of corresponding chars as a string, sort it and put it back to the original string in the same location.

e.g. s = “dcab”, pairs = [[0,3],[1,2]]
There are two connected components: {0,3}, {1,2}
subsequences:
1. 0,3 “db”, sorted: “bd”
2. 1,2 “ca”, sorted: “ac”
0 => b
1 => a
2 => c
3 => d
final = “bacd”

Time complexity: DFS: O(nlogn + k*(V+E)), Union-Find: O(nlogn + V+E)
Space complexity: O(n)

## C++/Union-Find

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b".  Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.


Example 2:

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.


Example 3:

Input: ["a==b","b==c","a==c"]
Output: true


Example 4:

Input: ["a==b","b!=c","c==a"]
Output: false


Example 5:

Input: ["c==c","b==d","x!=z"]
Output: true


Note:

1. 1 <= equations.length <= 500
2. equations[i].length == 4
3. equations[i][0] and equations[i][3] are lowercase letters
4. equations[i][1] is either '=' or '!'
5. equations[i][2] is '='

## Solution: Union Find

Time complexity: O(n)
Space complexity: O(1)

## C++

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /\, or blank space.  These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

Input:[  " /",  "/ "]Output: 2Explanation: The 2x2 grid is as follows:

Example 2:

Input:[  " /",  "  "]Output: 1Explanation: The 2x2 grid is as follows:

Example 3:

Input:[  "\/",  "/\"]Output: 4Explanation: (Recall that because \ characters are escaped, "\/" refers to \/, and "/\" refers to /\.)The 2x2 grid is as follows:

Example 4:

Input:[  "/\",  "\/"]Output: 5Explanation: (Recall that because \ characters are escaped, "/\" refers to /\, and "\/" refers to \/.)The 2x2 grid is as follows:

Example 5:

Input:[  "//",  "/ "]Output: 3Explanation: The 2x2 grid is as follows:

Note:

1. 1 <= grid.length == grid[0].length <= 30
2. grid[i][j] is either '/''\', or ' '.

# Solution 1: Split grid into 4 triangles and Union Find Faces

Divide each grid into 4 triangles and union them if not split.
Time complexity: O(n^2*alphn(n^2))
Space complexity: O(n^2)

# Solution 3: Pixelation (Upscale 3 times)

Time complexity: O(n^2)
Space complexity: O(n^2)

# Problem

Given a non-empty array of unique positive integers A, consider the following graph:

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4



Example 2:

Input: [20,50,9,63]
Output: 2



Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8



Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= 100000

# Solution: Union Find

For each number, union itself with all its factors.

E.g. 6, union(6,2), union(6,3)

Time complexity: $$O(\Sigma{sqrt(A[i])})$$

Space complexity: $$O(max(A))$$

# Problem

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5


Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3


Example 3:

Input: stones = [[0,0]]
Output: 0


Note:

1. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

# Solution 2: Union Find

Find all connected components (islands)

Ans = # of stones – # of islands

# Related Problems

Mission News Theme by Compete Themes.