# Java solution with union-find class

• Runtime of union() and find(): O(k), k is the height of tree, worst case is n.

``````public class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
List<Integer> list = new ArrayList<>();
UF2D uf = new UF2D(m, n);
for(int[] p : positions){
int x = uf.getIndex(p[0], p[1]);
if(repeat) continue;
for(int[] dir : dirs){
int ni=p[0]+dir[0], nj=p[1]+dir[1]; //neighbor_i, neighbor_j
int y = uf.getIndex(ni, nj);
if(!uf.isLand(y)) continue; //ni, nj out of border or not land
uf.union(x, y);
}
}
return list;
}

class UF2D{
private int[] uf;
private int m, n;
private int count = 0;

public UF2D(int m, int n){
this.m = m;
this.n = n;
uf = new int[m*n+1];
}
// all index > 0
public int getIndex(int i, int j) {
if (i < 0 || j < 0 || i >= m || j >= n) return 0;
return i*n + j + 1;
}
if(uf[i] == i) return false;
uf[i] = i;
count++;
return true;
}
public void union(int x, int y){
int xx = find(x);
int yy = find(y);
if(xx == yy) return;
uf[xx] = yy;
count--;
}
private int find(int i){
if(uf[i] == i) return i;
uf[i] = find(uf[i]);
return uf[i];
}
public int count(){
return count;
}
public boolean isLand(int i){
return uf[i] != 0;
}
}

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.