## 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 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 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 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 into a land.

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

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

Thoughts:

1. Union-find:UNION operation`O(1)`. FIND
operation is proportional to the depth of the tree. If N is the number of points added, the average running time is `O(logN)`, and a sequence of `4N`operations take `O(NlogN)`. If there is no balancing, the worse case could be `O(N^2)`.

2. Improvements:

1. Path Compression: change the parent in the finding when the parent is not the root
2. Union by rank:
1. if rank a > rank b: then parent[b] = a
2. if rank a < rank b: then parent[a] = b
3. else make parent either way and just increase the rank of the parent one

Code:

``````class Solution(object):
def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""
def find(parent, val):
while parent[val] != val:
'''
Path Compression:

parent[val] = parent[parent[val]]
'''
val = parent[val]
return val

def union(x, y):
'''
Union by Rank:

if rank[x] > rank[y]:
x, y =  y, x
rank[y] += rank[x] == rank[y]

'''
parent[find(x)] = find(y)
return find(y)

parent ,  rank =  [-1] * (m * n),  * (m * n)
d = [0, 1 , 0 , -1, 0]
cnt = 0
ans = []

if m < 1 or n < 1:
return []

for pos in positions:
cnt += 1
root = n * pos + pos
parent[root] = root

# expanding its neightbor: once find there is a island, connect them
for i in range(4):
x , y = pos + d[i] , pos + d[i + 1]
nb = x * n + y
if x >= 0 and x < m and y >= 0 and y < n and parent[nb] != -1:
rootN = find(parent, nb)
if root != rootN:
root = union (root, rootN)

cnt -= 1
ans.append(cnt)

return ans
``````