200.Number of Islands

Tags: [BFS], [DFS], [island]

Com: {fb}, {g}

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

Given a 2d grid map of'1's (land) and'0's (water), count the number of islands. 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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Better Solution: DFS

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        num_of_rows = len(grid)
        num_of_cols = len(grid[0])

        counter = 0
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if grid[row][col] == '1':
                   counter += 1
                   self.dfs(grid, num_of_rows, num_of_cols, row, col)

        return counter

    def dfs(self, grid, num_of_rows, num_of_cols, row, col):
        VISITED_MARK = '100'
        grid[row][col] = VISITED_MARK

        # top
        if row - 1 >= 0 and grid[row - 1][col] == '1':
            self.dfs(grid, num_of_rows, num_of_cols, row - 1, col)

        # left
        if col - 1 >= 0 and grid[row][col - 1] == '1':
            self.dfs(grid, num_of_rows, num_of_cols, row, col - 1)

        # bottom
        if row + 1 < num_of_rows and grid[row + 1][col] == '1':
            self.dfs(grid, num_of_rows, num_of_cols, row + 1, col)

        # right
        if col + 1 < num_of_cols and grid[row][col + 1] == '1':
            self.dfs(grid, num_of_rows, num_of_cols, row, col + 1)

Revelation:

• Assuming we can modify the grid.

Note:

• Time complexity = O(num_of_rows * num_of_cols), because each cell we only visited once.

Solution: DFS

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        num_of_rows = len(grid)
        num_of_cols = len(grid[0])

        counter = 0
        visited = [[False for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if visited[row][col] or grid[row][col] == '0':
                    continue

                # debug:
                print 'debug:[{}][{}]={}, counter={}'.format(row, col, grid[row][col], counter)

                counter += 1
                visited[row][col] = True
                self.dfs(grid, num_of_rows, num_of_cols, row, col, visited)

        return counter

    def dfs(self, grid, num_of_rows, num_of_cols, row, col, visited):
        # check four directions.
        # top
        if row - 1 >= 0 and grid[row - 1][col] == '1' and not visited[row - 1][col]:
            visited[row - 1][col] = True
            self.dfs(grid, num_of_rows, num_of_cols, row - 1, col, visited)

        # left
        if col - 1 >= 0 and grid[row][col - 1] == '1' and not visited[row][col - 1]:
            visited[row][col - 1] = True
            self.dfs(grid, num_of_rows, num_of_cols, row, col - 1, visited)

        # bottom
        if row + 1 < num_of_rows and grid[row + 1][col] == '1' and not visited[row + 1][col]:
            visited[row + 1][col] = True
            self.dfs(grid, num_of_rows, num_of_cols, row + 1, col, visited)

        # right
        if col + 1 < num_of_cols and grid[row][col + 1] == '1' and not visited[row][col + 1]:
            visited[row][col + 1] = True
            self.dfs(grid, num_of_rows, num_of_cols, row, col + 1, visited)

Revelation:

• The 'label island' approach seems doesn't work.

Note:

• Time complexity of above solution = O(num_of_rows * num_of_cols), because each cell of the grid, we only visited once.

Time Limited Exceeded: BFS

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        num_of_rows = len(grid)
        num_of_cols = len(grid[0])

        counter = 0
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if grid[row][col] == '1':
                   counter += 1
                   self.bfs(grid, num_of_rows, num_of_cols, row, col)

        return counter

    def bfs(self, grid, num_of_rows, num_of_cols, row, col):
        VISITED_MARK = '100'
        queue = collections.deque()
        queue.append((row, col))

        while queue:
            row, col = queue.popleft()
            grid[row][col] = VISITED_MARK

            # top
            if row - 1 >= 0 and grid[row - 1][col] == '1':
                queue.append((row - 1, col))

            # left
            if col - 1 >= 0 and grid[row][col - 1] == '1':
                queue.append((row, col - 1))

            # bottom
            if row + 1 < num_of_rows and grid[row + 1][col] == '1':
                queue.append((row + 1, col))

            # right
            if col + 1 < num_of_cols and grid[row][col + 1] == '1':
                queue.append((row, col + 1))

Revelation:

• Not sure why BFS is slower than DFS.

Note:

• Time complexity = O(num_of_rows * num_of_cols), because each cell we only visited once.