# Slightly modified an OOP Java Solution

• ``````public class Solution {

private int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public List<Integer> numIslands2(int m, int n, int[][] positions) {
UnionFind2D islands = new UnionFind2D(m, n);
List<Integer> ans = new ArrayList<>();
for (int[] position : positions) {
int x = position[0], y = position[1];
for (int[] d : dir) {
int q = islands.getID(x + d[0], y + d[1]);
if (q >= 0 && !islands.find(p, q))
islands.unite(p, q);
}
}
return ans;
}
}

class UnionFind2D {
private int[] id;
private int[] sz;
private int m, n, count;

public UnionFind2D(int m, int n) {
this.count = 0;
this.n = n;
this.m = m;
this.id = new int[m * n];
Arrays.fill(id, -1);
this.sz = new int[m * n];
}

public int index(int x, int y) { return x * n + y; }

public int size() { return this.count; }

public int getID(int x, int y) {
if (0 <= x && x < m && 0<= y && y < n)
return id[index(x, y)];
return -1;
}

public int add(int x, int y) {
int i = index(x, y);
id[i] = i; sz[i] = 1;
++count;
return i;
}

public boolean find(int p, int q) {
return root(p) == root(q);
}

public void unite(int p, int q) {
int i = root(p), j = root(q);
if (sz[i] < sz[j]) { //weighted quick union
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
--count;
}

private int root(int i) {
for (;i != id[i]; i = id[i])
id[i] = id[id[i]]; //path compression
return i;
}
}``````

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