MediumDepth-First SearchRecursionMatrixFlood Fill

Number of Islands

1 approach, code in every language

You are given a 2D grid made of the characters '1' (land) and '0' (water). An island is a maximal group of land cells connected horizontally or vertically, and every island is fully surrounded by water or by the edges of the grid. Diagonal neighbors are not considered connected.

Return the total number of distinct islands in the grid.

Example 1

Input: grid = [ ['1','1','0','0'], ['1','0','0','1'], ['0','0','1','1'], ['0','0','0','0'] ]

Output: 2

The top-left block of land forms one island, and the connected land cells on the right side form the second.

Example 2

Input: grid = [ ['1','0','1'], ['0','0','0'], ['1','0','1'] ]

Output: 4

Each corner cell is isolated by water, so the four land cells count as four separate islands.

Constraints

m == grid.length and n == grid[i].length
1 ≤ m, n ≤ 300
Each cell is either '0' or '1'

DFS Flood Fill

Iterate over every cell; when an unvisited land cell is found, run a depth-first flood fill that sinks the whole island, and increment the island count once per fill.

Loading animation…

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

1Loop through the grid cell by cell from top-left to bottom-right.
2When a cell equal to '1' is reached, add one to the island counter.
3Launch a recursive flood fill from that cell, turning every reachable land cell into '0'.
4The flood fill recurses up, down, left, and right, stopping at grid edges, water, or already-sunk cells.
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

Time

O(m * n) since each cell is examined a constant number of times

Space

O(m * n) worst-case recursion depth when the grid is entirely land

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free