var numIslands = function(grid) {
    
    const visited = grid.map(row => row.map(c => 0));
    const isLand = (x,y) => grid[y] ? grid[y][x]==='1' ? true : false : false;
    
    const dx = [1,0,-1,0];
    const dy = [0,1,0,-1];
    
    let union = 0;
    
    const dfs = (x,y) => {
        if(visited[y][x]) return;
        visited[y][x] = 1;
        
        for(let i=0; i<4; i++){
            const xx = x + dx[i];
            const yy = y + dy[i];
            isLand(xx, yy) && dfs(xx, yy);
        }
    }
    
    grid.forEach((row, y) => 
     row.forEach((land, x)=> {
        if(visited[y][x]) return;
        
        if(land==='1'){
            union++;
            dfs(x,y);
        }
    }))
    
    return union;
};

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    
    const visited = grid.map(row => row.map(c => 0));
    const isLand = (x,y) => grid[y] ? grid[y][x]==='1' ? true : false : false;
    
    const dx = [1,0,-1,0];
    const dy = [0,1,0,-1];
    
    let union = 0;
    
    const stack = [];
    
    grid.forEach((row, y)=>
     row.forEach((land, x)=> {
      if(visited[y][x]) return;
        
      if(land==='1'){
        stack.push([x,y]);
        union++;
        while(stack.length){
            const [x,y] = stack.shift();
            
            if(visited[y][x]) continue;
            visited[y][x] = 1;
            
            for(let i=0; i<4; i++){
                const xx = x+dx[i];
                const yy = y+dy[i];
                
                isLand(xx, yy) && stack.push([x+dx[i], y+dy[i]]);
            }
        }
      }  
    }))
    
    return union;
};

/**
 * @param {character[][]} grid
 * @return {number}
 */

class UnionFind{
    constructor(grid){
        this.parent = new Array(grid.length * grid[0].length);
        this.rank = new Array(grid.length * grid[0].length);
        this.count = 0;

        grid.forEach((row, r) => {
            row.forEach((col, c) => {
                if(grid[r][c]==='1'){
                    this.count++;
                    const nth = grid[0].length * r + c;
                    this.parent[nth] = nth
                    this.rank[nth] = 0;
                };               
            })
        });
        console.log(this);
    }
    
    find(node){ // value        
        const parentNode = this.parent[node];
        if(node!==parentNode){
            this.parent[node] = this.find(parentNode);
        }
        
        return this.parent[node]; // when parentNode is rootNode,
    }
    
    union(n1,n2){
        const root1 = this.find(n1); // 3 => 3 (rootA)
        const root2 = this.find(n2); // 4 => 4 (rootB)
        if(root1!==root2){
            if(this.rank[root1] > this.rank[root2]){
                this.parent[root2] = root1;
            }else if(this.rank[root2] > this.rank[root1]){
                this.parent[root1] = root2;
            }else{
                this.parent[root2] = root1;
                this.rank[root1]++;
            }
            this.count--;
        }
    }
}

var numIslands = function(grid) {
    
    if(grid.length===0){
        return 0;
    }
    
    const isLand = (x,y) => grid[y] ? grid[y][x]==='1' ? true : false : false;
    
    const dx = [1,0,-1,0];
    const dy = [0,1,0,-1];
    
    const unionFind = new UnionFind(grid);
    
    for(let r=0; r<grid.length; r++){
        for(let c=0; c<grid[0].length; c++){
            if(grid[r][c]==='1'){
                grid[r][c] = '0';

                for(let i=0; i<4; i++){
                    const xx = c + dx[i];
                    const yy = r + dy[i];
                    if(isLand(xx, yy)){
                        unionFind.union(r*grid[0].length +c, yy*grid[0].length + xx);
                    }
                }
                
            }
        }
    }
    
    return unionFind.count;
};