## Number of Islands II

• Time:O(n\log n)
• Space:O(n)

## C++

``````class UF {
public:
vector<int> id;

UF(int n) : id(n, -1) {}

void union_(int u, int v) {
id[u] = v;
}

int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};

class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
const vector<int> dirs{0, 1, 0, -1, 0};
vector<int> ans;
vector<vector<bool>> seen(m, vector<bool>(n));
UF uf(m * n);
int count = 0;

for (const auto& p : positions) {
const int i = p[0];
const int j = p[1];
if (seen[i][j]) {
ans.push_back(count);
continue;
}
seen[i][j] = true;
const int id = getId(i, j, n);
uf.id[id] = id;
++count;
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
const int neighborId = getId(x, y, n);
if (uf.id[neighborId] == -1)  // water
continue;
const int currentParent = uf.find(id);
const int neighborParent = uf.find(neighborId);
if (currentParent != neighborParent) {
uf.union_(currentParent, neighborParent);
--count;
}
}
ans.push_back(count);
}

return ans;
}

private:
int getId(int i, int j, int n) {
return i * n + j;
}
};
``````

## JAVA

``````class UF {
public int[] id;

public UF(int n) {
id = new int[n];
Arrays.fill(id, -1); // water
}

public void union(int u, int v) {
id[u] = v;
}

public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}

class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
final int[] dirs = {0, 1, 0, -1, 0};
List<Integer> ans = new ArrayList<>();
boolean[][] seen = new boolean[m][n];
UF uf = new UF(m * n);
int count = 0;

for (int[] p : positions) {
final int i = p[0];
final int j = p[1];
if (seen[i][j]) {
continue;
}
seen[i][j] = true;
final int id = getId(i, j, n);
uf.id[id] = id;
++count;
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
final int neighborId = getId(x, y, n);
if (uf.id[neighborId] == -1) // water
continue;
final int currentParent = uf.find(id);
final int neighborParent = uf.find(neighborId);
if (currentParent != neighborParent) {
uf.union(currentParent, neighborParent);
--count;
}
}
}

return ans;
}

private int getId(int i, int j, int n) {
return i * n + j;
}
}
``````

## Python

``````class UF:
def __init__(self, n: int):
self.id = [-1] * n

def union(self, u: int, v: int) -> None:
self.id[u] = v

def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]

class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
dirs = [0, 1, 0, -1, 0]
ans = []
seen = [[False] * n for _ in range(m)]
uf = UF(m * n)
count = 0

def getId(i: int, j: int, n: int) -> int:
return i * n + j

for i, j in positions:
if seen[i][j]:
ans.append(count)
continue
seen[i][j] = True
id = getId(i, j, n)
uf.id[id] = id
count += 1
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
neighborId = getId(x, y, n)
if uf.id[neighborId] == -1:  # water
continue
currentParent = uf.find(id)
neighborParent = uf.find(neighborId)
if currentParent != neighborParent:
uf.union(currentParent, neighborParent)
count -= 1
ans.append(count)

return ans
``````