Simple Java Solution Union Find


  • 1
    M
        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';
                }
            }
        }
    

Log in to reply
 

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