# Share my 1-D (m*n) solution beating 97.85%

• The idea is the same, using UnionFind, while it might be faster if we use 1-d array.

``````public class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
int[] parent = new int[m*n];
int count=0;
Arrays.fill(parent, -1);
List<Integer> ret = new ArrayList<Integer>();
for(int[] d:positions){
int cur = d[0]*n+d[1];
count++;
parent[cur] = cur;
if(cur%n!=0 && parent[cur-1]!=-1){
int p1 = find(parent, cur), p2 = find(parent, cur-1);
if(p1!=p2){ count--; parent[p1] = p2;}
}
if((cur+1)%n!=0 && parent[cur+1]!=-1){
int p1 = find(parent, cur), p2 = find(parent, cur+1);
if(p1!=p2){ count--; parent[p1] = p2;}
}
if(cur-n>=0 && parent[cur-n]!=-1){
int p1 = find(parent, cur), p2 = find(parent, cur-n);
if(p1!=p2){ count--; parent[p1] = p2;}
}
if(cur+n<m*n && parent[cur+n]!=-1){
int p1 = find(parent, cur), p2 = find(parent, cur+n);
if(p1!=p2){ count--; parent[p1] = p2;}
}
}
return ret;
}
public int find(int[] parent, int p){
while(p!=parent[p]){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
}
``````

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