305.Number of Islands II

Tags: [graph], [island], [BFS], [union_find]

Com: {g}

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

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:

Givenm = 3, n = 3,positions = [[0,0], [0,1], [1,2], [2,1]].
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

We return the result as an array:[1, 1, 2, 3]

Challenge:

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

Solution: Union Find

class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        if not positions:
            return []

        grid = [[0 for _ in xrange(n)] for _ in xrange(m)]

        # union find
        rank = [[0 for _ in xrange(n)] for _ in xrange(m)]
        uf = [[(row, col) for col in xrange(n)] for row in xrange(m)]

        counter = 0
        result = []
        for p in positions:
            row, col = p
            grid[row][col] = 1

            counter += 1

            # top
            if row - 1 >= 0 and grid[row - 1][col] == 1 and self.find(uf, row - 1, col) != self.find(uf, row, col):
                self.union(rank, uf, (row, col), (row - 1, col))
                counter -= 1

            # left
            if col - 1 >= 0 and grid[row][col - 1] == 1 and self.find(uf, row, col - 1) != self.find(uf, row, col):
                self.union(rank, uf, (row, col), (row, col - 1))
                counter -= 1

            # bottom
            if row + 1 < m and grid[row + 1][col] == 1 and self.find(uf, row + 1, col) != self.find(uf, row, col):
                self.union(rank, uf, (row, col), (row + 1, col))
                counter -= 1

            # right
            if col + 1 < n and grid[row][col + 1] == 1 and self.find(uf, row, col + 1) != self.find(uf, row, col):
                self.union(rank, uf, (row, col), (row, col + 1))
                counter -= 1

            result.append(counter)

        return result

    def find(self, uf, row, col):
        # path compression
        if uf[row][col] != uf[uf[row][col][0]][uf[row][col][1]]:
            uf[row][col] = self.find(uf, uf[row][col][0], uf[row][col][1])

        return uf[row][col]

    def union(self, rank, uf, (x_row, x_col), (y_row, y_col)):
        # union by rank

        xx_row, xx_col = self.find(uf, x_row, x_col)
        yy_row, yy_col = self.find(uf, y_row, y_col)

        if rank[xx_row][xx_col] > rank[yy_row][yy_col]:
            (xx_row, xx_col), (yy_row, yy_col) = (yy_row, yy_col), (xx_row, xx_col)

        if rank[xx_row][xx_col] == rank[yy_row][yy_col]:
            rank[yy_row][yy_col] += 1

        uf[xx_row][xx_col] = (yy_row, yy_col)

Revelation:

• Each operation make grid[row][col] = 1, then we check its four neighbors, if (row, col) and its neighbors have different representatives, then we union them and decrease the counter by 1.
• The simple UnionFind can finish the task the in T = O(k*(m*n)), the UnionFind with path compression can finish the task in T = O(k * lg(m*n)), and the UnionFind with both path compression and union by rank can finish the task in O(k * lg*(m*n)).
• UnionFind reference: https://zhaonanli.gitbooks.io/algorithm/content/union-find.html

Note:

• Time complexity = O(m*n + k*log*(m*n)).
• log*(x) means the number of times you need to take log() of x to make x down to 1.