Number of Islands

DFS flood fill, marking visited land as water

Flood fill with DFS. The grid IS the graph — each cell is a node.

Published Apr 16, 2026

Problem

Given an m × n grid of '1' (land) and '0' (water) characters, return the number of islands. An island is a maximal group of land cells connected 4-directionally (up/down/left/right).

Input

grid = [["1","1","0"],["1","1","0"],["0","0","1"]]

Output

Input

grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]

Output

Intuition

Each island is a connected component. Iterate the grid; whenever you see a '1', increment the counter and flood-fill from that cell to erase the whole component. The loop then only finds the first cell of each island.

"Erase" can mean (a) write '0' in place — zero extra memory, destructive; or (b) maintain a parallel visited grid — non-destructive, O(m · n) extra. Both are equivalent; the mutating version is slightly more cache-friendly.

The flood fill itself can be DFS (call stack or explicit stack) or BFS (queue). Same asymptotic cost; the choice is about stack-overflow safety on very large grids.

Approach

DFS flood fill, in-place marking

TimeO(m·n)

SpaceO(m·n)

Recommended

For every unvisited land cell, increment the count and launch a DFS that writes '0' on every connected land cell. DFS recursion depth can reach m · n in the worst case (spiral-shaped island).

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        let rows = grid.len();
        let cols = grid[0].len();
        let mut grid = grid;
        let mut count = 0;
        fn sink(r: isize, c: isize, rows: usize, cols: usize, grid: &mut Vec<Vec<char>>) {
            if r < 0 || c < 0 || r >= rows as isize || c >= cols as isize {
                return;
            }
            let (rr, cc) = (r as usize, c as usize);
            if grid[rr][cc] != '1' {
                return;
            }
            grid[rr][cc] = '0';
            sink(r + 1, c, rows, cols, grid);
            sink(r - 1, c, rows, cols, grid);
            sink(r, c + 1, rows, cols, grid);
            sink(r, c - 1, rows, cols, grid);
        }
        for r in 0..rows {
            for c in 0..cols {
                if grid[r][c] == '1' {
                    count += 1;
                    sink(r as isize, c as isize, rows, cols, &mut grid);
                }
            }
        }
        count
    }
}

Rust · runnable

function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const sink = (r: number, c: number): void => {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return;
    if (grid[r][c] !== '1') return;
    grid[r][c] = '0';
    sink(r + 1, c);
    sink(r - 1, c);
    sink(r, c + 1);
    sink(r, c - 1);
  };
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        sink(r, c);
      }
    }
  }
  return count;
}

TypeScript · runnable

BFS flood fill with a queue

TimeO(m·n)

SpaceO(min(m,n))

Identical algorithm with BFS. The BFS frontier never exceeds O(min(m, n)) for a rectangular grid — making this the memory-safest option. Prefer on very large inputs.

use std::collections::VecDeque;

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        let rows = grid.len();
        let cols = grid[0].len();
        let mut grid = grid;
        let mut count = 0;
        for r in 0..rows {
            for c in 0..cols {
                if grid[r][c] != '1' {
                    continue;
                }
                count += 1;
                let mut q: VecDeque<(usize, usize)> = VecDeque::new();
                q.push_back((r, c));
                grid[r][c] = '0';
                while let Some((cr, cc)) = q.pop_front() {
                    for (dr, dc) in [(1i32, 0i32), (-1, 0), (0, 1), (0, -1)] {
                        let nr = cr as i32 + dr;
                        let nc = cc as i32 + dc;
                        if nr < 0 || nc < 0 || nr >= rows as i32 || nc >= cols as i32 {
                            continue;
                        }
                        let (nr, nc) = (nr as usize, nc as usize);
                        if grid[nr][nc] == '1' {
                            grid[nr][nc] = '0';
                            q.push_back((nr, nc));
                        }
                    }
                }
            }
        }
        count
    }
}

Rust · runnable

function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ] as const;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      const q: [number, number][] = [[r, c]];
      grid[r][c] = '0';
      let head = 0;
      while (head < q.length) {
        const [cr, cc] = q[head++];
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
          if (grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            q.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

TypeScript · runnable

Trace

Grid: [["1","1","0"],["1","1","0"],["0","0","1"]]

1 1 0       0 0 0       0 0 0
1 1 0  -->  0 0 0  -->  0 0 0
0 0 1       0 0 1       0 0 0
           (sink 4-       (sink 1-
            cell island)   cell island)

step	(r,c)	grid[r][c]	action
1	(0,0)	1	count=1, sink top-left quad
2	(2,2)	1	count=2, sink single cell

Two islands total.

Edge cases

All water — returns 0.
Single cell grid — one island iff it's '1'.
Long thin strip — connected diagonally is NOT connected here (only 4-directional).
Recursion depth — for a snake-shaped single island filling the entire grid, DFS recursion depth is m · n. Use the BFS variant on 1000 × 1000 grids.

Takeaway

Count-components-in-a-grid is one of the most transferrable patterns in the graph track. The same skeleton — outer loop over every cell, start-flood-when-unvisited, increment counter — generalizes to: counting regions, finding max island area (#695), color enclosing regions (#130), and detecting cycles/holes. Once you own the flood fill, these are variations on "what do you increment" and "what do you mark".

Medium#994

Rotting Oranges

Multi-source BFS. All rotten oranges start in the queue simultaneously.

Medium#133

Clone Graph

BFS/DFS with a visited HashMap that maps old → new nodes.

Medium#79

Word Search

2D grid backtracking. Mark visited, explore 4 directions, unmark.