200. Number of Islands
Note: both m and n must have a length of at least 1.
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.
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:
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:
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.
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.
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.
Last modified 1yr ago