Number of Islands

MediumGraphs · DFS Flood Fill🧩 Graph DFS LeetCode #200 ↗Updated Oct 30, 2026

Problem

You get an m × n grid of characters where '1' is land and '0' is water. Land cells that touch horizontally or vertically belong to the same island; everything outside the grid is water. Return how many separate islands there are.

Inputrows: 11000 / 11000 / 00100 / 00011Output3

Inputrows: 111 / 010 / 111Output1

1 ≤ m, n ≤ 300 · grid[i][j] is '0' or '1' · diagonal cells are not connected

Try it yourself

Java

class Solution {
    public int numIslands(char[][] grid) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

An island is just a connected component of land. Scan the grid; each time you hit unvisited land, count one island and sink (flood-fill) the whole component so it is never counted again.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceFlood Each Cell, Count Island Leaders

Time O((m·n)²)Space O(m·n)

For every land cell, BFS its whole island with a fresh visited array and count the cell only if it is the island's leader (smallest index r*n+c). Each island has exactly one leader, but one island of k cells is explored k times.

Java

public int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length, count = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int s = 0; s < m * n; s++) {
        if (grid[s / n][s % n] != '1') continue;
        boolean[] seen = new boolean[m * n]; // fresh for every start cell
        Deque<Integer> q = new ArrayDeque<>(List.of(s));
        seen[s] = true;
        boolean leader = true; // is s the smallest id in its island?
        while (!q.isEmpty() && leader) {
            int cur = q.poll(), r = cur / n, c = cur % n;
            if (cur < s) leader = false;
            for (int[] d : dirs) {
                int x = r + d[0], y = c + d[1];
                if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != '1') continue;
                if (!seen[x * n + y]) { seen[x * n + y] = true; q.add(x * n + y); }
            }
        }
        if (leader) count++;
    }
    return count;
}

Correct and read-only, but re-explores every island once per cell — quadratic.

BetterUnion-Find (Disjoint Set Union)

Time O(m·n·α(m·n))Space O(m·n)

Each land cell starts as its own set (count = #land). Union every land cell with its right/down land neighbour; each successful union merges two islands, so count--. Path compression + rank keep operations near-constant.

Java

int[] parent, rank; int count;
public int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    parent = new int[m * n]; rank = new int[m * n];
    for (int i = 0; i < m * n; i++) {
        parent[i] = i;
        if (grid[i / n][i % n] == '1') count++;
    }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != '1') continue;
            if (r + 1 < m && grid[r + 1][c] == '1') union(r * n + c, (r + 1) * n + c);
            if (c + 1 < n && grid[r][c + 1] == '1') union(r * n + c, r * n + c + 1);
        }
    return count;
}
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    if (rank[ra] == rank[rb]) rank[ra]++;
    count--; // two islands merged
}

Near-linear, no deep recursion; extra arrays, but shines when land is added online.

OptimalDFS Flood Fill (Sink the Island)

Time O(m·n)Space O(m·n) stack

On each '1', count an island and DFS-sink it (set its cells to '0'). The grid is the visited set, so every cell is sunk at most once.

Java

public int numIslands(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;
}
private void sink(char[][] grid, int r, int c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1') return;
    grid[r][c] = '0'; // mark visited
    sink(grid, r + 1, c); sink(grid, r - 1, c);
    sink(grid, r, c + 1); sink(grid, r, c - 1);
}

Simplest true O(m·n); for huge grids use an iterative stack/BFS to avoid deep recursion.

At a glance

Level	Approach	Time	Space
Brute Force	Flood Each Cell, Count Island Leaders	`O((m·n)²)`	`O(m·n)`
Better	Union-Find (Disjoint Set Union)	`O(m·n·α(m·n))`	`O(m·n)`
Optimal	DFS Flood Fill (Sink the Island)	`O(m·n)`	`O(m·n) stack`

Common pitfalls

BFS: mark on enqueue, not dequeue, or cells repeat.
Diagonals do not connect — use 4 directions.
Compare with '1' (char), not 1.

Interview tips

Ask if mutating the grid is allowed; else use visited.
Frame it as “count connected components”.
Land added over time (LC 305)? → Union-Find.

Pattern

Grid flood fill → count or label connected groups of similar cells.

My notes saved in this browser