Data Structures
powered by pagefind esc close · ↑↓ navigate · ↵ open
practice · medium · from Graphs

Number of Islands

time
O(rows · cols)
space
O(rows · cols)
tags
graphs · grid · dfs · connected-components

in the wild Connected-component segmentation on an occupancy grid (which clumps of obstacles form one object?), region-counting in image masks, flood-fill in paint tools.

Problem

You're given an m × n grid where each cell is '1' (land) or '0' (water). Two land cells belong to the same island if they're adjacent horizontally or vertically (not diagonally). Land at the grid's edge is bordered by water. Return the number of islands.

Examples

[['1','1','1','1','0'],
 ['1','1','0','1','0'],
 ['1','1','0','0','0'],
 ['0','0','0','0','0']]                  → 1   (all land is connected)

[['1','1','0','0','0'],
 ['1','1','0','0','0'],
 ['0','0','1','0','0'],
 ['0','0','0','1','1']]                  → 3

[['0']]                                  → 0

Why this is the canonical "grid as graph" problem

A grid is just a graph in disguise: every cell is a vertex; adjacent cells (4-connectivity) are connected by edges. "Count the islands" = "count the connected components".

Standard recipe for counting connected components:

  1. Walk every vertex.
  2. When you hit one that's unvisited and qualifies (= '1'), increment your counter and flood-fill from it (DFS or BFS), marking every reachable land cell as visited.
  3. Continue. Each flood-fill colors exactly one component.

Each cell is touched a constant number of times → O(m · n). The choice between DFS and BFS is taste — DFS recursion is shorter; BFS uses an explicit queue and avoids stack overflow on huge grids.

This template generalizes to: "find the largest island", "perimeter of an island", "color all enclosed regions" (LeetCode "Surrounded Regions" — same flood-fill, different starting points), and "count distinct islands by shape" (canonicalize each flood-fill's coordinate set).

Hints

Hint 1 — what is the underlying graph?

Stop thinking "2D grid". Think: each land cell is a node; an edge exists between two land cells iff they're vertically or horizontally adjacent. What classical graph question equals "how many islands"?

Hint 2 — flood fill

Once you've spotted a land cell that hasn't been visited, you want to mark all land cells connected to it as one island. The two ways: recursive DFS (4 neighbors), or BFS with a queue. Either is fine.

Hint 3 — mutate the grid as your visited marker

You don't need a separate visited array. Just write '0' over each visited cell. Saves space; simplifies code. (If the caller doesn't want the grid mutated, copy first.)

Solution

def num_islands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != "1":
            return
        grid[r][c] = "0"                        # mark visited
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

    count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)
    return count

def deep_copy(g): return [row[:] for row in g]

cases = [
    ([['1','1','1','1','0'],
      ['1','1','0','1','0'],
      ['1','1','0','0','0'],
      ['0','0','0','0','0']], 1),
    ([['1','1','0','0','0'],
      ['1','1','0','0','0'],
      ['0','0','1','0','0'],
      ['0','0','0','1','1']], 3),
    ([['0']], 0),
]
for grid, expected in cases:
    got  = num_islands(deep_copy(grid))
    mark = "✓" if got == expected else "✗"
    print(f"{mark} num_islands(...) = {got}  (expected {expected})")
function numIslands(grid) {
  if (!grid.length || !grid[0].length) return 0;
  const m = grid.length, n = grid[0].length;

  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || 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 count = 0;
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (grid[r][c] === '1') { count++; dfs(r, c); }
  return count;
}

const deepCopy = g => g.map(row => row.slice());
const cases = [
  [[['1','1','1','1','0'],
    ['1','1','0','1','0'],
    ['1','1','0','0','0'],
    ['0','0','0','0','0']], 1],
  [[['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']], 3],
  [[['0']], 0],
];
for (const [grid, expected] of cases) {
  const got = numIslands(deepCopy(grid));
  console.log(`${got === expected ? "✓" : "✗"} numIslands(...) = ${got}  (expected ${expected})`);
}
pub fn num_islands(grid: &mut Vec<Vec<char>>) -> i32 {
    if grid.is_empty() || grid[0].is_empty() { return 0; }
    let (m, n) = (grid.len(), grid[0].len());

    // Iterative DFS — avoids Rust's recursion + mut-borrow dance.
    fn flood(grid: &mut Vec<Vec<char>>, r: usize, c: usize, m: usize, n: usize) {
        let mut stack = vec![(r, c)];
        while let Some((r, c)) = stack.pop() {
            if grid[r][c] != '1' { continue; }
            grid[r][c] = '0';
            if r + 1 < m            { stack.push((r + 1, c)); }
            if r > 0                { stack.push((r - 1, c)); }
            if c + 1 < n            { stack.push((r, c + 1)); }
            if c > 0                { stack.push((r, c - 1)); }
        }
    }

    let mut count = 0;
    for r in 0..m {
        for c in 0..n {
            if grid[r][c] == '1' {
                count += 1;
                flood(grid, r, c, m, n);
            }
        }
    }
    count
}

