Number of Islands BFS and DFS in DSA C# - Execution Trace

Concept Flow - Number of Islands BFS and DFS

Start at each cell in grid

↓

Is cell '1' and unvisited?

No→Move to next cell

Yes↓

Increment island count

↓

Explore neighbors using BFS or DFS

↓

Mark all connected '1's visited

↓

Continue scanning grid

↓

All cells checked?

No→Repeat

Yes↓

Return total island count

Scan each cell; when a '1' is found and not visited, count an island and explore all connected '1's using BFS or DFS to mark them visited.

Execution Sample

DSA C#

int NumIslands(char[][] grid) {
  int count = 0;
  for (int r = 0; r < grid.Length; r++) {
    for (int c = 0; c < grid[0].Length; c++) {
      if (grid[r][c] == '1') {
        BFS(grid, r, c);
        count++;
      }
    }
  }
  return count;
}

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

Execution Table

Step	Operation	Current Cell (r,c)	Island Count	Visited Cells Marked	Visual Grid State
1	Check cell	(0,0)	0	None	[['1','1','0'],['0','1','0'],['0','0','1']]
2	Found '1', start BFS	(0,0)	1	(0,0)	[['V','1','0'],['0','1','0'],['0','0','1']]
3	BFS visit neighbor	(0,1)	1	(0,0),(0,1)	[['V','V','0'],['0','1','0'],['0','0','1']]
4	BFS visit neighbor	(1,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
5	No more neighbors	N/A	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
6	Check cell	(0,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
7	Check cell	(0,2)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
8	Check cell	(1,0)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
9	Check cell	(1,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
10	Check cell	(1,2)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
11	Check cell	(2,0)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
12	Check cell	(2,1)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
13	Check cell	(2,2)	1	(0,0),(0,1),(1,1)	[['V','V','0'],['0','V','0'],['0','0','1']]
14	Found '1', start BFS	(2,2)	2	(0,0),(0,1),(1,1),(2,2)	[['V','V','0'],['0','V','0'],['0','0','V']]
15	No more neighbors	N/A	2	(0,0),(0,1),(1,1),(2,2)	[['V','V','0'],['0','V','0'],['0','0','V']]
16	All cells checked	N/A	2	(0,0),(0,1),(1,1),(2,2)	[['V','V','0'],['0','V','0'],['0','0','V']]

💡 All cells checked, BFS explored all connected lands, total islands counted = 2

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 14	Final
Island Count	0	1	1	1	2	2
Visited Cells	{}	{(0,0)}	{(0,0),(0,1)}	{(0,0),(0,1),(1,1)}	{(0,0),(0,1),(1,1),(2,2)}	{(0,0),(0,1),(1,1),(2,2)}

Key Moments - 3 Insights

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

Marking cells visited prevents counting the same land cell multiple times, as shown in steps 2-5 where connected cells are marked to avoid recounting.

Why do we increment island count only when we find an unvisited '1'?

Because each unvisited '1' represents a new island start; BFS/DFS then marks all connected land cells visited, so we don't count connected parts again (see steps 2 and 14).

What happens if we don't check if a cell is visited before BFS/DFS?

We would count the same island multiple times, inflating the island count incorrectly, as BFS/DFS would run repeatedly on the same connected land.

Visual Quiz - 3 Questions

Look at the execution table, what is the island count after step 4?

A 1

B 0

C 2

D 3

💡 Hint

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

At which step does the BFS start for the second island?

A Step 5

B Step 10

C Step 14

D Step 16

💡 Hint

Look for the step where 'Found '1', start BFS' happens again after the first island.

If we did not mark visited cells, how would the island count change?

A It would decrease

B It would increase incorrectly

C It would stay the same

D It would be zero

💡 Hint

Refer to key_moments about why marking visited cells is important to avoid double counting.

Concept Snapshot

Number of Islands:
- Scan each cell in grid
- If cell is '1' and unvisited, increment island count
- Use BFS or DFS to mark all connected '1's visited
- Continue until all cells checked
- Return total island count

Full Transcript

This concept counts the number of islands in a grid of '1's (land) and '0's (water). We scan each cell. When we find a '1' that is not visited, we start BFS or DFS to mark all connected land cells as visited. This prevents counting the same island multiple times. We increment the island count each time we start BFS/DFS on a new unvisited land cell. The process continues until all cells are checked. The final count is the number of islands.

Practice

1. What does the "Number of Islands" problem typically ask you to find in a 2D grid?

easy

A. Calculate the perimeter of islands

B. Find the largest island size

C. Replace all '1's with '0's

D. Count how many groups of connected '1's (land) exist

Solution

1. Step 1: Understand the problem statement

   The problem asks to count distinct islands, where islands are groups of connected '1's (land) in the grid.

2. Step 2: Identify what is being counted

   We count how many separate groups of connected land cells exist, not their size or perimeter.

3. Final Answer:

   Count how many groups of connected '1's (land) exist -> Option D

4. Quick Check:

   Number of islands = count of connected land groups [OK]

Hint: Islands = connected groups of '1's in grid [OK]

Common Mistakes:

• Confusing island count with island size
• Counting water cells instead of land
• Ignoring connectivity rules (horizontal and vertical)

2. Which of the following C# code snippets correctly initializes a 2D char array representing a grid for the Number of Islands problem?

easy

A. char[,] grid = new char[][] { {'1','0'}, {'0','1'} };

B. char[,] grid = { {'1','0'}, {'0','1'} };

C. char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} };

D. char[][] grid = new char[2][2] { {'1','0'}, {'0','1'} };

Solution

1. Step 1: Understand C# 2D array initialization

   In C#, jagged arrays (array of arrays) are declared as char[][] and initialized with new char[][] and inner arrays. Number of Islands uses jagged arrays for grid[r][c] access and grid[0].Length.

2. Step 2: Check each option's syntax

   char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} };: char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} }; correctly uses jagged array syntax.
   char[,] grid = new char[][] { {'1','0'}, {'0','1'} };: declares char[,] (rectangular) but tries jagged init - type mismatch.
   char[,] grid = { {'1','0'}, {'0','1'} };: valid rectangular char[,], but incompatible with grid[r][c] and grid[0].Length.
   char[][] grid = new char[2][2] { {'1','0'}, {'0','1'} };: new char[2][2] invalid syntax (incorrect brackets).

