Grid Traversal: Solving the 'Number of Islands' Problem

Number of Islands is a good example of a problem that looks like a matrix exercise until we describe it properly. We are given a grid of '1' and '0' values. Land is '1', water is '0', and horizontally or vertically adjacent land cells belong to the same island. The task is simply to count how many separate islands exist.

The trap is thinking that we are counting cells. We are not. We are counting connected groups. That is why this is really a traversal problem. As soon as we find one piece of land, we need to walk the whole connected region so that we do not count the same island twice.

Why This is a Graph Problem in Disguise

Even though the input is a two‑dimensional array, the structure is graph‑shaped.

Each land cell can connect to up to four neighbours:

• up
• down
• left
• right

That means every land cell is effectively a node, and adjacency gives us the edges. Once we say that out loud, the right mental model becomes much clearer. We need to visit each connected component once, which is exactly what depth‑first search or breadth‑first search is good at.

Why a Naive Counting Approach Fails Immediately

If we simply counted how many '1' cells appear in the grid, we would be answering a different question:

• how many land cells exist?

But the problem is asking:

• how many separate land masses exist?

That difference is exactly why traversal matters. One island might occupy one cell or ten. The size of the connected region is irrelevant to the count once we know it is all one component.

What the Counting Step Really Means

Suppose we loop through the grid and find a '1'. At that moment, we know we have discovered a new island, so the count should increase by one.

What we must not do is continue scanning as if that cell were isolated. We have to mark the whole island as visited immediately. Otherwise, later cells from the same island will still look like fresh land and we will count them again.

That is the whole structure of the solution:

• scan the grid
• when we see unvisited land, increase the island count
• traverse the connected land from that starting point
• mark each visited land cell so it is not counted again

A Practical TypeScript Solution

export const numIslands = (grid: string[][]): number => {  const rowCount = grid.length;  const columnCount = grid[0]?.length ?? 0;  if (rowCount === 0 || columnCount === 0) {    return 0;  }  const visitIsland = (row: number, column: number): void => {    if (      row < 0 ||      column < 0 ||      row >= rowCount ||      column >= columnCount ||      grid[row][column] !== '1'    ) {      return;    }    grid[row][column] = '0';    visitIsland(row + 1, column);    visitIsland(row - 1, column);    visitIsland(row, column + 1);    visitIsland(row, column - 1);  };  let islandCount = 0;  for (let row = 0; row < rowCount; row += 1) {    for (let column = 0; column < columnCount; column += 1) {      if (grid[row][column] === '1') {        islandCount += 1;        visitIsland(row, column);      }    }  }  return islandCount;};

Why the in‑Place Marking Works

The line:

grid[row][column] = '0';

is doing the real bookkeeping. It turns visited land into water for the rest of the traversal, which means we do not need a separate visited matrix.

That is a tidy fit here because once a land cell has been explored, we never need to treat it as unvisited again. In other words, the mutation lines up exactly with the problem state.

There is one trade‑off, though. We are modifying the input grid. In an interview or algorithm setting that is usually fine. In production code, if the original grid must remain untouched, we would either clone it first or track visited cells separately.

Walking One Island through by Hand

Imagine this grid:

1 1 0 01 0 0 10 0 1 10 0 0 0

The first time we hit the top‑left 1, we count one island and recursively visit every connected land cell in that group. That clears the small island in the top‑left area.

Later, when we reach the 1 in the second row on the far right, that is a separate group, so the count increases again. The connected land in the lower‑right area belongs to that same second island.

What matters is that traversal turns "several land cells" into "one counted component".

Why BFS and Dfs are Both Valid Here

This is one of those problems where the traversal choice is more about expression than about correctness.

DFS works nicely because:

• the recursive version is short
• the code mirrors "keep exploring this island" quite naturally

BFS works nicely because:

• it makes the frontier of connected land explicit
• some people find the queue easier to trace than recursion

The count does not change. The core requirement is only that every cell in the component gets marked before the outer scan carries on.

Depth‑First Search versus Breadth‑First Search

This article uses DFS because the recursive version is compact and matches the shape of the connected‑region problem neatly.

BFS would work just as well:

• start from one land cell
• use a queue to explore its neighbours
• mark visited cells as you go

The choice here is mostly about implementation style. The underlying idea is identical: once you discover one cell from an island, traverse the whole connected component before moving on.

An Alternative with a Visited Matrix

If mutating the grid feels awkward, we can keep a separate visited matrix of booleans. That gives us cleaner separation between:

• the original problem input
• the traversal bookkeeping

The downside is extra space and slightly more setup code.

That makes the trade‑off straightforward:

• in‑place marking is smaller and perfectly reasonable for algorithm practice
• a visited matrix is more explicit if preserving the input matters

Neither changes the real idea. They are just two different ways of storing the same "already explored" state.

Common Mistakes

Forgetting to Mark Visited Land

If you skip that step, the same island will be counted several times. That is the most common bug in this problem.

Counting Cells Instead of Components

The goal is not "how much land exists?" It is "how many disconnected groups of land exist?" That distinction changes everything.

Treating Diagonal Neighbours as Connected

In this problem, diagonals do not count. The allowed moves are only horizontal and vertical.

Continuing the Outer Scan Without Finishing the Island Traversal

As soon as we discover fresh land, we need to consume the whole component. If we only mark one or two cells and then continue the outer loop, the island count becomes unreliable very quickly.

Complexity and Why It is Acceptable

We visit each cell at most once, so the time complexity is O(rows * columns). The extra space is O(rows * columns) in the worst case if the recursion stack grows across a large connected island.

That is exactly what we should expect from a traversal problem. The work grows with the size of the grid, not with the number of possible paths we might imagine.

Wrapping up

Number of Islands is a strong teaching problem because it turns a plain‑looking grid into a graph question without needing any abstract graph notation. Once we recognise that the real task is counting connected components, the solution becomes much calmer.

Key Takeaways

• The grid is best understood as a graph of connected land cells.
• Each time we discover fresh land, we have found one new island.
• Traversal and visited‑state handling are what make the count correct.

This is the kind of problem that gets much easier once we describe it honestly. We are not counting cells. We are traversing components.