Number of Islands: Exploring a Grid with Depth-First Search

Problem

A rectangular grid with m rows and n columns describes a map. Each cell contains the character '1' for land or '0' for water. Return how many separate islands the map contains.

Land cells belong to the same island when a path connects them by moving up, down, left, or right through land. Diagonal contact does not connect two cells. Treat everything outside the grid as water, so land touching an edge can still form an island.

Example 1

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

All land cells are connected, even though some are not directly beside one another.

Example 2

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

Constraints

• m == grid.length
• Every row has the same length n.
• 1 <= m, n <= 300
• Each cell contains '0' or '1', not an integer value.

By the end of this lesson, you should be able to recognize connected regions in a grid, explore one with a stack, and explain why each island is counted exactly once.

Count regions, not land cells

Counting every '1' would count the area of the land, not the number of islands. The four land cells in the top-left corner of Example 2 belong to one island.

Checking only the cell above and the cell to the left is also insufficient for a simple counting rule. Two stretches that initially look separate may join farther down:

1 0 1
1 1 1

There is only one island here. To count correctly, we need to identify all land connected to a starting cell, even when the connecting path bends or goes backward relative to our row scan.

Think of each land cell as a graph vertex. It has an edge to each land cell immediately above, below, left, or right. An island is a connected component of this graph; we can discover it without building a separate graph structure.

Explore one whole island at a time

This process is often called a flood fill. We will use iterative depth-first search (DFS): a stack stores cells whose neighbors we still need to inspect. Removing the most recently added cell takes the exploration deeper through the island.

To record a visit, change the cell from '1' to '0'. This does not change which island we count; it marks land that has already been claimed by a traversal. The algorithm therefore modifies the input grid.

Algorithm

1. Start an island counter at 0 and scan every cell row by row.
2. Skip a cell if it contains '0': it is water or land already visited.
3. When a cell contains '1', increment the counter. Change that cell to '0' and push its coordinates onto a stack.
4. While the stack is not empty, pop a cell and examine its four orthogonal neighbors. For each neighbor inside the grid that is still '1', change it to '0' and push it.
5. When the stack empties, this island is finished. Continue the outer scan and return the counter after the last cell.

Mark each cell before pushing it, including the starting cell. Otherwise, two neighboring cells could both schedule the same land cell before it is processed. Marking on discovery ensures that every land cell enters the stack only once.

Walkthrough: three islands

Label the original land in Example 2 by island. Dots represent water:

A A . . .
A A . . .
. . B . .
. . . C C

Use zero-based (row, column) coordinates. The outer scan reaches these new starting points:

The other land cells do not start traversals because the earlier traversal has already marked them '0'. Island B and island C remain separate: (2, 2) and (3, 3) touch only diagonally.

To see the stack at work, follow the first island. The implementations inspect neighbors in the order up, down, left, right; the stack’s top is shown on the right:

When examining (1, 1), its neighbor (1, 0) is already marked even though it is still waiting in the stack. That is what prevents duplicate work.

Implementation

All three implementations use an explicit stack, so a large island does not require a deep chain of recursive function calls. C# stores coordinate tuples, Go stores pairs of integers, and Python stores tuples in a list.

using System.Collections.Generic;

public class Solution
{
    public int NumIslands(char[][] grid)
    {
        if (grid.Length == 0 || grid[0].Length == 0)
            return 0;

        int rows = grid.Length;
        int cols = grid[0].Length;
        int islands = 0;
        var stack = new Stack<(int Row, int Col)>();
        var directions = new (int Row, int Col)[]
        {
            (-1, 0), (1, 0), (0, -1), (0, 1)
        };

        for (int row = 0; row < rows; row++)
        {
            for (int col = 0; col < cols; col++)
            {
                if (grid[row][col] != '1')
                    continue;

                islands++;
                // Mutate the grid: mark land as visited before pushing it.
                grid[row][col] = '0';
                stack.Push((row, col));

                while (stack.Count > 0)
                {
                    var current = stack.Pop();

                    foreach (var direction in directions)
                    {
                        int nextRow = current.Row + direction.Row;
                        int nextCol = current.Col + direction.Col;

                        if (nextRow < 0 || nextRow >= rows ||
                            nextCol < 0 || nextCol >= cols ||
                            grid[nextRow][nextCol] != '1')
                            continue;

                        grid[nextRow][nextCol] = '0';
                        stack.Push((nextRow, nextCol));
                    }
                }
            }
        }

        return islands;
    }
}

