Q29 Number of Islands II - Coding Ninjas (DSU)

import java.util.Arrays;

public class Solution {
    public static int[] numOfIslandsII(int m, int n, int[][] q) {
        /* dynamic graph so we will use DSU , here set represent -> every cell which is part of
        same island will be under same set 
        */

        //making 2d array to 1d array based on cell no
        int parent[] = new int[m*n];
        int rank[] = new int[m*n];
        int ans[] = new int[q.length];

        Arrays.fill(parent, -1);

        //running queries one by one
        int count = 0;  //for islands

        for(int i = 0 ; i < q.length ; i++){
            int position[]= q[i];
            int x = position[0] , y = position[1];
            int cellno = x*n+y;

            //if already processed add to answer and continue
            if(parent[cellno] != -1){
                ans[i] = count;
                continue;
            }

            //if its coming first time make it island cell
            parent[cellno] = cellno;
            rank[cellno] = 1;
            count ++ ;          //new island
            
            //now check its adjacent cells if any one of it is island cell they will merge
            for(int dirs[] : dir){
                int rowdash = x + dirs[0];
                int coldash = y + dirs[1];
                int celldash = rowdash * n + coldash;

                //if invalid cell continue
                if(rowdash < 0 || coldash < 0 || rowdash >= m || coldash >= n 
                || parent[celldash] == -1)
                continue;
                
                //if valid cell combine both islands and decrease count 
                union(celldash , cellno , parent ,rank);
                count--;
                
            }
            
            ans[i] = count;
        }
        return ans;
    }

    public static int dir[][] = {{0,1} , {1,0} , {-1,0} , {0,-1}};
    public static int find(int x , int[] parent){
        if(parent[x] == x)
        return x;
        
        int temp = find(parent[x] , parent);
        parent[x] = temp;
        return temp;
    }
    public static void union(int x , int y , int[] parent , int[] rank){
        int lx = find(x , parent);
        int ly = find(y , parent);

        if(lx != ly){
            if(rank[lx] > ly){
                parent[ly] = lx;
            }
            else if(rank[lx] < ly){
                parent[lx] = ly;
            }
            else{
                parent[lx] = ly;
                rank[ly] ++;
            }
        }
    }
}