## 305. Number of Islands II

A 2d grid map of `m`

rows and `n`

columns is initially filled with water. We may perform an *addLand* operation which turns the water at position (row, col) into a land. Given a list of positions to operate, **count the number of islands after each addLand operation**. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

**Example:**

Input:m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]Output:[1,1,2,3]

**Explanation:**

Initially, the 2d grid `grid`

is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0 0 0 0 0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0 0 0 0 Number of islands = 1 0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0 0 0 0 Number of islands = 1 0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0 0 0 1 Number of islands = 2 0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0 0 0 1 Number of islands = 3 0 1 0

**Follow up:**

Can you do it in time complexity O(k log mn), where k is the length of the `positions`

?

## Rust Solution

```
struct Solution;
struct UnionFind {
parent: Vec<usize>,
n: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
i
} else {
let k = self.find(j);
self.parent[i] = k;
k
}
}
fn union(&mut self, i: usize, j: usize) -> bool {
let i = self.find(i);
let j = self.find(j);
if i != j {
self.parent[i] = j;
self.n -= 1;
true
} else {
false
}
}
}
impl Solution {
fn num_islands2(m: i32, n: i32, positions: Vec<Vec<i32>>) -> Vec<i32> {
let m = m as usize;
let n = n as usize;
let mut uf = UnionFind::new(m * n);
let mut grid = vec![vec![0; n]; m];
let mut group = 0;
let mut res = vec![];
for position in positions {
let r = position[0] as usize;
let c = position[1] as usize;
let i = r * n + c;
if grid[r][c] == 1 {
res.push(group);
continue;
}
grid[r][c] = 1;
group += 1;
if r > 0 && grid[r - 1][c] == 1 {
let j = (r - 1) * n + c;
if uf.union(i, j) {
group -= 1;
}
}
if c > 0 && grid[r][c - 1] == 1 {
let j = r * n + c - 1;
if uf.union(i, j) {
group -= 1;
}
}
if r + 1 < m && grid[r + 1][c] == 1 {
let j = (r + 1) * n + c;
if uf.union(i, j) {
group -= 1;
}
}
if c + 1 < n && grid[r][c + 1] == 1 {
let j = r * n + c + 1;
if uf.union(i, j) {
group -= 1;
}
}
res.push(group);
}
res
}
}
#[test]
fn test() {
let m = 3;
let n = 3;
let positions = vec_vec_i32![[0, 0], [0, 1], [1, 2], [2, 1]];
let res = vec![1, 1, 2, 3];
assert_eq!(Solution::num_islands2(m, n, positions), res);
}
```

Having problems with this solution? Click here to submit an issue on github.