# LeetCode 305. Number of Islands II

## 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] = [ri, ci]` is the position `(ri, ci)` at which we should operate the `ith` operation.

Return an array of integers `answer` where `answer[i]` is the number of islands after turning the cell `(ri, ci)` 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 into a land. We have 1 island.
- Operation #2: addLand(0, 1) turns the water at grid into a land. We still have 1 island.
- Operation #3: addLand(1, 2) turns the water at grid into a land. We have 2 islands.
- Operation #4: addLand(2, 1) turns the water at grid into a land. We have 3 islands.
```

Example 2:

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

Constraints:

• `1 <= m, n, positions.length <= 104`
• `1 <= m * n <= 104`
• `positions[i].length == 2`
• `0 <= ri < m`
• `0 <= ci < 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, position

if (x, y) in islands:

results.append(union_find.count)

continue

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 ).