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] ++; } } } }