# Java solution with time complexity O(k log mn)

• Most of the solutions initialize an array with size m * n. The initialization would take O(mn) times. Use a map instead of the array can help us bypass the initialization.

``````class Solution {
class UnionSet {
public int size = 0;
private Map<Integer, Integer> par = new HashMap<>();
if (!par.containsKey(a)) {
par.put(a, a);
size++;
}
}
public void union(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == -1 || pb == -1 || pa == pb) return;
par.put(pa, pb);
size--;
}
private int find(int x) {
Integer parent = par.get(x);
if (parent == null) return -1;
if (parent == x) {
return x;
}
par.put(x, find(parent));
return par.get(x);
}
}
public List<Integer> numIslands2(int m, int n, int[][] positions) {
int[] dir = {0, 1, 0, -1, 0};
UnionSet unionSet = new UnionSet();
List<Integer> ans = new ArrayList<>();
for (int[] pos : positions) {
for (int i = 0; i < 4; i++) {
int x = pos[0] + dir[i];
int y = pos[1] + dir[i + 1];
if (x < 0 || x >= m || y < 0 || y >= n) {
continue;
}
unionSet.union(pos[0] * n + pos[1], x * n + y);
}