Number of Islands BFS and DFS in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start BFS from the given cell.

DSA C#

Queue<(int, int)> queue = new Queue<(int, int)>();
queue.[1]((row, col));

Drag options to blanks, or click blank then click option'

AEnqueue

BAdd

CPush

DInsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using Add or Push instead of Enqueue.

In C#, the method to add an item to a Queue is Enqueue.

2fill in blank

medium

Complete the code to mark the current cell as visited in the grid.

DSA C#

grid[row][col] = [1];

Drag options to blanks, or click blank then click option'

A'1'

B'0'

C'2'

D'#'

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited cells as '1' which means land.

We mark visited land cells as '0' to indicate water or visited.

3fill in blank

hard

Fix the error in the DFS recursive call to explore neighbors.

DSA C#

DFS(grid, row + [1], col);
DFS(grid, row, col + [1]);
DFS(grid, row - [1], col);
DFS(grid, row, col - [1]);

Drag options to blanks, or click blank then click option'

A1

B2

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 2 as offset causing no movement or skipping cells.

We move one step in each direction, so the offset is 1.

4fill in blank

hard

Fill both blanks to check if the cell is within grid bounds.

DSA C#

if (row [1] 0 && row [2] grid.Length)

Drag options to blanks, or click blank then click option'

A>=

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or <= which can cause index errors.

Row index must be greater or equal to 0 and less than grid length.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension for counting islands by size.

DSA C#

var islandSizes = new Dictionary<int, int>();
foreach (var size in sizes) {
    if (islandSizes.ContainsKey([1])) {
        islandSizes[[2]] += 1;
    } else {
        islandSizes[[3]] = 1;
    }
}

Drag options to blanks, or click blank then click option'

Asize

B1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong keys or values causing runtime errors.

We use the variable size as the key to count occurrences.

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