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 or BFS to mark connected land cells. Increment counter for each new island.
Implementation
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def dfs(i, j):
if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == "0":
return
grid[i][j] = "0"
dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == "1":
islands += 1
dfs(i, j)
return islandsComplexity Analysis
Time Complexity
O(V + E)Space Complexity
O(V)Key Learning Points
Use queue for level-order traversalMaintain visited setProcess all neighbors at current level before next
Related Problems to Practice
Number of IslandsWalls and GatesShortest Path
Complexity
Time:O(V + E)
Space:O(V)
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