JAVA, union find method with clear comment, 10ms


  • 0
    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') {
                            list.add(i);
                            list.add(j);
                        }
                    }
                }
            }
            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);
            
        }
    }
    ``

Log in to reply
 

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