# 200. Number of Islands
## Description
See:
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:
#### 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:
This is a [disconnected graph](/cs-theory-and-problems/data-structures/graph.md#connected-graph) scenario.
## Solutions
Since this is a [graph](/cs-theory-and-problems/data-structures/graph.md) we can use either[ DFS](/cs-theory-and-problems/algorithms/depth-first-search-dfs.md) or [BFS](/cs-theory-and-problems/algorithms/breadth-first-search-bfs.md) 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.
```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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/200.-number-of-islands.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.