# Easy Java Solution Beats 93%

• ``````public class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList();
int[][] matrix = new int[m][n];
int[] roots = new int[m * n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
roots[j + i * n] = j + i * n;
}
}
int count = 0;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] pos : positions) {
count++;
int ox = pos[0];
int oy = pos[1];
matrix[ox][oy] = 1;
for (int[] d : dirs) {
int x = ox + d[0];
int y = oy + d[1];
if (x >= m || x < 0 || y >= n || y < 0) continue;
if (matrix[x][y] == 1) {
int root1 = find(roots, y + x * n);
int root2 = find(roots, oy + ox * n);
if (root1 != root2) {
roots[root1] = root2;
count--;
}
}
}
res.add(count);
}

return res;
}

private int find(int[] roots, int key) {
while (roots[key] != key) {
roots[key] = roots[roots[key]];
key = roots[key];
}
return key;
}
}
``````

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