Number of Islands

NeetCode: Number of Islands · LeetCode: 200. Number of Islands · Difficulty: Medium

Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is a maximal group of land cells connected horizontally or vertically.

Example

Text

grid:  11110     Output: 1
       11010
       11000
       00000

grid:  11000     Output: 3
       11000
       00100
       00011

A grid is an implicit graph: each cell is a node and its four neighbors are its edges. Counting islands is counting connected components: scan the cells, and each time unvisited land is found, count one island and flood-fill everything connected to it so it is not counted again.

The grid is a char[][]. The examples build it from strings with a helper parse that calls String.toCharArray() on each row.

Brute force: recursive DFS with a visited matrix

Keep the input untouched and record what has been seen in a separate visited matrix. The recursion visits every cell of an island once.

Java

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

    private void dfs(char[][] grid, boolean[][] visited, int r, int c) {
        visited[r][c] = true;
        for (int[] d : DIRS) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= grid.length || nc >= grid[0].length) {
                continue;
            }
            if (grid[nr][nc] == '1' && !visited[nr][nc]) {
                dfs(grid, visited, nr, nc);
            }
        }
    }

    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        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' && !visited[r][c]) {
                    count++;
                    dfs(grid, visited, r, c);
                }
            }
        }
        return count;
    }
}

public class Main {
    static char[][] parse(String... rows) {
        char[][] grid = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            grid[i] = rows[i].toCharArray();
        }
        return grid;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.numIslands(parse("11110", "11010", "11000", "00000")));
        System.out.println(s.numIslands(parse("11000", "11000", "00100", "00011")));
        System.out.println(s.numIslands(parse()));
    }
}

Output

1
3
0

Both versions are linear. The practical costs are that the recursion depth can reach m * n on a snake-shaped island, which throws StackOverflowError on large grids because Java's thread stack is limited, and that the extra matrix doubles the memory. Time: O(m * n). Space: O(m * n) for visited plus the recursion stack.

Optimal: iterative flood fill that sinks land in place

Replace the recursion with an explicit stack (an ArrayDeque on the heap, so the call stack cannot overflow), and instead of a visited matrix overwrite each land cell with '0' when it is pushed. Sunk land is exactly already-seen land. The method modifies the grid it is given, which LeetCode allows.

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) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != '1') {
                    continue;
                }
                count++;
                grid[r][c] = '0';
                Deque<int[]> stack = new ArrayDeque<>();
                stack.push(new int[]{r, c});
                while (!stack.isEmpty()) {
                    int[] cell = stack.pop();
                    for (int[] d : DIRS) {
                        int nr = cell[0] + d[0];
                        int nc = cell[1] + d[1];
                        if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
                            continue;
                        }
                        if (grid[nr][nc] == '1') {
                            grid[nr][nc] = '0';
                            stack.push(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        return count;
    }
}

public class Main {
    static char[][] parse(String... rows) {
        char[][] grid = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            grid[i] = rows[i].toCharArray();
        }
        return grid;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.numIslands(parse("11110", "11010", "11000", "00000")));
        System.out.println(s.numIslands(parse("11000", "11000", "00100", "00011")));
        System.out.println(s.numIslands(parse()));
    }
}

Output

1
3
0

Marking a cell when it is pushed, not when it is popped, guarantees it is pushed at most once. Time: O(m * n), each cell is sunk once and looked at from four sides. Space: O(m * n) worst case for the stack, with no visited matrix.