MediumLeetCode #200Graphs
Number of Islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Constraints
m == grid.length, n == grid[i].length, 1 <= m, n <= 300
Examples
Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
Solution
Approach
DFS/BFS: iterate through grid, when finding a '1', increment count and flood fill (mark all connected '1's as visited).
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
return
grid[r][c] = "0"
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
dfs(r, c)
return countComplexity
Time:O(m*n)
Space:O(m*n)
Hints
- 1.Treat grid as graph, cells as nodes
- 2.When you find land, explore all connected land
- 3.Mark visited cells to avoid counting twice
Asked at
Google