Number of Islands
Count the number of islands in a grid.
Count connected land components in a grid. The important move is consuming one whole island the moment you find its first land cell.
Pattern fit
The grid is a graph where each land cell connects to adjacent land cells, so the problem is simply counting connected components.
Key observation
Once you discover one land cell, the whole connected component should be consumed in one traversal.
Target complexity
O(mn) / O(mn)
How to break down the solution cleanly
Scan the grid cell by cell.
When you encounter an unvisited land cell, increment the island count.
Run DFS or BFS from that cell to mark the entire connected component.
Continue scanning until every land cell belongs to some visited island.
Walk through one example
If the first row starts a 2x2 land block, that whole block still counts as one island.
DFS will spread through its four-direction neighbors and mark them visited.
The next isolated land region you find starts island count number two.
Reference implementation
Pythondef numIslands(grid: list[list[str]]) -> int:
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
def dfs(row: int, col: int) -> None:
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] != "1":
return
grid[row][col] = "0"
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
islands = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] == "1":
islands += 1
dfs(row, col)
return islands
Common pitfalls
Not marking visited immediately and revisiting the same cell.
Checking only two directions and undercounting islands.
Common follow-ups
How would a union-find solution differ?
What changes if diagonal neighbors also connect?
Continue with related problems
Build repeatable depth inside the BFS / DFS cluster before moving on.