Number of Islands

[norangmangto]

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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

[norangmangto]

We can use DFS or BFS to solve this question.

I usually use BFS to solve such question. So I used BFS first.

My first BFS solution is below.

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

        res = 0
        for i in range(len(grid)):  # row
            for j in range(len(grid[i])):  # column
                if grid[i][j] == '1':
                    res += 1
                    self.remove_island(grid, i, j)

        return res

    def remove_island(self, grid, i, j):
        res = 0
        queue = [(i, j)]
        while queue:
            x, y = queue.pop(0)
            if grid[x][y] == '1':
                res += 1
                grid[x][y] = '0'
                if y-1 >= 0: queue.append((x, y-1))  # left
                if y+1 < len(grid[x]): queue.append((x, y+1))  # right
                if x-1 >= 0: queue.append((x-1, y))  # up
                if x+1 < len(grid): queue.append((x+1, y))  # down

        return res

[norangmangto]

My DFS solution is below.

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

        no_of_islands = 0
        max_size = 0
        for i in range(len(grid)):  # column
            for j in range(len(grid[i])):  # row
                size = self.dfs(grid, i, j)
                if size > 0:
                    no_of_islands += 1
                    if max_size < size:
                        max_size = size

        return no_of_islands

    def dfs(self, grid, x, y):
        if grid[x][y] == '0':
            return 0

        size_of_island = 1
        grid[x][y] = '0'
        if y-1 >= 0: size_of_island += self.dfs(grid, x, y-1)  # left
        if y+1 < len(grid[x]): size_of_island += self.dfs(grid, x, y+1)  # right
        if x-1 >= 0: size_of_island += self.dfs(grid, x-1, y)  # up
        if x+1 < len(grid): size_of_island += self.dfs(grid, x+1, y)  # down

        return size_of_island

[norangmangto]

I updated bfs solution like below. (updated to get the size of the biggest island)

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

        no_of_islands = 0
        max_size = 0
        for i in range(len(grid)):  # column
            for j in range(len(grid[i])):  # row
                size = self.bfs(grid, i, j)
                if size > 0:
                    no_of_islands += 1
                    if max_size < size:
                        max_size = size

        return no_of_islands

    def bfs(self, grid, i, j):
        size = 0
        queue = [(i, j)]
        while queue:
            x, y = queue.pop(0)
            if grid[x][y] == '1':
                size += 1
                grid[x][y] = '0'
                if y-1 >= 0: queue.append((x, y-1))  # left
                if y+1 < len(grid[x]): queue.append((x, y+1))  # right
                if x-1 >= 0: queue.append((x-1, y))  # up
                if x+1 < len(grid): queue.append((x+1, y))  # down

        return size

[norangmangto]

There is another solution using UnionFind data structure (aka Disjoint Set) from leetcode solution

I will solve this again using that solution.