Number of Islands

The problem

You are given a map as a grid with m rows and n columns. Each cell is "1" for land or "0" for water. Return the number of islands.

An island is a group of land cells joined up, down, left or right. Diagonal cells do not join. Everything outside the grid is water.

Example 1

Input: grid = [["1","1","0","0","1"], ["1","0","0","1","1"], ["0","0","1","0","0"]]

Output: 3

The three land cells at the top left form one island, the three at the top right form another, and the lone 1 in the bottom row is the third.

	0	1	2	3	4
0	1	1	0	0	1
1	1	0	0	1	1
2	0	0	1	0	0

Example 2

Input: grid = [["1","1"], ["1","1"]]

Output: 1

All four land cells touch, so they are one island.

Example 3

Input: grid = [["0","0"], ["0","0"]]

Output: 0

No land, no islands.

Constraints

• 1 ≤ m, n ≤ 300
• Each cell is “0” or “1”.

Clarifying questions

Do diagonal cells join an island?

No. Only cells that share a side.

Is the edge of the grid water?

Yes. Land at the edge simply stops there.

Can we change the grid?

Usually yes. If not, keep a separate grid of visited cells instead of sinking the land.

How large can an island be?

The whole grid, 90,000 cells. A recursive search can get that deep and overflow the call stack, so we keep our own stack.

Spot the pattern

The grid is a graph in disguise: each land cell is a node, and two land cells that touch are joined by an edge. An island is a group of nodes that can reach each other, a connected component. Counting the groups is graph search: start a search at a node not seen yet, mark everything it reaches, and count one group.

Solutions

Flood fillO(m × n)

Show all

There is only one approach worth showing. Every cell must be looked at, and this looks at each one a fixed number of times. Breadth-first search or union-find give the same cost.

Flood fill O(m × n)

The idea

Scan the grid row by row. When the scan meets land, that land belongs to an island we have not counted yet. Count it, then sink the whole island: turn this cell into water and do the same for every land neighbor, and their neighbors, until no land of this island is left. This spreading is called a flood fill, and it is a depth-first search.

The fill keeps its own stack of sunk cells whose neighbors are not checked yet. It pops a cell, sinks each land neighbor and pushes it. We do not use recursion here: one island can be the whole grid, 90,000 cells, and a recursive fill that deep overflows the call stack (the memory a program keeps for calls that have not returned yet).

After that, the scan goes on. It will never meet this island again, because all of it is now water. So each island is counted exactly once.

Why it is correct: the flood fill reaches exactly the cells joined to the starting cell, which is one whole island. The scan counts one island each time it finds land that no earlier flood fill reached.

Walkthrough

	0	1	2	3	4
0	1	1	0	0	1
1	1	0	0	1	1
2	0	0	1	0	0

stack top →

empty

count

0

1. count = 0
2. for row, column in every cell:
3. if grid[row][column] == "1":
4. count += 1
5. sink(row, column)
6. return count
7. def sink(start_row, start_column):
8. grid[start_row][start_column] = "0"; stack = [(start_row, start_column)]
9. while stack:
10. row, column = stack.pop()
11. for each neighbor that is land (grid == "1"):
12. grid[neighbor] = "0"; stack.append(neighbor)

Scan the grid row by row. 1 is land and 0 is water. A sunk cell shows the number of its island.

← BackStep →Play1 / 18

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private char[][] grid;

    // Flood fill: each time the scan meets land, count a new island and
    // sink all of it, so it is never counted again. Every cell is handled a few times.
    public int numIslands(char[][] grid) {
        this.grid = grid;
        int count = 0;
        for (int row = 0; row < grid.length; row++)
            for (int column = 0; column < grid[0].length; column++)
                // Land that is still here belongs to an island not seen yet.
                if (grid[row][column] == '1') {
                    count++;
                    sink(row, column);
                }
        return count;
    }

    private void sink(int startRow, int startColumn) {
        int rows = grid.length, columns = grid[0].length;
        // Our own stack instead of recursion: a recursive fill can go as deep as the grid
        // has cells (90,000), which overflows the call stack.
        // Turn land into water as it goes on the stack, so no later step counts it or pushes it again.
        grid[startRow][startColumn] = '0';
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[] { startRow, startColumn });
        int[][] directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            int row = cell[0], column = cell[1];
            for (int[] direction : directions) {
                int neighborRow = row + direction[0], neighborColumn = column + direction[1];
                // Only land of this island spreads the fill; water and sunk cells stop it.
                if (neighborRow >= 0 && neighborRow < rows && neighborColumn >= 0 && neighborColumn < columns
                    && grid[neighborRow][neighborColumn] == '1') {
                    grid[neighborRow][neighborColumn] = '0';
                    stack.push(new int[] { neighborRow, neighborColumn });
                }
            }
        }
    }
}

Big O

Time O(m × n)Space O(m × n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are two parts. The scan runs once per cell. The flood fill repeats its while loop, so we count the pops from the stack and the neighbor checks after each pop. Each scan run, each pop and each neighbor check is a fixed job, so each counts as 1 step.

   1. count = 0
   2. for row, column in every cell:
   3. if grid[row][column] == "1":
   4. count += 1
   5. sink(row, column)
   6. return count
   7. def sink(start_row, start_column):
   8. grid[start_row][start_column] = "0"; stack = [(start_row, start_column)]
   9. while stack:
   10. row, column = stack.pop()
   11. for each neighbor that is land (grid == "1"):
   12. grid[neighbor] = "0"; stack.append(neighbor)

2. 2 Count the runs on Example 1

   The grid has 3 × 5 = 15 cells, so the scan runs 15 times. Each of the 7 land cells is pushed once and popped once: 7 pops. Each pop checks 4 neighbors: 28 checks.

   15 + 7 + 28 = 50 steps.

   	scan runs	pops	neighbor checks
   steps	15	7	28

   total

   15 + 7 + 28 = 50

3. 3 Write the count for any n

   A land cell is pushed only once, because it turns into water as it goes on the stack. So with at most m × n land cells, there are at most m × n pops, and 4 neighbor checks after each one:

   m × n (scan) + m × n (pops) + 4 × m × n (checks) = 6 × m × n steps

   Check it with Example 1: the bound is 6 × 15 = 90. The real run used 50, because only 7 of the 15 cells are land.

4. 4 Keep only the part that grows fastest

   Drop the 6. When the grid doubles, 6 × m × n doubles too. What is left is m × n: the size of the grid.

   So the time is O(m × n).

5. S Space: count the extra memory the same way

   The grid is changed in place, so there is no visited set. The memory is the fill’s stack. A cell is on it at most once, so it never holds more than m × n cells. If the whole grid is land, it holds about half the grid at once. So the space is O(m × n) in the worst case.

   stack (up to m × n cells)count

Common mistake

Sinking a cell when it is popped, not when it is pushed

A cell must turn into water as it goes on the stack. If it sinks only when popped, two of its land neighbors can both push it before that, so the same cell lands on the stack many times.

Tested at the limits

2,000 random grids of up to 6 x 6 cells with a random share of land, so single cells, long snakes and full grids come up. The flood fill gave the same count every time as a simple breadth-first search written in the test.

Largest inputs	Result
An all-land 300 x 300 grid (the most allowed): one island of 90,000 cells, filled in one go. Flood fill.	0.07 s, and about 3 MB of extra memory: the stack of cells waiting to be checked, which can grow with m × n.
A 300 x 300 checkerboard: 45,000 islands of one cell each. Flood fill.	0.03 s, and under 0.001 MB of extra memory: each fill ends at once, so the stack stays tiny.