Java BFS&Union-Find solution. Straight forward.


  • 1

    The idea was introduced by @sugeladi here: https://discuss.leetcode.com/topic/17224/a-really-simple-and-readable-c-solution-only-cost-12ms

    But I'm using BFS to avoid potential stack overflow when using DFS.

    public class Solution {
        // Define Node class to store position information.
        // Each element in board can be regarded as a Node, since we are using BFS
        // x is row index and y is column index
        class Node {
            int x;
            int y;
            Node(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
        
        public void solve(char[][] board) {
            // When board is smaller than or equal to 2*2. No change needed. Return.
            if (board == null || board.length < 3 || board[0].length < 3) {
                return;
            }
            
            int m = board.length;
            int n = board[0].length;
            
            // Use array visited to avoid re-visited, which will cause infinite loop
            int[][] visited = new int[m][n];
            Queue<Node> queue = new LinkedList<>();
            
            // This is the first "layer" of Nodes 
            // They are 'O' Nodes at the boundary
            for (int i = 0; i < m; i++) {
                if (board[i][0] == 'O') {
                    queue.offer(new Node(i, 0));
                }
                if (board[i][n - 1] == 'O') {
                    queue.offer(new Node(i, n - 1));
                }
            }
            
            for (int i = 0; i < n; i++) {
                if (board[0][i] == 'O') {
                    queue.offer(new Node(0, i));
                }
                if (board[m - 1][i] == 'O') {
                    queue.offer(new Node(m - 1, i));
                }
            }
            
            // BFS use queue
            // iterate the current "layer" and put next "layer" into the queue
            // The next "layer" are those unvisited 'O' Nodes that are adjacent to current Nodes
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Node node = queue.poll();
                    update(node, visited, queue, board);
                }
            }
            
            // Traverse the board. Change 'O' Node to 'X', '*' Node to 'O'
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '*') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
        
        // Change the character at this position to '*' and mark as visited
        // Put adjacent, unvisited, 'O' Node to the queue. They are the next "layer"
        public void update(Node node, int[][] visited, Queue<Node> queue, char[][] board) {
            board[node.x][node.y] = '*';
            visited[node.x][node.y] = 1;
            
            if (node.x - 1 >= 0 && visited[node.x - 1][node.y] == 0 && board[node.x - 1][node.y] == 'O') {
                queue.offer(new Node(node.x - 1, node.y));
            }
            if (node.x + 1 < board.length && visited[node.x + 1][node.y] == 0 && board[node.x + 1][node.y] == 'O') {
                queue.offer(new Node(node.x + 1, node.y));
            }
            if (node.y - 1 >= 0 && visited[node.x][node.y - 1] == 0 && board[node.x][node.y - 1] == 'O') {
                queue.offer(new Node(node.x, node.y - 1));
            }
            if (node.y + 1 < board[0].length && visited[node.x][node.y + 1] == 0 && board[node.x][node.y + 1] == 'O') {
                queue.offer(new Node(node.x, node.y + 1));
            }
        }
    }
    

    Another solution is to use Union-Find like this:

    public class Solution {
        class UF {
            public int count;
            public int[] id;
                
            UF (int N) {
                count = N;
                id = new int[N];
                for (int i = 0; i < N; i++) {
                    id[i] = i;
                }
            }
                
            public int find(int p) {
                while (p != id[p]) {
                    id[p] = id[id[p]];
                    p = id[p];
                }
                return p;
            }
                
            public void union(int p, int q) {
                int pRoot = find(p);
                int qRoot = find(q);
                if (pRoot == qRoot) {
                    return;
                }
                id[pRoot] = qRoot;
                return;
            }
                
            public boolean isConnected(int p, int q) {
                int pRoot = find(p);
                int qRoot = find(q);
                if (pRoot == qRoot) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        
        public void solve(char[][] board) {
            if (board == null || board.length < 3 || board[0].length < 3) {
                return;
            }
            
            int m = board.length;
            int n = board[0].length;
            UF uf = new UF(m * n + 1);  //an extra node is created as dummy node
            
            // Union all 'O' at boundary to the dummy node and union all 'O' nodes
            // In this situation, all the 'O' node that are connected to the boundary 'O' node are connected to the dummy node
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O' && (i == 0 || j == 0 || i == m - 1 || j == n - 1)) {
                        uf.union(i * n + j, m * n);
                    } else if (board[i][j] == 'O') {
                        // check and connect with neighbor 'O' nodes
                        if (i > 0 && board[i - 1][j] == 'O') {
                            uf.union((i - 1) * n + j, i * n + j);
                        }
                        if (i < m - 1 && board[i + 1][j] == 'O') {
                            uf.union((i + 1) * n + j, i * n + j);
                        }
                        if (j > 0 && board[i][j - 1] == 'O') {
                            uf.union(i * n + j - 1, i * n + j);
                        }
                        if (j < n - 1 && board[i][j + 1] == 'O') {
                            uf.union(i * n + j + 1, i * n + j);
                        }
                    }
                }
            }
            
            // traverse the board to mark all the 'O' that is not connected to the dummy node
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O' && !uf.isConnected(i * n + j, m * n)) {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }
    

Log in to reply
 

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