Number of islands (Find Union) - Teeeeeebag/LeetCode GitHub Wiki

1. if (grid[i][j] == '1' && id[p] == -1)
   This is not true, because even id[p] != -1 there is still opportunity to union!
2. Pay attention to the place where we update id[p] with p
3. Time complexity is O(n^3) because find() takes n

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length ==0 || grid[0].length == 0){
            return 0;
        }
        //index = x*grid[0].length + y;
        int[] id = new int[grid.length*grid[0].length];
        Arrays.fill(id, -1);
        for (int i=0; i<grid.length; ++i){
            for (int j=0; j<grid[0].length; ++j){
                int p = i*grid[0].length + j;
                //This if cannot have something like grid[i][j] == '1' && id[p] == -1
                if(grid[i][j] == '1'){
                    if (id[p] == -1)
                        id[p] = p; // This is very important. To deal with the case where there is no '1' neighbor
                    if (i-1>=0 && grid[i-1][j] == '1'){
                        int p2 = (i-1)*grid[0].length + j;
                        union(p, p2, id);
                    }
                    if (i+1<grid.length && grid[i+1][j] == '1'){
                        int p2 = (i+1)*grid[0].length + j;
                        union(p, p2, id);
                    }
                    if (j-1>=0 && grid[i][j-1] == '1'){
                        union(p, p-1, id);
                    }
                    if (j+1<grid[0].length && grid[i][j+1] =='1'){
                        union(p, p+1, id);
                    }
                }
            }
        }
        int cnt = 0;
        for (int i=0; i<id.length; ++i){
            if(id[i] == i){
                ++cnt;
            }
        }
        return cnt;
    }
    private int find(int p, int[] id){
        //find root 
        if(id[p] == -1){
            id[p] = p;
        }// This is very important. 
        while (id[p] != p){
            p = id[p];
        }
        return p;
    }
    private void union(int p1, int p2, int[] id){
        int root1 = find(p1, id);
        int root2 = find(p2, id);
        if (root1 == root2){
            return;
        } else {
            id[root1] = root2;
        }
    }
}