# My java solution using Union Find

• ``````public void solve(char[][] board) {
if(board.length == 0) return;
int m = board.length;
int n = board[0].length;
UnionFind uf = new UnionFind(m,n);
int cache = -1;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == 'O'){
if(i == 0 || i == m-1 || j == 0 || j == n-1){//judge four edges of board
if(cache == -1) cache = i*n + j;
else uf.union(cache,i*n + j);// union 'O' in four edges of board
}
if(j+1 < n && board[i][j+1] == 'O') uf.union(i*n+j,i*n+j+1);// union right direction
if(i+1 < m && board[i+1][j] == 'O') uf.union(i*n+j,(i+1)*n+j);// union down direction
}
}
}
if(cache == -1){// it shows four edges of board are all 'X'
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == 'O') board[i][j] = 'X';// we just need set 'O' to 'X'
}
}
return;
}
for(int i = 0; i < m; i++){// set 'O' to 'X' which 'O' is not connected with 'O' of cache
for(int j = 0; j < n; j++){
if(board[i][j] == 'O' && !uf.isConnected(cache,i*n+j))  board[i][j] = 'X';
}
}
return;
}
private class UnionFind{
int[] id;
int[] rank;
public UnionFind(int m,int n){
id = new int[m*n];
rank = new int[m*n];
for(int i = 0; i < m*n; i++){
id[i] = i;
rank[i] = 1;
}
}
public int find(int p){
if(p != id[p]) id[p] = find(id[p]);
return id[p];
}
public boolean isConnected(int p,int q){
int pp = find(p);
int qq = find(q);
return pp == qq;
}
public void union(int p ,int q){
int pp = find(p);
int qq = find(q);
if(pp == qq) return;
if(rank[pp] > rank[qq]){
id[qq] = pp;
rank[pp] += rank[qq];
}
else{
id[pp] = qq;
rank[qq] += pp;
}
}
}``````

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