Number of islands

Given a boolean 2D matrix,0is represented as the sea,1is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Example

Given graph:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

return3.

Analysis:

Use Union find. Represent the grid using a array, index being x*m+y (m is length of each row, x is row, y is column index)

Have a HashSet<Integer> to keep track of all representative of each island.

Iterate through whole grid, at each "1", check its right and down adjacent node, if that node is "1", call "connect" and remember to remove one of the representative node from HashSet when 2 island got linked. After checking adjacent nodes, add "find(currentNode)" to HashSet as adding "island".

In the end, size of island should represent the answer.

Answer:

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    private Set<Integer> islands = new HashSet<Integer>();
    private int[] father = null;
    public int numIslands(boolean[][] grid) {
        // Write your code here
        if(grid.length == 0)
        {
            return 0;
        }
        int n = grid.length;
        int m = grid[0].length;
        init(n,m);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j])
                {
                    int ij = i*m+j;
                    if(i<n-1) //still can look down for connection
                    {
                        if(grid[i+1][j])
                        {
                            connect(ij, ij+m);
                        }
                    }
                    if(j<m-1)
                    {
                        if(grid[i][j+1])
                        {
                            connect(ij, ij+1);
                        }
                    }
                    islands.add(find(ij));
                }
            }
        }
        return islands.size();
    }

    private void init(int n, int m)
    {
        int nm = n*m;
        father = new int[nm];
        for(int i=0; i<nm; i++)
        {
            father[i] = i;
        }
    }

    private void connect(int a, int b)
    {
        int rootA = find(a);
        int rootB = find(b);
        if(rootA != rootB)
        {
            father[rootA] = rootB;
            islands.remove(rootA);
        }
    }

    private int find(int x)
    {
        if(father[x] == x)
        {
            return x;
        }
        return father[x] = find(father[x]);
    }
}