number-of-islands.html

Number of Islands (LeetCode 200)

You are given a 2D grid of characters, char[][] grid, where '1' is land and '0' is water. An island is a group of land cells connected horizontally or vertically (not diagonally). Count the islands. Everything outside the grid counts as water.

For example, this grid has 3 islands:

1 1 0 0 1
1 0 0 0 1
0 0 1 0 0
0 0 1 1 0

The top-left island has 3 cells, the island on the right edge has 2, and the island near the bottom has 3.

The Solution

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == '1' && !visited[row][col]) {
                    dfs(grid, row, col, visited);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int row, int col, boolean[][] visited) {
        if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length
                || visited[row][col] || grid[row][col] == '0') {
            return;
        }
        visited[row][col] = true;  // never un-marked: this cell's island is finished for good
        dfs(grid, row + 1, col, visited);
        dfs(grid, row, col + 1, visited);
        dfs(grid, row - 1, col, visited);
        dfs(grid, row, col - 1, visited);
    }
}

How It Works

The outer double loop scans every cell, row by row. When it finds land that has not been visited yet, that cell belongs to an island nobody has counted, so we explore the whole island with dfs and add 1 to count.

dfs is a flood fill. Starting from one land cell, it marks the cell as visited and then recurses down, right, up and left. A call returns right away if it steps off the grid, onto water, or onto a cell that is already visited. When the first call returns, every cell of that island has been marked.

So each island is counted exactly once: the first time the outer loop reaches one of its cells. Every other cell of the island is already marked by then, and the outer loop skips it.

Why We Never Un-mark visited

My first instinct was to un-mark each cell on the way out of dfs, the way backtracking does. Here is the note I left myself in the code:

//visited[row][col] = false; Not needed because when I leave dfs for good, I should never touch these cells again...
//but I thought this would prevent my outer double loop from entering a specific (row,col)
//yes, I'm right, so make this a condition in my double loop to ensure I only eval a position if visited[row][col] == false. This solves it.

In backtracking problems, such as Word Search, un-marking is required. A cell used by one path may be needed by a different path later, so each path has to release its cells when it backs out.

Here, the question is different. We are not looking for paths; we are asking which island each cell belongs to, and that answer never changes. Once dfs finishes, the island is complete. If we un-marked its cells, the outer double loop would reach them again, start a new dfs, and count the same island more than once. Keeping the marks, and checking !visited[row][col] in the outer loop, is what makes each island count exactly once.

Complexity

Let the grid have mm rows and nn columns.

Time: Θ(mn)\Theta(mn). The outer double loop visits each of the mnmn cells once. Each cell is marked at most once, and after that, any call that reaches it returns immediately. A cell can be reached by at most 4 calls, one from each neighbor, plus one from the outer loop, so the total number of dfs calls is at most 5mn5mn, and each call does constant work outside its recursive calls.

Space: Θ(mn)\Theta(mn). The visited array has mnmn entries. The recursion also uses the call stack: in the worst case, a single island that winds through every cell makes the recursion Θ(mn)\Theta(mn) calls deep. In the best case, a grid with no land, the recursion never starts.

The Risk: StackOverflowError

On a 300×300 grid, LeetCode’s largest input, a single island can make dfs recurse up to 90,000 calls deep. Each call adds a frame to Java’s call stack, which has a fixed size, and the program can crash with a StackOverflowError, depending on the stack size. This is a risk for any recursive algorithm whose recursion depth grows with the input size. In a later post, I’ll derive an implementation that handles these extreme cases.

770 words