305. Number of Islands II

A 2d grid map of mrows and ncolumns 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 gridgridis 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?

Thoughts:

1. Union-find:UNION operationO(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 4Noperations 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), [0] * (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[0] + pos[1]
            parent[root] = root

            # expanding its neightbor: once find there is a island, connect them
            for i in range(4):
                x , y = pos[0] + d[i] , pos[1] + 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