# Long but clear java solution beats 100%

• Union Find. An important optimization is to minimize the height of the tree by asking leaves to point to root directly.

``````public class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<>();
int count = 0;
int[] parent = new int[m * n]; // use an array to represent the tree
for (int i = 0; i < m * n; i++) parent[i] = -1; // indicate this position is 0
for (int[] point : positions) {
count++;
int key = point[0] * n + point[1]; // map (row, col) to a single value
parent[key] = key; // set itself as root
if (key - n >= 0) { // can go up
int next = key - n;
if (parent[next] >= 0) {
while (parent[next] != next) { // find the root of the neighbor
int copy = parent[next];
parent[next] = key; // important for efficiency
next = copy;
}
parent[next] = key; // set the neighbor's root
count--;
}
}
if (key + n < m * n) { // can go down
int next = key + n;
if (parent[next] >= 0) {
while (parent[next] != next) {
int copy = parent[next];
parent[next] = key;
next = copy;
}
if (key != next) {
count--;
parent[next] = key;
}
}
}
if (key % n > 0) { // can go left
int next = key - 1;
if (parent[next] >= 0) {
while (parent[next] != next) {
int copy = parent[next];
parent[next] = key;
next = copy;
}
if (key != next) {
count--;
parent[next] = key;
}
}
}
if (key % n < n - 1) { // can go right
int next = key + 1;
if (parent[next] >= 0) {
while (parent[next] != next) {
int copy = parent[next];
parent[next] = key;
next = copy;
}
if (key != next) {
count--;
parent[next] = key;
}
}
}