Java Union Find Solution


  • 0
    Z

    It's intuitive to come up with a union-find based solution. To make union-find algorithm more efficient, we use a weighted version of the algorithm and try to make the forest as flat as possible.

    class Solution {
        public int numIslands(char[][] grid) {
            if (grid==null || grid.length<=0 || grid[0].length<=0) return 0;
            
            int m = grid.length, n = grid[0].length;
            int cnt = m*n, neighbor = 0, current = 0;
            
            // Union-find data type
            int[] uf = new int[cnt];
            // Size for each island
            int[] sz = new int[cnt];
            
            // initiate each cell of land as separated
            for (int i=0; i<cnt; i++) {uf[i]=i; sz[i]=1;}
            for (int i=0; i<m; i++) {
                for (int j=0; j<n; j++) {
                    if (grid[i][j]=='0') {cnt--; continue;}
                    // current: index for current cell in UnionFind array uf
                    current = i * n + j;
                    // Check cell above the current one
                    neighbor = (i - 1) * n + j;
                    if (i>0 && grid[i-1][j]=='1' && !connected(uf, current, neighbor)) {
                        union(uf, sz, current, neighbor);
                        cnt--;
                    }
                    // Check cell on the right hand side of the current one
                    neighbor = i * n + j + 1;
                    if (j<n-1 && grid[i][j+1]=='1' && !connected(uf, current, neighbor)) {
                        union(uf, sz, current, neighbor);
                        cnt--;
                    }
                }
            }
            return cnt;
        }
        
        public void union(int[] uf, int[] sz, int i, int j) {
            // make smaller trees point to larger ones
            int ri = root(uf, i), rj = root(uf, j);
            if (sz[ri] <= sz[rj]) {
                uf[ri] = rj;
                sz[rj] += sz[ri];
            }
            else {
                uf[rj] = ri;
                sz[ri] += sz[rj];
            }
        }
        
        public int root(int[] uf, int i) {
            // flat the tree by halve
            while (i != uf[i]) {
                uf[i] = uf[uf[i]];
                i = uf[i];
            }
            return i;
        }
        
        public boolean connected(int[] uf, int i, int j) {
            return root(uf, i) == root(uf, j);
        }
    }
    

Log in to reply
 

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