# QuickUnion method

• Well, this took me a while to write because all the possible scenarios when you connecting the O's. Basically, I get the QuickUnionWithPathCompression (path compression is not required here, I just type it to practice a bit). The idea is simple, loop from row= 1 to 2nd last and col = 1 to 2nd last. For each cell, we search four different directions. If current cell is 'O' and its neighbor is 'O' we union them. Because the nature of implementation of this data structure, we have to make sure edge cell are the second parameter of the union, and use of isBoundary(qu.find(flat(x, y))) to union is required.
The overall performance is bad though :)
QuickUnion Utility Class

``````    private class QuickUnion{
private int count;
private int[] parent;
public QuickUnion(int n){
count = n;
parent = new int[n];
for (int i = 0; i < n; i++){
parent[i] = i;
}
}

public int count(){
return count;
}

public int find(int p){
int root = p;
while (root != parent[root])
root = parent[root];
while (p != root){
int newP = parent[p];
parent[p] = root;
p = newP;
}
return root;
}

public void union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
}

public boolean connected(int p, int q){
return find(p) == find(q);
}
}
``````

Solution

``````	private int m, n;

private int flat(int i, int j) {
return i * n + j;
}

private boolean isBoundary(int p) {
int x = p / n, y = p % n;
return isBoundary(x, y);
}

private boolean isBoundary(int x, int y) {
return x == 0 || x == m - 1 || y == 0 || y == n - 1;
}

public void solve(char[][] board) {
if (board == null || board.length < 3 || board[0].length < 3) return;
m = board.length;
n = board[0].length;
QuickUnion qu = new QuickUnion(m * n);
int[][] directions = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };
for (int row = 1; row < m - 1; row++) {
for (int col = 1; col < n - 1; col++) {
if (board[row][col] == 'O') {
for (int[] direction : directions) {
int x = row + direction[0], y = col + direction[1];
int current = flat(row, col);
int neighbor = flat(x, y);
if (board[x][y] == 'O' && !qu.connected(current, neighbor)) {
if (isBoundary(qu.find(neighbor))) {
qu.union(current, neighbor);
} else {
qu.union(neighbor, current);
}
}
}
}
}
}
for (int row = 1; row < m - 1; row++) {
for (int col = 1; col < n - 1; col++) {
int p = qu.find(flat(row, col));
if (!isBoundary(p)) board[row][col] = 'X';
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.