func numIslands(grid [][]byte) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}

	rows, cols := len(grid), len(grid[0])
	islands := 0
	stack := make([][2]int, 0)
	directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if grid[row][col] != '1' {
				continue
			}

			islands++
			// Mutate the grid: mark land as visited before pushing it.
			grid[row][col] = '0'
			stack = append(stack, [2]int{row, col})

			for len(stack) > 0 {
				current := stack[len(stack)-1]
				stack = stack[:len(stack)-1]

				for _, direction := range directions {
					nextRow := current[0] + direction[0]
					nextCol := current[1] + direction[1]

					if nextRow < 0 || nextRow >= rows ||
						nextCol < 0 || nextCol >= cols ||
						grid[nextRow][nextCol] != '1' {
						continue
					}

					grid[nextRow][nextCol] = '0'
					stack = append(stack, [2]int{nextRow, nextCol})
				}
			}
		}
	}

	return islands
}

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])
        islands = 0
        directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] != "1":
                    continue

                islands += 1
                # Mutate the grid: mark land as visited before pushing it.
                grid[row][col] = "0"
                stack = [(row, col)]

                while stack:
                    current_row, current_col = stack.pop()

                    for row_step, col_step in directions:
                        next_row = current_row + row_step
                        next_col = current_col + col_step

                        if (
                            next_row < 0 or next_row >= rows
                            or next_col < 0 or next_col >= cols
                            or grid[next_row][next_col] != "1"
                        ):
                            continue

                        grid[next_row][next_col] = "0"
                        stack.append((next_row, next_col))

        return islands

The code compares characters: C# and Go use '1', while Python uses "1". Passing numeric 1 and 0 values instead is outside the stated input contract. Bounds checks happen before accessing a neighboring cell.

Input mutation

After a successful call, all original land cells have become '0'. Calling the function again on the same grid therefore returns 0. When comparing implementations or repeating a test, give each call a fresh grid.

If the caller needs the original map afterward, copy each row before passing it to this version, or keep a separate visited matrix and leave the grid unchanged. Copying only the outer container still shares its rows. Either alternative uses O(m × n) additional storage.

The implementations also return 0 for a grid with no rows or no columns, although the problem’s constraints exclude these inputs. They otherwise assume a rectangular grid.

Why it works

Consider a traversal that starts from a land cell:

• Every cell it discovers is connected to that start, because we only move from a discovered land cell to an adjacent land cell. The traversal cannot cross water or jump diagonally.
• Every land cell in the same island is eventually discovered. Along any connecting path, processing one cell discovers the next unvisited cell on the path.
• Marking cells before pushing them prevents duplicate visits. Once the stack empties, the entire island is marked and no future scan position in that island can start a new traversal.

The outer scan visits every grid position, so it eventually starts a traversal for every island. Each traversal increments the counter once and covers exactly one island. Therefore the returned count is correct.

Complexity

• Time: O(m × n). The outer scan checks every cell. Each land cell is pushed and popped at most once, and processing it examines only four neighbors. The total traversal work across all islands is linear in the grid size.
• Extra space: O(m × n) in the worst case. The stack can hold a number of coordinates proportional to the grid size. Changing the grid avoids a visited matrix, but does not remove the stack’s storage cost.

The nested row and column loops do not multiply the cost by a full traversal for every cell. Visited cells never start a second traversal.

What about breadth-first search?

A queue can replace the stack to explore cells in breadth-first order. Mark cells before enqueueing them, and keep the same island counter and four-neighbor checks. The answer and worst-case time and space bounds remain the same.

Recursive DFS is another way to express the traversal, but the grid can contain 90,000 cells. A long winding island may require too many nested calls for the language’s call stack. The explicit stack avoids that recursion-depth limit.

Common mistakes

• Including diagonal neighbors. This merges islands that the problem treats as separate.
• Incrementing for every land cell. Increment only when the outer scan finds the start of an unvisited island.
• Forgetting to mark the starting cell. Mark it before adding it to the stack, just like its neighbors.
• Reading a neighbor before checking its coordinates. Cells at the edges have fewer than four valid neighbors.
• Claiming constant extra space. In-place marking saves a visited matrix, but the traversal stack still takes space.
• Reusing the changed grid. Tests need fresh rows because the first call consumes the land markers.

Try it yourself

Count the islands in each map. These diagrams omit quotes for readability; the actual input still contains characters.

Map A

1 0
0 1

Map B

1 0 1
1 1 1

Map C

0 0 0
0 0 0

Map D

1 1 1
1 0 1
1 1 1

Then write the solution without looking at the implementation. Explain why the counter changes only in the outer scan, why marking happens before pushing, and why the total work stays linear even when the map contains many islands.