Number of Islands BFS and DFS in DSA Typescript - Execution Trace

Concept Flow - Number of Islands BFS and DFS

Start at each cell in grid

↓

Is cell land and unvisited?

No→Move to next cell

Yes↓

Increment island count

↓

Explore neighbors (BFS or DFS)

↓

Mark connected land cells as visited

↓

Continue scanning grid

↓

All cells checked?

No→Repeat

Yes↓

Return total island count

Scan each cell; if land and not visited, increase island count and explore all connected land cells using BFS or DFS to mark them visited; repeat until all cells checked.

Execution Sample

DSA Typescript

function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const visited = new Set<string>();

  function dfs(r: number, c: number) {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return;
    if (grid[r][c] === '0' || visited.has(`${r},${c}`)) return;
    visited.add(`${r},${c}`);
    dfs(r+1, c);
    dfs(r-1, c);
    dfs(r, c+1);
    dfs(r, c-1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !visited.has(`${r},${c}`)) {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Counts islands by scanning grid and using DFS to mark connected land cells visited.

Execution Table

Step	Operation	Current Cell	Visited Cells	Island Count	Visual State
1	Check cell (0,0)	(0,0)	{}	0	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
2	Found land and unvisited, increment count	(0,0)	{(0,0)}	1	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
3	DFS explore neighbors from (0,0)	(0,0)	{(0,0),(0,1),(1,0),(1,1)}	1	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
4	Check cell (0,1)	(0,1)	{(0,0),(0,1),(1,0),(1,1)}	1	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
5	Already visited, skip	(0,1)	{(0,0),(0,1),(1,0),(1,1)}	1	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
6	Check cell (0,2)	(0,2)	{(0,0),(0,1),(1,0),(1,1)}	1	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
7	Water cell, skip	(0,2)	{(0,0),(0,1),(1,0),(1,1)}	1	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
8	Check cell (2,2)	(2,2)	{(0,0),(0,1),(1,0),(1,1)}	1	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
9	Found land and unvisited, increment count	(2,2)	{(0,0),(0,1),(1,0),(1,1),(2,2)}	2	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
10	DFS explore neighbors from (2,2)	(2,2)	{(0,0),(0,1),(1,0),(1,1),(2,2)}	2	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
11	Check cell (3,3)	(3,3)	{(0,0),(0,1),(1,0),(1,1),(2,2)}	2	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
12	Found land and unvisited, increment count	(3,3)	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3)}	3	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
13	DFS explore neighbors from (3,3)	(3,3)	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3)}	3	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
14	All cells checked	-	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3)}	3	1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1

💡 All cells checked, total islands counted: 3

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 9	After Step 12	Final
count	0	1	1	2	3	3
visited	{}	{(0,0)}	{(0,0),(0,1),(1,0),(1,1)}	{(0,0),(0,1),(1,0),(1,1),(2,2)}	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3)}	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3)}

Key Moments - 3 Insights

Why do we mark cells as visited during DFS/BFS?

Marking cells as visited prevents revisiting the same land cell multiple times, avoiding infinite loops and double counting islands. See execution_table rows 3 and 10 where visited cells grow.

Why do we increment island count only when we find unvisited land?

We count a new island only when we find a land cell not yet visited, meaning a new connected group. This is shown in execution_table rows 2, 9, and 12.

Why do we explore neighbors in four directions only?

Islands are connected horizontally or vertically, not diagonally. So we check up, down, left, right neighbors in DFS/BFS as in the code and execution_table steps.

Visual Quiz - 3 Questions

Look at the execution_table, what is the island count after step 9?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Island Count' column at step 9 in the execution_table.

At which step does the visited set first include cell (2,2)?

A Step 3

B Step 9

C Step 12

D Step 14

💡 Hint

Look at the 'Visited Cells' column in execution_table rows to find when (2,2) appears.

If we did not mark cells as visited, what would happen in the execution?

A The island count would be correct.

B The algorithm would skip some islands.

C The DFS/BFS would revisit cells endlessly causing infinite loops.

D The grid would be modified incorrectly.

💡 Hint

Refer to key_moments about why visited marking is important.

Concept Snapshot

Number of Islands counts connected land groups in a grid.
Scan each cell; if land and unvisited, increment count.
Use DFS or BFS to mark all connected land cells visited.
Neighbors checked: up, down, left, right only.
Return total count after scanning all cells.

Full Transcript

The Number of Islands problem scans a grid cell by cell. When it finds a land cell that hasn't been visited, it counts a new island and explores all connected land cells using DFS or BFS to mark them visited. This prevents counting the same island multiple times. The exploration checks neighbors up, down, left, and right. The process continues until all cells are checked. The final count is the total number of islands.