80.Number of Islands

MediumBlind 75Graphs · 1/19

Problem

You are given an m x n grid of characters where '1' is land and '0' is water. Return the number of islands.

An island is a group of '1' cells connected horizontally or vertically (not diagonally). You may assume everything outside the grid is water.

Examples

Input:  grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Explanation: All land cells touch each other through up/down/left/right moves.

Input:  grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
Explanation: The top-left 2x2 block, the single cell in the middle, and the pair at the bottom right.

Constraints

m == grid.length, n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'

💡 Key Insight

Treat the grid as a graph: every land cell is a node and it has an edge to each adjacent land cell. The answer is the number of connected components among land cells. Scan the grid; every time you hit land that has not been visited yet, you have found a new island — flood-fill it (DFS or BFS) so none of its cells is counted again. Each cell is touched a constant number of times, so the whole thing is O(m·n).

Brute Force

TimeO((m·n)²)SpaceO(m·n)

Intuition

Give each island exactly one "owner": its first land cell in row-major order. For every land cell, run a fresh BFS over its island and check whether any cell of the island comes earlier in row-major order. Only owners get counted, so each island is counted exactly once. It is correct but repeats the same flood fill once per cell of the island.

Algorithm

For every cell (r, c) with grid[r][c] == '1':
- BFS from (r, c) with a brand-new visited array.
- If any reached cell has id nr * cols + nc smaller than r * cols + c, (r, c) is not the owner.
- Otherwise increment islands.
Return islands.

Visualization

grid           ids (r*cols+c)
1 1 0          0 1 2
1 0 0          3 4 5
0 0 1          6 7 8

cell 0: BFS reaches {0,1,3} → smallest id is 0 → owner   → islands = 1
cell 1: BFS reaches {1,0,3} → 0 < 1           → not owner
cell 3: BFS reaches {3,0,1} → 0 < 3           → not owner
cell 8: BFS reaches {8}     → owner                     → islands = 2

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int numIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int islands = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && isOwner(grid, r, c)) {
                    islands++;
                }
            }
        }
        return islands;
    }

    // Fresh BFS: is (r, c) the first cell (row-major) of its island?
    private boolean isOwner(char[][] grid, int r, int c) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        int myId = r * cols + c;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            if (cell[0] * cols + cell[1] < myId) {
                return false; // an earlier cell owns this island
            }
            for (int[] d : DIRS) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc] && grid[nr][nc] == '1') {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return true;
    }
}

Complexity

Time: O((m·n)²) — up to m·n land cells, each launching a BFS that may cover the whole grid (plus allocating a fresh visited array).
Space: O(m·n) — the visited array and queue of a single BFS.

Union-Find

TimeO(m·n·α(m·n))SpaceO(m·n)

Intuition

Start with every land cell as its own set, so count = number of land cells. Then, for every pair of adjacent land cells, union their sets. Each union that actually merges two different sets reduces the number of islands by one. Whatever remains is the answer. Only the right and down neighbours need to be checked — the left and up pairs were already handled from the other side.

Algorithm

Map cell (r, c) to id r * cols + c. For each land cell set parent[id] = id and count++.
For each land cell, if the cell below or to the right is land, union them; on a successful merge, count--.
find uses path compression and union uses rank, so each operation is almost O(1).
Return count.

Dry Run

grid      ids
1 1 0     0 1 2
1 0 0     3 4 5
0 0 1     6 7 8

land cells: 0,1,3,8                     count = 4
cell 0: right 1 is land → union(0,1)    count = 3
cell 0: down  3 is land → union(0,3)    count = 2
cell 1: down  4 is water, right 2 water
cell 3: nothing new
cell 8: no right/down neighbours
answer = 2

flowchart LR
    A["{0} {1} {3} {8}<br/>count = 4"] -->|"union(0,1)"| B["{0,1} {3} {8}<br/>count = 3"]
    B -->|"union(0,3)"| C["{0,1,3} {8}<br/>count = 2"]
    C --> D["return 2"]

Code

java

class Solution {
    private int[] parent;
    private int[] rank;
    private int count;

    public int numIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        parent = new int[rows * cols];
        rank = new int[rows * cols];
        count = 0;

        // Every land cell starts as its own island
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    int id = r * cols + c;
                    parent[id] = id;
                    count++;
                }
            }
        }

        // Merge with right and down neighbours only
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != '1') continue;
                int id = r * cols + c;
                if (r + 1 < rows && grid[r + 1][c] == '1') union(id, id + cols);
                if (c + 1 < cols && grid[r][c + 1] == '1') union(id, id + 1);
            }
        }
        return count;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return; // already the same island
        if (rank[ra] < rank[rb]) {
            int tmp = ra; ra = rb; rb = tmp;
        }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        count--; // two islands became one
    }
}

