Java, UnionFind with explanation


  • 0
    D

    I use union-find, union all water cells as a single component, union islands accordingly(follow the rules). For each island cell, only check its immediate right and down side if available.

    public class Solution {
        public int numIslands(char[][] grid) 
        {
            if (grid == null || grid.length == 0) { return 0; }
            
            int row = grid.length;
            int col = grid[0].length;
            
            // last extra cell is for water union
            int[] uf = new int[row * col + 1];
            // number of components at beginning, for each union, we minus one in count
            int count = row * col + 1;
            // init
            for (int i = 0; i < uf.length; i++) { uf[i] = i; }
            
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    // if water, connect it to last cell in uf[]
                    if (grid[i][j] == '0') { union(uf, i, j, row, 0, col); count--; }
                    else
                    {
                        // for eahc island, only check its down and right side if available
                        // check down side
                        if (i < row - 1 && grid[i + 1][j] != '0')
                        {
                            if (root(uf, i, j, col) != root(uf, i + 1, j, col))
                            {
                                union(uf, i, j, i + 1, j, col);
                                count--;
                            }
                        }
                        // check right side
                        if (j < col - 1 && grid[i][j + 1] != '0')
                        {
                             if (root(uf, i, j, col) != root(uf, i, j + 1, col))
                            {
                                union(uf, i, j, i, j + 1, col);
                                count--;
                            }
                        }
                    }
                }
            }
            // exclude water part
            return count - 1;
        }
        
        // have the same root?
        private int root(int[] uf, int i, int j, int col)
        {
            int id = i * col + j;
            while (uf[id] != id)
            {
                // compress path
                uf[id] = uf[uf[id]];
                id = uf[id];
            }
            return id;
        }
        
        // union these two
        private void union(int[] uf, int i1, int j1, int i2, int j2, int col)
        {
            int r1 = root(uf, i1, j1, col);
            int r2 = root(uf, i2, j2, col);
            uf[r1] = r2;
        }
    }
    

Log in to reply
 

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