Graph traversal · BFS flood fill on a grid

Medium · O(m·n) time · O(min(m, n)) space

Problem

You are given an m × n grid of characters. "1" is land and "0" is water. An island is a group of land cells joined up, down, left or right. Diagonals do not join. Everything outside the grid is water. Return the number of islands.
Example 1 Input: grid = [["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]] Output: 3 (the 2×2 block, the single cell at (2,2), and the pair at (3,3)-(3,4)) Example 2 Input: grid = [["1","0","1"], ["0","1","0"], ["1","0","1"]] Output: 5 (diagonal neighbours are not connected)
Constraints 1 ≤ m, n ≤ 300 grid[i][j] is "0" or "1"

Brute force

Picture a map seen from above. Land is "1" and water is "0". Land squares that touch each other, up, down, left or right, form one island. Squares that only touch at a corner are not joined. How many islands are there?

  1. A cell is land if it holds "1".
  2. Two land cells are in the same island if you can walk from one to the other through land, moving up, down, left or right.
  3. Return how many separate islands there are.

We are counting groups of land, not land squares. Here is the first example, with each island in its own colour.

The first idea is the simplest one: go through the grid and add 1 for every land cell.

The problem with it

It is fast, but it is wrong. On the example it returns 7, because there are 7 land cells, but there are only 3 islands. It counts the 2 × 2 block four times.

Still, it gets one thing right: scanning every cell is the right way to find islands. The only problem is that we count land that we have already met as part of an island.

How to think your way to the optimal solution

When we find a land cell, how do we make sure that none of its island-mates is ever counted again?

Scan the grid row by row. The first land cell we meet in a part of the map we have not looked at belongs to a new island, so we add 1. Then we sink the whole island: walk to every land cell connected to it, and turn each one into water. When the scan moves on, those cells read "0", so they cannot be counted again.

The walk uses a queue, a line where things are taken out in the order they arrived. The queue holds land cells whose neighbours we have not looked at yet. We take one out, look at its four neighbours, and every neighbour that is land is sunk at once and added to the queue. When the queue is empty, the whole island has been sunk.

We sink a cell at the moment it joins the queue, not when we take it out. Otherwise a cell could be added twice, by two different neighbours.

Why is it safe? When the walk stops, every land cell connected to the start has been sunk. So any "1" left in the grid belongs to an island we have not counted yet, and each island is counted exactly once, when the scan first reaches it.

The optimal solution

  1. Scan every cell, row by row.
  2. the cell is water⟶move on
  3. the cell is land⟶add 1 to the count, sink it, and put it in the queue
  4. Take a cell out of the queue. For each of its four neighbours: inside the grid and land⟶sink it and put it in the queue
  5. When the queue is empty, continue the scan. At the end, return the count.

By hand, on this 4 × 5 grid (1 is land):

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
  1. The cell (0,0) is land. Count is 1. We sink it, then the walk sinks (0,1), (1,0) and (1,1). The 2 × 2 block is gone.
  2. The scan continues over water. At (2,2) it finds land. Count is 2. It has no land neighbours, so only that cell is sunk.
  3. At (3,3) the scan finds land. Count is 3. The walk reaches (3,4) and sinks it too.
  4. The scan ends. The answer is 3.

Press Play to watch the queue and the sinking. Try the 3 × 3 ring: it is one island, even though the centre is water.

Complexity analysis

O(m × n)
Time. Here's why: the scan visits each of the m × n cells once. Each land cell is added to the queue at most once, because it is sunk the moment it is added, and for each cell we look at four neighbours, which takes the same small time every time.
O(min(m, n))
Space. The queue holds the cells at the edge of the part of the island we are exploring, which is about as long as the shorter side of the grid. Sinking cells reuses the grid itself, so nothing else grows.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Land appears one cell at a time. After each new cell, tell me how many islands there are."

What they are checkingWhether you see that rerunning the whole search after every cell is too slow, and know the tool for this. This is the well-known "Number of Islands II".

A strong answerRerunning the search each time costs O(m × n) per new cell, which is too slow. I would use Union-Find, which keeps track of groups as they merge. When a new land cell appears, the island count goes up by 1. Then for each land neighbour, I join the two groups, and every join that really merges two groups lowers the count by 1. Each step is almost constant time. See the Union-Find lesson.

"Why did you use a queue? I would have used recursion."

What they are checkingWhether you can compare two ways of exploring and pick one for a reason, not by habit.

A strong answerBoth find the same islands. The difference is memory in the worst case. Recursion (a depth-first search) can go as deep as the island is long: a grid of 300 × 300 that is all land could make 90,000 nested calls, which can overflow the call stack in many languages. A queue lives in ordinary memory and has no such limit. See Depth-First Search for the recursive version.

"You are not allowed to change the grid."

What they are checkingWhether you notice that your solution quietly destroys its input, and know the cost of fixing it.

A strong answerI would keep a separate set (or a grid of true and false) of cells I have already visited, and check it instead of writing "0" into the grid. That costs O(m × n) extra space. The other option is to change the grid and then put every cell back at the end, which keeps the extra space low but still modifies the input during the run, so it is not safe if another thread reads the grid at the same time.

Spot this pattern