public class Solution {
private int[] roots;
private int count;
public List<Integer> numIslands2(int m, int n, int[][] positions) {
int[][] matrix = new int[m][n];
roots = new int[m*n];
List<Integer> res = new ArrayList<>();
// initialize roots
for(int i=0; i<m*n; i++){
roots[i] = i;
}
for(int[] pos:positions){
int x = pos[0], y = pos[1];
// check if current position is already land
if(1==matrix[x][y]){
res.add(count);
continue;
}
int cur = x*n+y;
matrix[x][y] = 1;
++count;
// visit neighbors
if(y>0 && matrix[x][y1]>0){
union(cur, cur1);
}
if(y<n1 && matrix[x][y+1]>0){
union(cur, cur+1);
}
if(x>0 && matrix[x1][y]>0){
union(cur, curn);
}
if(x<m1 && matrix[x+1][y]>0){
union(cur, cur+n);
}
res.add(count);
}
return res;
}
private int find(int t){
while(t!=roots[t]){
roots[t] = roots[roots[t]];
t = roots[t];
}
return t;
}
private void union(int a, int b){
int aroot = find(a), broot = find(b);
if(aroot!=broot){
roots[aroot] = broot;
count;
}
}
}
Java simple UnionFind solution beating 97.94%


@fei38 Thank you for pointing out that a position in the array may already be a land. I have updated my code to avoid such bug. And I found that even OJ did not take this case into consideration.

@skyxu Thank you for modifying your code and reply so fast. And thank you for share your code. I learnt a lot.

@skyxu Can I replace the following code:
'''
if(1==matrix[x][y]){
res.add(res.get(res.size()1));
continue;
}
'''
with:
'''
if(1==matrix[x][y]){
res.add(count);
continue;
}
'''
I think that would be more easy. Thank you!

@fei38 Yes you are right! I didn't notice that. Thanks for pointing out! Really appreciate that.

@fei38 said in Java simple UnionFind solution beating 97.94%:
{{0,0}, {0,1}, {1,2}, {2,1},{2,1}}
It is good to remove a potential bug. But I do not think remove duplicate is the main point of this problem. That is why OJ does not take it into account.