Number of Islands — DFS/BFS Flood Fill

Problem

Given an m x n grid of '1' (land) and '0' (water), return the number of islands.

Example:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints: 1 <= m, n <= 300

Approach — DFS Flood Fill

For each unvisited land cell, start a DFS that marks the entire connected island as visited. Count how many DFS calls are made.

Key insight: mutate grid in-place ('1' → '0') to avoid a separate visited array.

Time: O(mn) | Space: O(mn) recursion stack

Solutions

C

void dfs(char** g, int r, int c, int R, int C) {
    if (r<0||r>=R||c<0||c>=C||g[r][c]!='1') return;
    g[r][c]='0';
    dfs(g,r+1,c,R,C); dfs(g,r-1,c,R,C);
    dfs(g,r,c+1,R,C); dfs(g,r,c-1,R,C);
}
int numIslands(char** g, int R, int* cols) {
    int C=cols[0], count=0;
    for (int r=0;r<R;r++)
        for (int c=0;c<C;c++)
            if (g[r][c]=='1') { dfs(g,r,c,R,C); count++; }
    return count;
}

C++

class Solution {
    void dfs(vector<vector<char>>& g, int r, int c) {
        if (r<0||r>=g.size()||c<0||c>=g[0].size()||g[r][c]!='1') return;
        g[r][c]='0';
        dfs(g,r+1,c); dfs(g,r-1,c); dfs(g,r,c+1); dfs(g,r,c-1);
    }
public:
    int numIslands(vector<vector<char>>& g) {
        int cnt=0;
        for (int r=0;r<g.size();r++)
            for (int c=0;c<g[0].size();c++)
                if (g[r][c]=='1') { dfs(g,r,c); cnt++; }
        return cnt;
    }
};

Java

class Solution {
    private void dfs(char[][] g, int r, int c) {
        if (r<0||r>=g.length||c<0||c>=g[0].length||g[r][c]!='1') return;
        g[r][c]='0';
        dfs(g,r+1,c); dfs(g,r-1,c); dfs(g,r,c+1); dfs(g,r,c-1);
    }
    public int numIslands(char[][] g) {
        int cnt=0;
        for (int r=0;r<g.length;r++)
            for (int c=0;c<g[0].length;c++)
                if (g[r][c]=='1') { dfs(g,r,c); cnt++; }
        return cnt;
    }
}

JavaScript

var numIslands = function(grid) {
    const dfs = (r, c) => {
        if (r<0||r>=grid.length||c<0||c>=grid[0].length||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);
    };
    let cnt=0;
    for (let r=0;r<grid.length;r++)
        for (let c=0;c<grid[0].length;c++)
            if (grid[r][c]==='1') { dfs(r,c); cnt++; }
    return cnt;
};

Python

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        R, C = len(grid), len(grid[0])
        def dfs(r, c):
            if not (0<=r<R and 0<=c<C) or grid[r][c]!='1': return
            grid[r][c]='0'
            for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                dfs(r+dr, c+dc)
        count=0
        for r in range(R):
            for c in range(C):
                if grid[r][c]=='1':
                    dfs(r,c); count+=1
        return count

Complexity

Time: O(m*n) — each cell visited at most once
Space: O(m*n) — recursion depth in worst case (all land)

Key Takeaway

Every "count connected components in a grid" problem uses this exact template. The only variable is the condition for what counts as land.