Share my C++ Union-Find solution, which is self-explanatory.


  • 1
    S

    The Union Find implementation uses union by rank and path compression. All we need is to find all 'O's in the boundary and union all adjacent 'O's.

    class Unions {
    private:
        vector<int> roots;
        vector<int> ranks;
    public:
        Unions(int m, int n) {
            int size = m*n;
            roots.resize(size);
            ranks.resize(size);
            for (int i=0; i<size; ++i) {
                roots[i] = i;
                ranks[i] = 0;
            }
        }
        
        int findRoot (int x) {
            if (x != roots[x]) {
                roots[x] = findRoot(roots[x]);
            }
            return roots[x];
        }
        
        void unionAll(int x, int y) {
            int rootX = findRoot(x);
            int rootY = findRoot(y);
            
            if (ranks[rootX] > ranks[rootY]) {
                roots[rootY] = rootX;
            } else {
                roots[rootX] = rootY;
                if (ranks[rootX] == ranks[rootY]) {
                    ++ranks[rootY];
                }
            }
        }
    };
    
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            if (board.empty() || board[0].empty()) return;
            int m = board.size();
            int n = board[0].size();
            Unions unions(m, n);
            int boundary = -1;
            int cur;
            for (int i=0; i<m; ++i) {
                for (int j=0; j<n; ++j) {
                    if (board[i][j] == 'O') {
                        cur = i*n+j;
                        if (inBoundary(i, j, m, n)) {
                            if (boundary != -1) {
                                unions.unionAll(boundary, cur);
                            } else {
                                boundary = cur;
                            }
                        }
                        if (i+1<m && board[i+1][j] == 'O') {
                            unions.unionAll(cur, (i+1)*n+j);
                        }
                        if (j+1<n && board[i][j+1] == 'O') {
                            unions.unionAll(cur, i*n+j+1);
                        }
                    }
                }
            }
            
            if (boundary == -1) {
                for (auto &aLine : board) {
                    for (auto &c: aLine) {
                        c = 'X';
                    }
                }
                return;
            }
            
            int boundaryRoot = unions.findRoot(boundary);
            for (int i=0; i<m; ++i) {
                for (int j=0; j<n; ++j) {
                    if (unions.findRoot(i*n+j) != boundaryRoot) {
                        board[i][j] = 'X';
                    }
                }
            }
            
        }
        
        inline bool inBoundary(int x, int y, int m, int n) {
            return (x==0 || y==0 || x==m-1 || y==n-1);
        }
    };

Log in to reply
 

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