Number of Islands
Count connected groups in a grid, and see why marking a cell as visited the moment you reach it is the whole algorithm
Problem Statement
Given a 2D grid of '1' (land) and '0' (water), count the number of islands.
An island is land connected horizontally or vertically — diagonals do not connect. Assume the grid is surrounded by water on all sides.
Input:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Output: 3Intuition
A grid is a graph in disguise. Each cell is a node, and each cell is connected to the neighbour above, below, left and right. Once you see that, this becomes a standard question: how many connected groups are there?
And there is a simple way to count connected groups in any graph.
The key insight
Walk the grid cell by cell. When you find land you have not seen before, you have found a new island — so add one to the count.
Then immediately erase that entire island, by walking every piece of land connected to it and marking it visited.
Because the whole island is now consumed, none of its other cells can ever start a second count.
The counting and the erasing work together. Without the erase, a 2×2 block of land would be counted four times. Without the count, you would just be wandering.
The real-world version
You have a map and a marker pen. You scan it left to right, top to bottom. The first time you hit an unpainted patch of land, you shout "one!" and then paint that entire landmass solid — following it wherever it goes.
You keep scanning. Painted land is ignored. Every shout is a new island.
Approach
Scan every cell
Two nested loops over rows and columns. Most cells will do nothing.
If the cell is water or already visited, skip it
This is what stops one island being counted more than once.
Otherwise, increment the count
You have just discovered a new island. It has at least this one cell.
Flood the whole island
From this cell, visit all four neighbours, and their neighbours, and so on — stopping at water and at the grid edge. Mark each one visited.
When the flood finishes, the entire island is consumed.
Mark visited when you ENTER a cell, not when you leave
This one line decides whether the solution works.
If you mark a cell only after exploring its neighbours, then cell A explores B, and B explores A right back — because A is not marked yet. The recursion bounces between them until the stack overflows.
Marking on entry means a cell can never be entered twice, which both prevents the loop and makes the whole thing O(rows × cols).
Watch it run
Solution
def num_islands(grid: list[list[str]]) -> int:
"""Count connected groups of '1' cells, joined horizontally or vertically."""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def sink(row: int, col: int) -> None:
"""Erase the island containing (row, col)."""
# One guard covers both the grid edge and water.
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] != "1":
return
# Mark visited on ENTRY, before recursing. This is what stops
# two adjacent cells exploring each other forever.
grid[row][col] = "0"
sink(row + 1, col)
sink(row - 1, col)
sink(row, col + 1)
sink(row, col - 1)
for row in range(rows):
for col in range(cols):
if grid[row][col] == "1":
count += 1 # a new island
sink(row, col) # consume all of it
return count
def num_islands_bfs(grid: list[list[str]]) -> int:
"""BFS version — safe on very large grids, where recursion would overflow."""
from collections import deque
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] != "1":
continue
count += 1
grid[row][col] = "0"
queue = deque([(row, col)])
while queue:
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
# Mark when ENQUEUEING, not when dequeueing — otherwise
# the same cell can be added to the queue many times.
grid[nr][nc] = "0"
queue.append((nr, nc))
return countMark on enqueue, not on dequeue
The BFS version has its own version of the same trap. If you mark a cell visited only when you pop it from the queue, the same cell can be pushed several times before it is ever popped — once by each neighbour.
The result is still correct, but the queue can grow to many times the grid size, and on a large grid that is a memory blowout.
Complexity Analysis
Time Complexity
O(rows × cols)
Space Complexity
O(rows × cols)
- Time — the outer scan touches every cell once, and the flood touches each land cell once. No cell is ever processed twice, because it is marked the instant it is reached. So the total is linear in the number of cells.
- Space — for DFS this is the recursion stack. The worst case is a grid that is entirely land, where the flood can nest as deep as the cell count.
When to prefer BFS here
For a 1000 × 1000 grid of solid land, the DFS version needs up to one million nested calls. Python raises RecursionError and JavaScript throws RangeError.
The BFS version keeps its frontier in a queue on the heap, so it survives. When grid dimensions are large, reach for BFS.
Edge Cases
Related Problems
- Course Schedule — a graph where the edges are given directly rather than implied by a grid
- Find the Town Judge — a graph problem needing no traversal at all
- Binary Tree Level Order Traversal — the same BFS shape on a tree
- Graphs — representations, and why a visited set is required