200. Number of Islands

Description

See: https://leetcode.com/problems/number-of-islands/

Note: both m and n must have a length of at least 1.

Observations

We need to find "islands" of 1s in a sea of 0s. If a 1 touches another 1 in the directions up, down, left or right then they are considered to form an island. Note that diagonally touching 1s are not considered to form an island.

Examples

Example 1

grid = [ ["0","0","1"], ["0","1","1"], ["0","1","1"] ]

grid = [
["0","0","1"],
["0","1","1"],
["0","1","1"], 
]

In this example there is 1 island. It is formed by the cells [0,2], [1,2], [1,1], [2,2], [2,1].

The connections can be diagrammed as:

Example 2

grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]

In this example there are 3 islands:

• Island 1: [0,0], [0,1], [1,0] and [1,1]

• Island 2: [2, 2]

• Island 3: [3, 3] and [3, 4]

The connections are diagrammed as:

This is a disconnected graph scenario.

Solutions

Since this is a graph we can use either DFS or BFS to traverse the vertices to determine how many islands there are. This is a disconnected graph, so we will need to iterate through the entire matrix to find the various islands.

I solved the problem using the DFS algorithm and using a Set to keep track of the visited vertices.

After submitting my answer I looked at some of the other solutions in the discussion. Another approach to marking the vertex as visited is to change to value of the vertex itself. So, change it from "1" to "X". Since we are only looking for "1"s an X will be ignored and we won't visit it. This approach saves space on storage as we don't need the Set to track the visited vertices. However, it does mutate the input array, which may not be acceptable.

Using a Set to keep track of visited vertices

My solution using DFS.

class Solution:
    def __dfs(self, grid: List[List[str]], m: int, n: int, visited: Set):
        if m < 0 or n < 0 or m >= len(grid) or n >= len(grid[m]) or grid[m][n] == "0" or (m, n) in visited:
            return
        visited.add((m, n))
        # In the standard DFS algorithm we usually have a for loop to iterate over the adjacent vertices list. Here, we
        # look in the surrounding cells instead. 
        self.__dfs(grid, m + 1, n, visited)
        self.__dfs(grid, m - 1, n, visited)
        self.__dfs(grid, m, n + 1, visited)
        self.__dfs(grid, m, n - 1, visited)

    def numIslands(self, grid: List[List[str]]) -> int:
        num = 0
        visited = set()
        for m in range(len(grid)):
            for n in range(len(grid[m])):
                if (m, n) not in visited and grid[m][n] == "1":
                    num += 1
                    self.__dfs(grid, m, n, visited)
        return num

Time complexity: O(V + E) where V is the number of vertices (here it is m * n), and E is the number of edges.

Space complexity: O(V), the visited vertices are stored in the Set.

Mutating the input matrix to mark visited vertices

I like this solution, if mutating the input grid is acceptable.

class Solution:
    def __dfs(self, grid, m, n, i, j):
        if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1":
            return
        grid[i][j] = "X"
        self.__dfs(grid, m, n, i - 1, j)
        self.__dfs(grid, m, n, i + 1, j)
        self.__dfs(grid, m, n, i, j + 1)
        self.__dfs(grid, m, n, i, j - 1)

    def numIslands(self, grid: List[List[str]]) -> int:
        num = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    num += 1
                    self.__dfs(grid, m, n, i, j)

        return num

Time Complexity: Same as above

Space Complexity: O(1), no additional space is needed.