200. Number of Islands

Reformulated question¶

Count how many connected groups of '1' exist in a 2D grid, where cells connect only up, down, left, and right.

Example:

grid =
1 1 0
0 1 0
1 0 1

islands = 3
# groups: {(0,0),(0,1),(1,1)}, {(2,0)}, {(2,2)}

Key trick¶

Scan every cell once, and when you find an unvisited land cell, flood-fill its whole island with DFS or BFS and increment the answer.

Trap¶

Diagonal cells do not connect.
Forgetting to mark visited causes double counting.
Recursive DFS can hit Python recursion limits on large grids.
Using a separate starting_nodes list is unnecessary extra work.

Why is this question interesting?¶

It is the basic grid-to-graph pattern: detect connected components by turning each land cell into a node and flood-filling once per component.

Solve the problem with idiomatic python¶

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

        def dfs(r: int, c: int) -> None:
            # Stop on out-of-bounds, water, or already-visited cells.
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if grid[r][c] != "1":
                return

            # Mark visited by sinking land into water.
            grid[r][c] = "0"

            # Visit 4-directionally connected land.
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)

        islands = 0

        for r in range(rows):
            for c in range(cols):
                # First cell of a new island.
                if grid[r][c] == "1":
                    islands += 1
                    dfs(r, c)

        return islands

Time: \(O(mn)\)
Space:
- Recursive DFS: up to \(O(mn)\) in worst case call stack
- If counting mutation only: \(O(1)\) extra grid storage

Pytest test¶

import pytest


class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows = len(grid)
        cols = len(grid[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] != "1":
                return

            # Mark as visited in-place to avoid a separate set.
            grid[r][c] = "0"

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

        islands = 0

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

        return islands


@pytest.mark.parametrize(
    ("grid", "expected"),
    [
        (
            [
                ["1", "1", "1", "1", "0"],
                ["1", "1", "0", "1", "0"],
                ["1", "1", "0", "0", "0"],
                ["0", "0", "0", "0", "0"],
            ],
            1,
        ),
        (
            [
                ["1", "1", "0", "0", "0"],
                ["1", "1", "0", "0", "0"],
                ["0", "0", "1", "0", "0"],
                ["0", "0", "0", "1", "1"],
            ],
            3,
        ),
        (
            [["0"]],
            0,
        ),
        (
            [["1"]],
            1,
        ),
        (
            [
                ["1", "0", "1", "0"],
                ["0", "1", "0", "1"],
                ["1", "0", "1", "0"],
            ],
            6,
        ),
        (
            [
                ["1", "1", "1"],
                ["1", "1", "1"],
            ],
            1,
        ),
    ],
)
def test_numIslands(grid, expected):
    # Copy because solution mutates the grid in-place.
    copied = [row[:] for row in grid]
    assert Solution().numIslands(copied) == expected

Comment my solution¶

It is correct and clear enough for interview use.
The main issue is the comment says BFS, but the code is DFS.
Building starting_nodes first makes a full extra pass and extra memory for no benefit.
Using a visited set works, but in-place marking is simpler and usually preferred here.
Recursive DFS is concise, but on a 300 x 300 all-land grid it may exceed Python recursion depth.
A strong interview version is:
- one pass
- start flood-fill immediately on each '1'
- mark visited in-place
- mention iterative DFS/BFS if recursion depth is a concern

## Solution
# WORKS
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        # multi source BFS starting on "1" (not visited) cells expanding
        # to neighbors, one layer at time stopping when layer contains
        # only zeroes or visited cells.
        # We keep a set of visited node.
        # We count how many "1" non visited we can BFS
        m = len(grid)
        n = len(grid[0])

        starting_nodes = []

        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    starting_nodes.append((i,j))

        def expand(i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return
            if (i, j) in visited or grid[i][j] == "0":
                return
            visited.add((i, j))
            expand(i - 1, j)
            expand(i + 1, j)
            expand(i, j - 1)
            expand(i, j + 1)

        count = 0
        visited = set()
        for i, j in starting_nodes:
            if (i, j) in visited:
                continue
            count += 1
            expand(i, j)

        return count

A tighter version close to yours:

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

        def expand(r: int, c: int) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if grid[r][c] != "1":
                return

            grid[r][c] = "0"
            expand(r - 1, c)
            expand(r + 1, c)
            expand(r, c - 1)
            expand(r, c + 1)

        count = 0

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

        return count