3. Final Answer:

   char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} }; -> Option C

4. Quick Check:

   Jagged array with new keyword = correct syntax [OK]

Hint: Use 'new' keyword for jagged arrays in C# [OK]

Common Mistakes:

• Omitting 'new' keyword in array initialization
• Confusing jagged arrays with rectangular arrays
• Using wrong braces or missing inner arrays

3. Given the following grid and BFS-based code snippet, what is the output (number of islands)?

char[][] grid = new char[][] {
  new char[] {'1','1','0','0'},
  new char[] {'1','0','0','1'},
  new char[] {'0','0','1','1'},
  new char[] {'0','0','0','0'}
};

int CountIslands(char[][] grid) {
  int count = 0;
  int rows = grid.Length;
  int cols = grid[0].Length;
  bool[][] visited = new bool[rows][];
  for (int i = 0; i < rows; i++) visited[i] = new bool[cols];

  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (grid[r][c] == '1' && !visited[r][c]) {
        BFS(r, c, grid, visited);
        count++;
      }
    }
  }
  return count;
}

void BFS(int r, int c, char[][] grid, bool[][] visited) {
  int[] dr = { -1, 1, 0, 0 };
  int[] dc = { 0, 0, -1, 1 };
  Queue<(int, int)> queue = new Queue<(int, int)>();
  queue.Enqueue((r, c));
  visited[r][c] = true;

  while (queue.Count > 0) {
    var (row, col) = queue.Dequeue();
    for (int i = 0; i < 4; i++) {
      int nr = row + dr[i];
      int nc = col + dc[i];
      if (nr >= 0 && nr < grid.Length && nc >= 0 && nc < grid[0].Length && grid[nr][nc] == '1' && !visited[nr][nc]) {
        queue.Enqueue((nr, nc));
        visited[nr][nc] = true;
      }
    }
  }
}

