# 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"] ]`

```python
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:

![](https://4048269476-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F6JbWoYwqVgAwosJzOAwN%2Fuploads%2FUmrWy2Q1TMbCAs6kKlaQ%2F200_number_of_islands.svg?alt=media\&token=35374385-df41-4714-bfd2-5271642738c5)

#### Example 2

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

```python
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:

![](https://4048269476-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F6JbWoYwqVgAwosJzOAwN%2Fuploads%2FfsS88bBeRoI1dPzcyWHY%2F200_number_of_islands_2.svg?alt=media\&token=2881866f-7825-4fb5-bd2c-a42cd11dd39e)

This is a [disconnected graph](https://monica-granbois.gitbook.io/cs-theory-and-problems/data-structures/graph#connected-graph) scenario.

## Solutions

Since this is a [graph](https://monica-granbois.gitbook.io/cs-theory-and-problems/data-structures/graph) we can use either[ DFS](https://monica-granbois.gitbook.io/cs-theory-and-problems/algorithms/depth-first-search-dfs) or [BFS](https://monica-granbois.gitbook.io/cs-theory-and-problems/algorithms/breadth-first-search-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.&#x20;

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.

```python
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.

```python
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.