## Description

https://leetcode.com/problems/number-of-islands-ii/

You are given an empty 2D binary grid `grid`

of size `m x n`

. The grid represents a map where `0`

‘s represent water and `1`

‘s represent land. Initially, all the cells of `grid`

are water cells (i.e., all the cells are `0`

‘s).

We may perform an add land operation which turns the water at position into a land. You are given an array `positions`

where `positions[i] = [r`

is the position _{i}, c_{i}]`(r`

at which we should operate the _{i}, c_{i})`i`

operation.^{th}

Return *an array of integers* `answer`

*where* `answer[i]`

*is the number of islands after turning the cell* `(r`

_{i}, c_{i})*into a land*.

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 1:**

Input:m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]Output:[1,1,2,3]Explanation:Initially, the 2d grid is filled with water. - Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land. We have 1 island. - Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land. We still have 1 island. - Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land. We have 2 islands. - Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land. We have 3 islands.

**Example 2:**

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

**Constraints:**

`1 <= m, n, positions.length <= 10`

^{4}`1 <= m * n <= 10`

^{4}`positions[i].length == 2`

`0 <= r`

_{i}< m`0 <= c`

_{i}< n

**Follow up:** Could you solve it in time complexity `O(k log(mn))`

, where `k == positions.length`

?

## Explanation

Use union-find data structure to help solve the problem. Whenever we make a position to island, we also use union-find to link its neighbors so that the next time if we visit any of neighbor positions, we know it belongs to the same island.

## Python Solution

```
class UnionFind:
def __init__(self):
self.father = {}
self.count = 0
def union(self, a, b):
root_a = self.find(a)
root_b = self.find(b)
if root_a == root_b:
return
self.father[root_b] = root_a
self.count -= 1
def find(self, point):
path = []
while point != self.father[point]:
path.append(point)
point = self.father[point]
for p in path:
self.father[p] = point
return point
class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
islands = set()
results = []
union_find = UnionFind()
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
for position in positions:
x, y = position[0], position[1]
if (x, y) in islands:
results.append(union_find.count)
continue
islands.add((x, y))
union_find.father[(x, y)] = (x, y)
union_find.count += 1
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (nx, ny) in islands:
union_find.union((x, y), (nx, ny))
results.append(union_find.count)
return results
```

- Time Complexity: O(m * n + L), where L is the number of operations.
- Space Complexity: O(m *n ).