Console.WriteLine(CountIslands(grid));

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Analyze the grid for connected islands

   Islands are groups of '1's connected horizontally or vertically. The grid has these islands:
   - Island 1: (0,0),(0,1),(1,0)
   - Island 2: (1,3)
   - Island 3: (2,2),(2,3)

2. Step 2: BFS visits each island once

   The BFS marks all connected '1's as visited. Each BFS call increments count by 1. Total BFS calls = number of islands = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count islands by BFS calls = 3 [OK]

Hint: Count BFS calls on unvisited '1's = number of islands [OK]

Common Mistakes:

• Counting diagonally connected '1's as one island
• Missing isolated single '1's as islands
• Not marking visited cells properly

4. Identify the bug in the following DFS code for counting islands and select the correct fix:

void DFS(int r, int c, char[][] grid, bool[][] visited) {
  if (r < 0 || r >= grid.Length || c < 0 || c >= grid[0].Length || grid[r][c] == '0')
    return;
  visited[r][c] = true;
  DFS(r - 1, c, grid, visited);
  DFS(r + 1, c, grid, visited);
  DFS(r, c - 1, grid, visited);
  DFS(r, c + 1, grid, visited);
}

int CountIslands(char[][] grid) {
  int count = 0;
  int rows = grid.Length;
  int cols = grid[0].Length;
  bool[][] visited = new bool[rows][];
  for (int i = 0; i < rows; i++) visited[i] = new bool[cols];

  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (grid[r][c] == '1' && !visited[r][c]) {
        DFS(r, c, grid, visited);
        count++;
      }
    }
  }
  return count;
}

medium

A. Change grid[r][c] == '0' to grid[r][c] == '1' in base case

B. Add a check for visited[r][c] before recursive DFS calls

C. Initialize visited array with 'true' instead of 'false'

D. Remove visited array and rely on grid modification

Solution

1. Step 1: Identify missing visited check in DFS

   The DFS function does not check if a cell is already visited before recursive calls, causing infinite recursion or revisiting.

2. Step 2: Fix by adding visited check before recursion

   Adding "if (visited[r][c]) return;" before marking visited prevents revisiting cells and infinite loops.

3. Final Answer:

   Add a check for visited[r][c] before recursive DFS calls -> Option B

4. Quick Check:

   Prevent revisiting by checking visited before DFS calls [OK]

Hint: Always check visited before DFS recursion to avoid loops [OK]

Common Mistakes:

• Not checking visited before recursion
• Confusing base case conditions
• Modifying grid instead of using visited array

5. You want to modify the Number of Islands solution to count islands considering diagonal connections as well (8 directions). Which change is needed in the BFS or DFS traversal?

hard

A. Add diagonal directions (-1,-1), (-1,1), (1,-1), (1,1) to the direction arrays

B. Only check horizontal neighbors, ignore vertical and diagonal

C. Use a stack instead of a queue for BFS

D. Change grid cells from '1' to '2' when visited

Solution

1. Step 1: Understand connectivity rules

   Original problem connects cells horizontally and vertically (4 directions). To include diagonals, add those directions.

2. Step 2: Modify direction arrays for 8 directions

   Add diagonal moves (-1,-1), (-1,1), (1,-1), (1,1) to dr and dc arrays to explore all neighbors.

3. Final Answer:

   Add diagonal directions (-1,-1), (-1,1), (1,-1), (1,1) to the direction arrays -> Option A

4. Quick Check:

   Include diagonals by adding their directions [OK]

Hint: Add diagonal moves to directions for 8-way connectivity [OK]

Common Mistakes:

• Ignoring diagonal neighbors
• Confusing BFS and DFS data structures
• Changing grid values instead of using visited array