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.

Practice

1. What does the "Number of Islands" problem ask you to find in a grid of '1's and '0's?

easy

A. Calculate the perimeter of islands

B. Count how many groups of connected '1's (islands) exist

C. Count all '0's in the grid

D. Find the largest island size

Solution

1. Step 1: Understand the grid representation

   The grid contains '1's representing land and '0's representing water.

2. Step 2: Identify what the problem asks

   We need to count how many separate groups of connected '1's (islands) are present.

3. Final Answer:

   Count how many groups of connected '1's (islands) exist -> Option B

4. Quick Check:

   Islands = groups of connected '1's [OK]

Hint: Islands = connected lands, count groups of '1's [OK]

Common Mistakes:

• Counting total '1's instead of groups
• Confusing islands with largest island size
• Counting '0's instead of '1's

2. Which of the following TypeScript code snippets correctly initializes a 2D grid for the Number of Islands problem?

easy

A. const grid: string[] = ['10', '01'];

B. const grid: number[] = [1, 0, 0, 1];

C. const grid: string[][] = [['1','0'], ['0','1']];

D. const grid: string[][] = ['1', '0', '0', '1'];

Solution

1. Step 1: Check the grid type

   The grid should be a 2D array of strings representing '1' and '0'.

2. Step 2: Validate each option

   const grid: string[][] = [['1','0'], ['0','1']]; correctly uses a 2D array of strings. Others use incorrect types or structures.

3. Final Answer:

   const grid: string[][] = [['1','0'], ['0','1']]; -> Option C

4. Quick Check:

   2D array of strings = correct grid type [OK]

Hint: Grid must be 2D array of strings '1' or '0' [OK]

Common Mistakes:

• Using 1D arrays instead of 2D
• Using number arrays instead of string arrays
• Initializing grid as array of strings instead of array of arrays

3. Given the following grid, what is the number of islands found by a BFS or DFS algorithm?

const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
];

medium

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Identify connected groups of '1's

   First island: top-left 2x2 block of '1's. Second island: single '1' at (2,2). Third island: two connected '1's at bottom-right.

2. Step 2: Count total islands

   There are 3 separate islands in total.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count connected '1' groups = 3 [OK]

Hint: Count connected '1' clusters carefully [OK]

Common Mistakes:

• Counting diagonal connections as connected
• Missing single isolated '1's
• Counting all '1's instead of groups

4. Identify the bug in this DFS implementation for counting islands:

function dfs(grid: string[][], r: number, c: number) {
  if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') {
    return;
  }
  grid[r][c] = '0';
  dfs(grid, r + 1, c);
  dfs(grid, r - 1, c);
  dfs(grid, r, c + 1);
  // Missing dfs call here
}

medium

A. Missing dfs call for left neighbor (r, c - 1)

B. Should check for '1' instead of '0' in base case

C. grid[r][c] should be set to '1' instead of '0'

D. Parameters r and c are swapped in recursive calls

Solution

1. Step 1: Review recursive DFS calls

   DFS calls are made for down, up, and right neighbors but missing left neighbor (r, c - 1).

2. Step 2: Identify missing neighbor call

   Without calling dfs for left neighbor, some connected lands won't be visited, causing incorrect island count.

3. Final Answer:

   Missing dfs call for left neighbor (r, c - 1) -> Option A

4. Quick Check:

   All four directions must be checked [OK]

Hint: Check all 4 directions in DFS/BFS [OK]

Common Mistakes:

• Forgetting one direction in recursion
• Incorrect base case condition
• Not marking visited cells properly

5. You want to modify the BFS approach to count islands but only consider horizontal connections (left and right) and ignore vertical connections. Given this grid:

const grid = [
  ['1','0','1','0'],
  ['1','1','0','0'],
  ['0','0','1','1']
];

How many islands will your modified BFS count?

hard

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Understand horizontal-only connections

   Islands connect only left and right neighbors, vertical neighbors are ignored.

2. Step 2: Count islands with horizontal connections

   Row 0: '1' at (0,0) alone, '1' at (0,2) alone -> 2 islands.
   Row 1: '1's at (1,0) and (1,1) connected horizontally -> 1 island.
   Row 2: '1's at (2,2) and (2,3) connected horizontally -> 1 island.
   Total islands = 2 + 1 + 1 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Horizontal groups counted = 4 [OK]

Hint: Count only horizontal neighbors as connected [OK]

Common Mistakes:

• Counting vertical neighbors as connected
• Merging islands vertically by mistake
• Ignoring isolated horizontal '1's