# O(K+N) Java solution, clean, using optimized DSU (path compression and union by rank heuristics)

• ``````public class Solution {

static class DSU{
int[] parent;
int[] rank;
int[] size; // size of each set, or more accurately size of set which contains the i'th node
int setCount; // total number of distinct sets

// using zero based indexing
public DSU(int n){
parent = new int[n];
rank = new int[n];
size = new int[n];
setCount = n;

for(int i=0; i<n; i++){
makeSet(i);
}
}

public void makeSet(int x){
parent[x] = x;
rank[x] = x;
}

public boolean union(int x, int y){
int px = findSet(x), py = findSet(y);
if(px == py) return false;
return true;
}

private void link(int x, int y){
if(rank[x] > rank[y]) parent[y] = x;
else{
parent[x] = y;
if(rank[x] == rank[y]) rank[y]++;
}
}

public int findSet(int x){
if(parent[x]!=x) parent[x] = findSet(parent[x]);
return parent[x];
}
}

// returns the vertice mapping for position i,j, using 0 based indexing
int v_num(int i, int j){
return i*n + j;
}

// clockwise from 12:00
int[] dx = new int[]{0,1,0,-1};
int[] dy = new int[]{-1,0,1,0};

int[][] grid;
int m, n;

public List<Integer> numIslands2(int m_, int n_, int[][] positions) {
m = m_;
n = n_;
grid = new int[m][n];
DSU dsu = new DSU(m*n);
List<Integer> res = new ArrayList<>();

int cnt = 0, lcl = 0;
for(int i=0; i<positions.length; i++){
cnt++; // assuming each position is an actual piece of water not already land
lcl = 0;

int py = positions[i][0];
int px = positions[i][1];
grid[py][px] = 1;

for(int j=0; j<4; j++){
int x = px+dx[j], y = py+dy[j];

if(x<0 || x>=n || y<0 || y>=m) continue;

if(grid[y][x] == 1){
int u = v_num(py, px);
int w = v_num(y, x);
if(dsu.union(u, w)) lcl++;
}
}
cnt-=lcl;