fn main() {
    let mut g1: Vec<Vec<char>> = vec![
        "11110".chars().collect(),
        "11010".chars().collect(),
        "11000".chars().collect(),
        "00000".chars().collect(),
    ];
    let mut g2: Vec<Vec<char>> = vec![
        "11000".chars().collect(),
        "11000".chars().collect(),
        "00100".chars().collect(),
        "00011".chars().collect(),
    ];
    let mut g3: Vec<Vec<char>> = vec![vec!['0']];
    println!("{} num_islands(g1) = {}  (expected 1)", if num_islands(&mut g1) == 1 { "✓" } else { "✗" }, "...");
    println!("{} num_islands(g2) = {}  (expected 3)", if num_islands(&mut g2) == 3 { "✓" } else { "✗" }, "...");
    println!("{} num_islands(g3) = {}  (expected 0)", if num_islands(&mut g3) == 0 { "✓" } else { "✗" }, "...");
}
#include <iostream>
#include <vector>

void dfs(std::vector<std::vector<char>>& grid, int r, int c, int m, int n) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') return;
    grid[r][c] = '0';
    dfs(grid, r + 1, c, m, n);
    dfs(grid, r - 1, c, m, n);
    dfs(grid, r, c + 1, m, n);
    dfs(grid, r, c - 1, m, n);
}

int num_islands(std::vector<std::vector<char>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int m = (int)grid.size(), n = (int)grid[0].size(), count = 0;
    for (int r = 0; r < m; ++r)
        for (int c = 0; c < n; ++c)
            if (grid[r][c] == '1') { ++count; dfs(grid, r, c, m, n); }
    return count;
}

int main() {
    std::vector<std::vector<char>> g1 = {
        {'1','1','1','1','0'},
        {'1','1','0','1','0'},
        {'1','1','0','0','0'},
        {'0','0','0','0','0'} };
    std::vector<std::vector<char>> g2 = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'} };
    std::vector<std::vector<char>> g3 = {{'0'}};
    std::cout << (num_islands(g1) == 1 ? "✓" : "✗") << " num_islands(g1) = " << "1\n";
    std::cout << (num_islands(g2) == 3 ? "✓" : "✗") << " num_islands(g2) = " << "3\n";
    std::cout << (num_islands(g3) == 0 ? "✓" : "✗") << " num_islands(g3) = " << "0\n";
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int rows, cols;

static void dfs(char** grid, int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

int num_islands(char** grid, int m, int n) {
    rows = m; cols = n;
    int count = 0;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (grid[r][c] == '1') { count++; dfs(grid, r, c); }
    return count;
}

static char** clone(const char* lines[], int m) {
    char** g = malloc(m * sizeof(char*));
    for (int i = 0; i < m; i++) g[i] = strdup(lines[i]);
    return g;
}
static void freegrid(char** g, int m) { for (int i = 0; i < m; i++) free(g[i]); free(g); }

int main(void) {
    const char* l1[] = {"11110","11010","11000","00000"};
    const char* l2[] = {"11000","11000","00100","00011"};
    const char* l3[] = {"0"};

    char** g1 = clone(l1, 4); printf("%s num_islands(g1) = %d  (expected 1)\n",
        num_islands(g1, 4, 5) == 1 ? "✓" : "✗", 1); freegrid(g1, 4);

    char** g2 = clone(l2, 4); printf("%s num_islands(g2) = %d  (expected 3)\n",
        num_islands(g2, 4, 5) == 3 ? "✓" : "✗", 3); freegrid(g2, 4);

    char** g3 = clone(l3, 1); printf("%s num_islands(g3) = %d  (expected 0)\n",
        num_islands(g3, 1, 1) == 0 ? "✓" : "✗", 0); freegrid(g3, 1);
    return 0;
}

The Rust version is iterative because nested mutable borrows make recursion painful — a real-world Rust solution would either restructure with unsafe or accept the iterative form, which is cleaner anyway. Everywhere else, recursion is the natural fit.

Complexity

Time
O(m · n) — each cell is visited at most twice (once by the outer scan, once by a flood-fill).
Space
O(m · n) in the worst case — a snake-shaped giant island fills the recursion stack with every cell. Use an explicit stack/queue or Union-Find to bound this.
Union-Find variant
Walk the grid; for each land cell, union with each land neighbor. Final answer = number of distinct roots among land cells. Same big-O, often preferred when the grid is huge or streams in incrementally.

In the wild

Variations