# JAVA, union find method with clear comment, 10ms

• ``````public class Solution {
/* union find (my dfs and bfs all got TLE, I paste my code bellow, hope you can help me analyze the problem)
*
* Method:
* Create a Union find array 'uf' of length m*n to keep tracking roots of each cell.
*      Remark: m, n are the height and width of board respectively
* Initialize each root value to its index number, e.g. uf[10] = 10, uf[11] = 11;
* Scan the whole board, when it is a 'O' cell
*  1) if it is on the edge, change its root value to -1, union its surronding 'O' cells together
*  2) if it is not on the edge, just union its surronding 'O' cells together
*  remark: -1 is the dummy root to mark edge 'O'
*          when union two cells, if anyone's root is -1, change the other's root to -1, otherwise,
*          just make one of their root point to another's root (classic union).
* After that, scan the board again, if it is a 'O' cell and its root is not -1, change its content to 'X'
*
* Performance: 10ms (not that good, but at least passed)
*
*/
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int height = board.length;
int width = board[0].length;
int[] uf = new int[height * width];
//initialize uf array
for (int i = 0; i < uf.length; i ++) {
uf[i] = i;
}
for (int i = 0; i < height; i ++) {
for (int j = 0; j < width; j ++) {
if ((i == 0 || j == 0 || j == width - 1 || i == height - 1) && board[i][j] == 'O') {
uf[i * width + j] = -1;
}
if (board[i][j] == 'O') {
int base = i * width + j;
if (i > 0 && board[i - 1][j] == 'O') union(uf, base - width, base);
if (i < height - 1 && board[i + 1][j] == 'O') union(uf, base + width, base);
if (j > 0 && board[i][j - 1] == 'O') union(uf, base - 1, base);
if (j < width - 1 && board[i][j + 1] == 'O') union(uf, base + 1, base);
}
}
}

for (int i = 0; i < height; i ++) {
for (int j = 0; j < width; j ++) {
if (board[i][j] == 'O' && findRoot(uf, i * width + j) != -1) {
board[i][j] = 'X';
}
}
}
}

public void union(int[] uf, int pos1, int pos2) {
int root1 = findRoot(uf, pos1);
int root2 = findRoot(uf, pos2);
if (root1 == -1 && root2 != -1) {
uf[root2] = -1;
} else if (root1 != -1 && root2 == -1) {
uf[root1] = -1;
} else if (root1 != -1) {
uf[root1] = root2;
}
}

public int findRoot(int[] uf, int pos) {
if (uf[pos] == -1) {
return -1;
} else if (uf[pos] == pos) {
return pos;
} else {
uf[pos] = findRoot(uf, uf[pos]);
return uf[pos];
}
}
}
``````

Bellow is my BFS, got TLE, you know why?

``````public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int height = board.length;
int width = board[0].length;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < height; i ++) {
for (int j = 0; j < width; j ++) {
if ((i == 0 || i == height - 1) || (j == 0 || j == width - 1)) {
if (board[i][j] == 'O') {
}
}
}
}
while (!list.isEmpty()) {
List<Integer> next = new ArrayList<>();
int size = list.size();
for (int i = 0; i < size; i ++) {
int x = list.get(i++);
int y = list.get(i);
//System.out.println("X:" + x + " Y:" + y);
board[x][y] = '.';
if (x > 0 && board[x - 1][y] == 'O') {  next.add(x - 1); next.add(y);   }
if (y > 0 && board[x][y - 1] == 'O') {  next.add(x); next.add(y - 1);   }
if (x < height - 1 && board[x + 1][y] == 'O') { next.add(x + 1); next.add(y);   }
if (y < width - 1 && board[x][y + 1] == 'O') {  next.add(x); next.add(y + 1);   }
}
list = next;
}
for (int i = 0; i < height; i ++) {
for (int j = 0; j < width; j ++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == '.') {
board[i][j] = 'O';
}
}
}
}
}
``````

Here is my DFS, got stack overflow error, sad

``````public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
for (int i = 0; i < board.length; i ++) {
for (int j = 0; j < board[0].length; j ++) {
if ((i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1) && board[i][j] == 'O') {
backtracking(board, i, j);
}
}
}
for (int i = 0; i < board.length; i ++) {
for (int j = 0; j < board[0].length; j ++) {
if (board[i][j] != '.') {
board[i][j] = 'X';
} else {
board[i][j] = 'O';
}
}
}

}

public void backtracking(char[][] board, int x, int y) {
board[x][y] = '.';
if (x > 0 && board[x - 1][y] == 'O') backtracking(board, x - 1, y);
if (x < board.length - 1 && board[x + 1][y] == 'O')  backtracking(board, x + 1, y);
if (y > 0 && board[x][y - 1] == 'O') backtracking(board, x, y - 1);
if (y < board[0].length - 1 && board[x][y + 1] == 'O') backtracking(board, x, y + 1);

}
}
````````

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