Number of islands (flood fill)

Count groups of connected land cells in a grid. A grid is a graph where each cell links to its four neighbours.

Time O(rows × cols)Space O(rows × cols)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Scan the grid. Each time you hit unvisited land, you have found a new island: count it, then flood outward with DFS to mark every cell of that island so it is not counted again.

Code

C++PythonC#

void sink(vector<vector<char>>& g, int r, int c) {
    if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] != '1') return;
    g[r][c] = '0'; // mark as visited
    sink(g, r + 1, c); sink(g, r - 1, c);
    sink(g, r, c + 1); sink(g, r, c - 1);
}

int countIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int r = 0; r < (int)grid.size(); r++)
        for (int c = 0; c < (int)grid[0].size(); c++)
            if (grid[r][c] == '1') { count++; sink(grid, r, c); }
    return count;
}

def count_islands(grid: list[list[str]]) -> int:
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1': count += 1; sink(grid, r, c)
    return count

def sink(g: list[list[str]], r: int, c: int) -> None:
    if r < 0 or c < 0 or r >= len(g) or c >= len(g[0]) or g[r][c] != '1': return
    g[r][c] = '0'  # mark as visited
    sink(g, r + 1, c); sink(g, r - 1, c)
    sink(g, r, c + 1); sink(g, r, c - 1)

public static int CountIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.Length; r++)
        for (int c = 0; c < grid[0].Length; c++)
            if (grid[r][c] == '1') { count++; Sink(grid, r, c); }
    return count;
}

static void Sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.Length || c >= g[0].Length || g[r][c] != '1') return;
    g[r][c] = '0'; // mark as visited
    Sink(g, r + 1, c); Sink(g, r - 1, c);
    Sink(g, r, c + 1); Sink(g, r, c - 1);
}

Tips

The bounds check comes first in Sink, so the recursive calls never need to check before calling.
If you must not modify the input, track visited cells in a bool[,] instead.

In the .NET library

char[][] is a jagged array (array of arrays). A rectangular char[,] also works and uses grid.GetLength(0) and GetLength(1) for the sizes.