Number Of Islands

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Approach

BFS flood fill. Iterate every cell; when a '1' is found, increment the island counter and BFS to mark all connected land as visited.

When to Use

Connected components / flood fill — "count islands", "count regions", "label connected areas". BFS/DFS from each unvisited cell. Geospatial: land-use classification, satellite imagery segmentation.

Complexity

Time	O(m * n) — each cell visited at most once
Space	O(m * n) — visited set (or O(min(m, n)) BFS queue)

Implementation

SolutionTestsChallenge

number_of_islands

Count islands in a 2D grid of '1's (land) and '0's (water).

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Approach

BFS flood fill. Iterate every cell; when a '1' is found, increment the island counter and BFS to mark all connected land as visited.

When to use

Connected components / flood fill — "count islands", "count regions", "label connected areas". BFS/DFS from each unvisited cell. Geospatial: land-use classification, satellite imagery segmentation.

Complexity

Time: O(m * n) — each cell visited at most once Space: O(m * n) — visited set (or O(min(m, n)) BFS queue)

num_islands

num_islands(grid: list[list[str]]) -> int

Return the number of islands in grid.

num_islands([["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]]) 2

Source code in src/algo/graphs/number_of_islands.py

def num_islands(grid: list[list[str]]) -> int:
    """Return the number of islands in *grid*.

    >>> num_islands([["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]])
    2
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited: set[tuple[int, int]] = set()
    count = 0

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

    return count

tests/graphs/test_number_of_islands.py

"""Tests for the number of islands problem."""

from algo.graphs.number_of_islands import num_islands


class TestNumIslands:
    def test_single_island(self) -> None:
        grid = [
            ["1", "1", "1"],
            ["0", "1", "0"],
            ["0", "0", "0"],
        ]
        assert num_islands(grid) == 1

    def test_two_islands(self) -> None:
        grid = [
            ["1", "1", "0", "0", "0"],
            ["1", "1", "0", "0", "0"],
            ["0", "0", "1", "0", "0"],
            ["0", "0", "0", "1", "1"],
        ]
        assert num_islands(grid) == 3

    def test_all_water(self) -> None:
        grid = [["0", "0"], ["0", "0"]]
        assert num_islands(grid) == 0

    def test_all_land(self) -> None:
        grid = [["1", "1"], ["1", "1"]]
        assert num_islands(grid) == 1

    def test_empty_grid(self) -> None:
        assert num_islands([]) == 0
        assert num_islands([[]]) == 0

    def test_single_cell(self) -> None:
        assert num_islands([["1"]]) == 1
        assert num_islands([["0"]]) == 0

Implement it yourself

Run: just challenge graphs number_of_islands

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

number_of_islands

Count islands in a 2D grid of '1's (land) and '0's (water).

Problem

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Approach

BFS flood fill. Iterate every cell; when a '1' is found, increment the island counter and BFS to mark all connected land as visited.

When to use

Connected components / flood fill — "count islands", "count regions", "label connected areas". BFS/DFS from each unvisited cell. Geospatial: land-use classification, satellite imagery segmentation.

Complexity

Time: O(m * n) — each cell visited at most once Space: O(m * n) — visited set (or O(min(m, n)) BFS queue)

num_islands

num_islands(grid: list[list[str]]) -> int

Return the number of islands in grid.

num_islands([["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]]) 2

Source code in src/algo/graphs/number_of_islands.py

def num_islands(grid: list[list[str]]) -> int:
    """Return the number of islands in *grid*.

    >>> num_islands([["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]])
    2
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited: set[tuple[int, int]] = set()
    count = 0

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

    return count