Complexity

Time: O(m·n·α(m·n)) — each cell does at most two unions; α (inverse Ackermann) is effectively constant.
Space: O(m·n) — the parent and rank arrays.

DFS (Flood Fill)

TimeO(m·n)SpaceO(m·n)

Intuition

Scan the grid. When you find a '1', you have discovered a new island: increment the counter and sink the entire island by recursively turning every connected '1' into '0'. Sunk cells can never trigger another count, so no separate visited array is needed.

Algorithm

For every cell (r, c): if grid[r][c] == '1', increment islands and call dfs(r, c).
dfs(r, c): if out of bounds or grid[r][c] != '1', return. Otherwise set grid[r][c] = '0' and recurse on the four neighbours.
Return islands.

Dry Run

Example 2 grid:        after first DFS at (0,0):
1 1 0 0 0              0 0 0 0 0
1 1 0 0 0              0 0 0 0 0     islands = 1
0 0 1 0 0              0 0 1 0 0
0 0 0 1 1              0 0 0 1 1

(2,2) is '1' → islands = 2, sink it
(3,3) is '1' → islands = 3, sink (3,3) and (3,4)

Code

java

class Solution {
    public int numIslands(char[][] grid) {
        int islands = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    islands++;       // new island discovered
                    sink(grid, r, c); // erase it so it is never counted again
                }
            }
        }
        return islands;
    }

    private void sink(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || 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);
    }
}

Complexity

Time: O(m·n) — every cell is sunk at most once and examined a constant number of times.
Space: O(m·n) — recursion depth when the whole grid is one snake-shaped island.

BFSOptimal

TimeO(m·n)SpaceO(min(m, n))

Intuition

Same counting idea as DFS, but the island is explored with a queue instead of recursion. This avoids any risk of a stack overflow on a 300 x 300 all-land grid. Cells are marked as water when they are enqueued, so no cell enters the queue twice. Because BFS expands in "rings", the queue only ever holds a frontier, which is bounded by O(min(m, n)).

Algorithm

For every cell (r, c) with grid[r][c] == '1':
- Increment islands, set grid[r][c] = '0', push it onto the queue.
- While the queue is non-empty, pop a cell and for each in-bounds land neighbour: set it to '0' and enqueue it.
Return islands.

Dry Run

flowchart TD
    S["scan finds (0,0) = '1'<br/>islands = 1"] --> Q1["queue: (0,0)"]
    Q1 --> Q2["pop (0,0)<br/>enqueue (1,0), (0,1)"]
    Q2 --> Q3["pop (1,0)<br/>enqueue (1,1)"]
    Q3 --> Q4["pop (0,1), pop (1,1)<br/>nothing new"]
    Q4 --> S2["scan finds (2,2)<br/>islands = 2"]
    S2 --> S3["scan finds (3,3)<br/>islands = 3, BFS sinks (3,4)"]
    S3 --> R["return 3"]

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int numIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int islands = 0;
        Deque<int[]> queue = new ArrayDeque<>();

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != '1') continue;
                islands++;
                grid[r][c] = '0'; // mark on enqueue
                queue.offer(new int[]{r, c});

                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] d : DIRS) {
                        int nr = cell[0] + d[0], nc = cell[1] + d[1];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                            grid[nr][nc] = '0';
                            queue.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        return islands;
    }
}

Complexity

Time: O(m·n) — each cell is enqueued at most once and checks 4 neighbours.
Space: O(min(m, n)) — the BFS frontier inside a grid never exceeds roughly the length of the shorter side.

Complexity Comparison

Approach	Time	Space
Brute Force	O((m·n)²)	O(m·n)
Union-Find	O(m·n·α(m·n))	O(m·n)
DFS	O(m·n)	O(m·n)
BFS	O(m·n)	O(min(m, n))

Common Pitfalls

Comparing against the integer 1 instead of the character '1' — the grid is char[][], so grid[r][c] == 1 is always false.
Marking a cell visited when it is dequeued instead of when it is enqueued — the same cell gets added many times and the queue can blow up.
Counting diagonal neighbours as connected; only the four orthogonal directions count.
Forgetting the bounds check before reading grid[nr][nc], causing ArrayIndexOutOfBoundsException on edge cells.
Mutating the input when the caller needs it intact — if so, use a separate boolean[][] visited instead of sinking cells.