# Simple Java Solution Union Find

• ``````    private class UnionFind{
int[] parent;
public UnionFind(int n) {
parent = new int[n + 1];
for (int i = 0; i <= n; ++i) parent[i] = i;
}
public int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
public void union(int a, int b) {
int root_a = find(a), root_b = find(b);
if (root_a != root_b) {
parent[root_a] = root_b;
}
}
}
private static final int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
private boolean inBound(int i, int j, int m, int n) {
return i >= 0 && i < m && j >= 0 && j < n;
}
private boolean onEdge(int i, int j, int m, int n) {
return i == 0 || i == m - 1 || j == 0 || j == n - 1;
}
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length, n = board[0].length;
UnionFind uf = new UnionFind(m * n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] != 'O') continue;
for (int k = 0; k < dx.length; ++k) {
int x = i + dx[k], y = j + dy[k];
if (inBound(x, y, m, n) && board[x][y] == 'O') uf.union(i * n + j, x * n + y);
}
if (onEdge(i, j, m, n)) uf.union(i * n + j, m * n);
}
}
for (int i = 1; i < m - 1; ++i) {
for (int j = 1; j < n - 1; ++j) {
if (uf.find(i * n + j) != uf.find(m * n)) board[i][j] = 'X';
}
}
}
``````

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