LeetCode 200: Number of Islands

Problem Restatement

We are given an m x n grid.

Each cell is one of two characters:

We need to count how many islands exist in the grid.

An island is a group of land cells connected horizontally or vertically. Diagonal connection does not count. The official problem asks for the number of islands in a binary grid of land and water.

Input and Output

Example function shape:

def numIslands(grid: list[list[str]]) -> int:
    ...

Examples

Example 1:

grid = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"],
]

All land cells belong to one connected group.

Output:

1

Example 2:

grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]

There are three separate islands.

Output:

3

First Thought: Scan Every Cell

We can scan the whole grid from top-left to bottom-right.

When we see water, we ignore it.

When we see land, we have found an island.

But that land cell may connect to many other land cells. We must mark the whole island as visited, otherwise we may count the same island again later.

So the process is:

1. Find an unvisited land cell.
2. Count one new island.
3. Visit all land cells connected to it.
4. Continue scanning.

This is a connected components problem on a grid graph.

Key Insight

Each land cell is like a graph node.

Two land cells are connected if they are adjacent in one of four directions:

up, down, left, right

When we find a "1", we use DFS or BFS to visit the entire connected component.

To avoid extra visited memory, we can modify the grid in-place by turning visited land into water:

grid[r][c] = "0"

This is often called sinking the island.

Once an island is sunk, it cannot be counted again.

Algorithm

1. Let rows = len(grid) and cols = len(grid[0]).
2. Initialize islands = 0.
3. Scan every cell (r, c).
4. If grid[r][c] == "1":
   • Increase islands by 1.
   • Run DFS from (r, c) to mark the whole island as visited.
5. Return islands.

DFS Procedure

For a cell (r, c):

1. If the cell is outside the grid, stop.
2. If the cell is water, stop.
3. Mark it as visited by changing it to "0".
4. Visit its four neighbors:
   • (r + 1, c)
   • (r - 1, c)
   • (r, c + 1)
   • (r, c - 1)

Correctness

The main scan finds every cell in the grid.

When it reaches a land cell "1", that cell has not been visited before, because visited land cells are changed to "0".

So this cell must belong to a new island, and increasing the island count is correct.

The DFS visits exactly all land cells connected to the starting cell through horizontal or vertical moves. It changes all of them to "0", so no cell from the same island can start another count later.

Every island has at least one land cell. The first unvisited land cell from that island encountered by the scan will count it once.

Therefore, every island is counted once, and no island is counted more than once.

Complexity

Here, m is the number of rows and n is the number of columns.

The grid itself is modified in-place, so the extra data structure space is only the recursion stack.

Implementation

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        islands = 0

        def dfs(r: int, c: int) -> None:
            if r < 0 or r == rows or c < 0 or c == cols:
                return

            if grid[r][c] == "0":
                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":
                    islands += 1
                    dfs(r, c)

        return islands

Code Explanation

We store the grid dimensions:

rows = len(grid)
cols = len(grid[0])

The answer starts at zero:

islands = 0

The DFS first checks whether the cell is outside the grid:

if r < 0 or r == rows or c < 0 or c == cols:
    return

Then it stops on water:

if grid[r][c] == "0":
    return

If the cell is land, we mark it visited:

grid[r][c] = "0"

Then we explore the four connected directions:

dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)

The outer loops scan every cell:

for r in range(rows):
    for c in range(cols):

When an unvisited land cell is found, we count one island and sink it:

if grid[r][c] == "1":
    islands += 1
    dfs(r, c)

Alternative Implementation With BFS

DFS recursion can be replaced with an explicit queue.

from collections import deque

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        islands = 0

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def bfs(sr: int, sc: int) -> None:
            queue = deque([(sr, sc)])
            grid[sr][sc] = "0"

            while queue:
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if nr < 0 or nr == rows or nc < 0 or nc == cols:
                        continue

                    if grid[nr][nc] == "0":
                        continue

                    grid[nr][nc] = "0"
                    queue.append((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    islands += 1
                    bfs(r, c)

        return islands

BFS avoids recursion depth issues and has the same time complexity.

Testing

def run_tests():
    s = Solution()

    grid = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"],
    ]
    assert s.numIslands(grid) == 1

    grid = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"],
    ]
    assert s.numIslands(grid) == 3

    grid = [["0"]]
    assert s.numIslands(grid) == 0

    grid = [["1"]]
    assert s.numIslands(grid) == 1

    grid = [
        ["1", "0", "1"],
        ["0", "1", "0"],
        ["1", "0", "1"],
    ]
    assert s.numIslands(grid) == 5

    print("all tests passed")

run_tests()

Test meaning: