Number of Islands

Intuition

Every island is a connected region of '1' cells. If we scan the grid and stop at the first land cell we have not yet seen, that cell must belong to a brand-new island, so we increase the counter. We then flood the entire island by recursively visiting its four-directional land neighbors and marking each as water so it is never counted again. Because the flood fill consumes an entire island before the outer loop moves on, each island is discovered exactly once.

Algorithm walkthrough

1. 1Loop through the grid cell by cell from top-left to bottom-right.
2. 2When a cell equal to '1' is reached, add one to the island counter.
3. 3Launch a recursive flood fill from that cell, turning every reachable land cell into '0'.
4. 4The flood fill recurses up, down, left, and right, stopping at grid edges, water, or already-sunk cells.
5. 5Continue the outer scan; since flooded cells are now '0', only genuinely new islands trigger another count.

Implementation

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

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

        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count